Faster quantum and classical SDP approximations for quadratic binary optimization

PIRSA ID: 19100088
Series: Perimeter Institute Quantum Discussions
Event Type: Seminar
Scientific Area(s):
Other
End date:
Speaker(s):
  • Richard Kueng, California Institute of Technology (Caltech)
October 28, 2019 at 2:00 PM Bob Room

We give a quantum speedup for solving the canonical semidefinite programming relaxation for binary quadratic optimization. The class of relaxations for combinatorial optimization has so far eluded quantum speedups. Our methods combine ideas from quantum Gibbs sampling and matrix exponent updates. A de-quantization of the algorithm also leads to a faster classical solver. For generic instances, our quantum solver gives a nearly quadratic speedup over state-of-the-art algorithms.
This is joint work with Fernando Brandao (Caltech) and Daniel Stilck Franca (QMATH, Copenhagen).