15407

The Quantum Approximate Optimization Algorithm: Recent Results

APA

(2020). The Quantum Approximate Optimization Algorithm: Recent Results. The Simons Institute for the Theory of Computing. https://simons.berkeley.edu/talks/quantum-approximate-optimization-algorithm-recent-results

MLA

The Quantum Approximate Optimization Algorithm: Recent Results. The Simons Institute for the Theory of Computing, Feb. 26, 2020, https://simons.berkeley.edu/talks/quantum-approximate-optimization-algorithm-recent-results

BibTex

          @misc{ scivideos_15407,
            doi = {},
            url = {https://simons.berkeley.edu/talks/quantum-approximate-optimization-algorithm-recent-results},
            author = {},
            keywords = {},
            language = {en},
            title = {The Quantum Approximate Optimization Algorithm: Recent Results},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2020},
            month = {feb},
            note = {15407 see, \url{https://scivideos.org/Simons-Institute/15407}}
          }
          
Edward Farhi (Google)
Talk number15407
Source RepositorySimons Institute

Abstract

1. Landscape Independence.  Consider problems where instances come from a fixed distritution such as MAX CUT on d-regular random graphs of fixed size.  Then regardless of the depth of the algorithm, for fixed parameters the expected value of cost funtion in the associated quantum state is independent of the instance up to finite size effects. This Landscape Independence shows that once good parameters have been chosen for one instance they can be used for others coming from the same distribution. 2.Sherrington Kirkpatrick.  This is an all to all connected spin glass model. We have a method for calculating the expected value of the cost function at any parameters for typical instances in the infinite size limit. The method works for any depth p (independent of the number of spins) and numerically we have gone out to p of 8.  I will also discuss provable concentration results which confirm Landscape Independence for the SK model.