skip to content

Semidefinite optimization approaches to classical and quantum combinatorial optimization

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

Block seminar: February 23 - February 25, 2023

More information to be provided later.

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.