GAMP/QMATH seminar by Daniel França (QMATH)

Research Seminar for GAMP/QMATH (Geometric Analysis and Mathematical Physics/Villum Centre for the Mathematics of Quantum Theory)

Speaker: Daniel Stilck França (QMATH).

Title: Quantum Speed-up for the Goemans-Williamson.

Abstract:
We give a quantum algorithm for finding large cuts for d-regular graphs with n vertices,
running in time O(n^2d^(−1/2)). The cut obtained achieves the approximation ratio of the
Goemans-Williamson semidefinite programming based approximation algorithm for the
maximum cut, which requires Ω(nd) time to be solved classically. Our method gives
a speed-up for graphs with d >n^2/3. The algorithm builds on quantum semidefinite
programming solvers recently developed, overcoming their main limitation of the high
cost in terms of the error of the solution. For obtaining the cut, we also show how the original Goemans-Williamson rounding scheme can be
implemented faster on a quantum computer.
This is joint work with Fernando Brandao and Richard Kueng.