Quantum mechanics

Function (biology)

Algorithm

Quantum computer

Biology

Discrete mathematics

Statistics

Semidefinite programming

Applied mathematics

Energy minimization

Energy (signal processing)

Computer science

Mathematical optimization

Limit (mathematics)

Evolutionary biology

Physics

Mathematics

Value (mathematics)

Mathematical analysis

Minification

Artificial intelligence

Quantum

Combinatorics

Conjecture

Machine learning

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>&amp;#x2212;</mml:mo><mml:mi>&amp;#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">&amp;#x2192;</mml:mo><mml:mi mathvariant="normal">&amp;#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.

The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size