Block Seminar – Semidefinite optimization approaches to classical and quantum combinatorial optimization

Organizers: David Gross (University Cologne, Institute for theoretical physics), Frank Vallentin (University Cologne, Department Mathematics/Computer Science), Angelika Wiegele (Alpen-Adria-Universität Klagenfurt / Global faculty of University of Cologne)

Date: Wednesday, February 22, 2023 – Friday, February 24, 2023
Room: Stefan Cohn-Vossen Raum (313), Mathematisches Institut, Weyertal 86-90
Zoom link:

Description: In this block seminar we will build bridges between the fields of mathematical optimization, theoretical computer science and quantum computation. We will start with combinatorial optimization. Examples are the classical problems boolean satisfiability problem (SAT), maximum cut (MAX CUT), maximum independent set, graph coloring, as well as their quantum analogues quantum SAT or quantum MAX CUT. We will see that these problems have in common that they are computationally hard, even for quantum computers. We will investigate that these problems are amenable to semidefinite optimization approaches with the aim of deriving efficient approximation algorithms or computing exact solutions.


Wednesday, February 22, 2023
10:00 – 10:45: Angelika Wiegele  (Algorithms for solving SDP: Interior point methods)
11:00 – 11:45: Angelika Wiegele (Algorithms for solving SDP: Bundle methods)
13:00 – 13:45: Angelika Wiegele (Algorithms for solving SDP: Projection methods)
14:00 – 14:45: Daniel Brosch (SDP for extremal combinatorics)

Thursday, February 23, 2023
10:00 – 10:45 Frank Vallentin (On the integrality gap of the maximum-cut semidefinite programming relaxation in fixed dimension)
11:00 – 11:45: Arne Heimendahl (MIP* = RE and Tsirelson’s problem)
13:00 – 13.30: Karla Leipold (Minimal rank solutions for calculating the EHZ-capacity of polytopes)
13:45 – 14:15: Andreas Spomer (The kissing number problem for regular tetrahedra)
14:30 – 15:00: Sebastian Miebach (Classification of universally optimal quasicodes in real projective spaces)
Evening: Dinner (self paid)

Friday, February 24, 2023
10:00 – 11:00: David Gross (Quantum Crash Course)
11:00 – 12:00: Lionel Jeevan Dmello (Quantum 2-SAT)
13:00 – 14:00: Sahil Ugale (Quantum MAX-CUT)
14:00 – 15:00: Laurens Ligthart (SDP hierarchies for quantum optimization)
optional: 30min run your own hands-on quantum sdp hierarchies. (with jupyter notebook by Laurens Download)