The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size 论文
摘要
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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>p</mml:mi></mml:math>. 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math> spins with all-to-all random signed couplings. There is a recent classical algorithm by Montanari that, assuming a widely believed conjecture, can efficiently find an approximate solution for a typical instance of the SK model to within <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo>&#x2212;</mml:mo><mml:mi>&#x03F5;</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math> times the ground state energy. We 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mn>2</mml:mn><mml:mi>p</mml:mi></mml:math> QAOA parameters, in the infinite size limit that can be evaluated on a computer with <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mn>16</mml:mn><mml:mi>p</mml:mi></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math> complexity. We evaluate the formula up to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>p</mml:mi><mml:mo>=</mml:mo><mml:mn>12</mml:mn></mml:math>, and find that the QAOA at <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>p</mml:mi><mml:mo>=</mml:mo><mml:mn>11</mml:mn></mml:math> outperforms the standard semidefinite programming algorithm. Moreover, we show concentration: With probability tending to one as <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi><mml:mo stretchy="false">&#x2192;</mml:mo><mml:mi mathvariant="normal">&#x221E;</mml:mi></mml:math>, 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.