Скачать с ютуб QIP2021 | The Quantum Approximate Optimization Algorithm (Leo Zhou) в хорошем качестве

QIP2021 | The Quantum Approximate Optimization Algorithm (Leo Zhou)

Authors: Edward Farhi, Jeffrey Goldstone, Sam Gutmann and Leo Zhou Affiliations: Google | Massachusetts Institute of Technology | not applicable | Harvard University Abstract: The Quantum Approximate Optimization Algorithm (QAOA) is a general-purpose algorithm for combinatorial optimization problems whose performance can only improve with the number of layers p. While QAOA holds promise as an algorithm that can be run on near-term quantum computers, its computational power has not been fully explored. In this work, we study the QAOA applied to the Sherrington-Kirkpatrick (SK) model, which can be understood as energy minimization of n spins with all-to-all random signed couplings. There is a recent classical algorithm by Montanari that, assuming a widely believed conjecture, can be tailored to efficiently find an approximate solution for a typical instance of the SK model to within (1-epsilon) times the ground state energy. We can only hope to match its performance with the QAOA. Our main result is a novel technique that allows us to evaluate the typical-instance energy of the QAOA applied to the SK model. We produce a formula for the expected value of the energy, as a function of the 2p QAOA parameters, in the infinite size limit that can be evaluated on a computer with O(16^p) complexity. We evaluate the formula up to p=12, and find that the QAOA at p=11 outperforms the standard semidefinite programming algorithm. Moreover, we show concentration: With probability tending to one as n goes to infinity, measurements of the QAOA will produce strings whose energies concentrate at our calculated value. As an algorithm running on a quantum computer, there is no need to search for optimal parameters on an instance-by-instance basis since we can determine them in advance. What we have here is a new framework for analyzing the QAOA, and our techniques can be of broad interest for evaluating its performance on more general problems where classical algorithms may fail. Get entangled with us! ▶ QIP2021 Conference: https://www.mcqst.de​/qip2021 ▶ Website: https://www.mcqst.de​ ▶ Twitter:   / mcqst_cluster​   ▶ LinkedIn:   / mcqst