PIRSA:19100088

Video URL

https://pirsa.org/19100088

Faster quantum and classical SDP approximations for quadratic binary optimization

Kueng, R. (2019). Faster quantum and classical SDP approximations for quadratic binary optimization. Perimeter Institute for Theoretical Physics. https://pirsa.org/19100088

Kueng, Richard. Faster quantum and classical SDP approximations for quadratic binary optimization. Perimeter Institute for Theoretical Physics, Oct. 28, 2019, https://pirsa.org/19100088 

          @misc{ scivideos_PIRSA:19100088,
            doi = {10.48660/19100088},
            url = {https://pirsa.org/19100088},
            author = {Kueng, Richard},
            keywords = {Other Physics},
            language = {en},
            title = {Faster quantum and classical SDP approximations for quadratic binary optimization},
            publisher = {Perimeter Institute for Theoretical Physics},
            year = {2019},
            month = {oct},
            note = {PIRSA:19100088 see, \url{https://scivideos.org/pirsa/19100088}}
          }

Richard Kueng California Institute of Technology

Talk numberPIRSA:19100088
DOI10.48660/19100088
Source RepositoryPIRSA
Collection
Talk Type Scientific Series
Subject

Abstract

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).