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 $p$. While QAOA holds promise as an algorithm that can be run on near-term quantum computers, its computational po...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
2022-07-01
|
| Series: | Quantum |
| Online Access: | https://quantum-journal.org/papers/q-2022-07-07-759/pdf/ |
| _version_ | 1818114564551606272 |
|---|---|
| author | Edward Farhi Jeffrey Goldstone Sam Gutmann Leo Zhou |
| author_facet | Edward Farhi Jeffrey Goldstone Sam Gutmann Leo Zhou |
| author_sort | Edward Farhi |
| collection | DOAJ |
| description | 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 efficiently find an approximate solution for a typical instance of the SK model to within $(1-\epsilon)$ 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 $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\to\infty$, 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. |
| first_indexed | 2024-12-11T03:52:44Z |
| format | Article |
| id | doaj.art-00569b43a08a4dd2a7eadbecd4ea4283 |
| institution | Directory Open Access Journal |
| issn | 2521-327X |
| language | English |
| last_indexed | 2024-12-11T03:52:44Z |
| publishDate | 2022-07-01 |
| publisher | Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften |
| record_format | Article |
| series | Quantum |
| spelling | doaj.art-00569b43a08a4dd2a7eadbecd4ea42832022-12-22T01:21:51ZengVerein zur Förderung des Open Access Publizierens in den QuantenwissenschaftenQuantum2521-327X2022-07-01675910.22331/q-2022-07-07-75910.22331/q-2022-07-07-759The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite SizeEdward FarhiJeffrey GoldstoneSam GutmannLeo ZhouThe 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 efficiently find an approximate solution for a typical instance of the SK model to within $(1-\epsilon)$ 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 $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\to\infty$, 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.https://quantum-journal.org/papers/q-2022-07-07-759/pdf/ |
| spellingShingle | Edward Farhi Jeffrey Goldstone Sam Gutmann Leo Zhou The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size Quantum |
| title | The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size |
| title_full | The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size |
| title_fullStr | The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size |
| title_full_unstemmed | The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size |
| title_short | The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size |
| title_sort | quantum approximate optimization algorithm and the sherrington kirkpatrick model at infinite size |
| url | https://quantum-journal.org/papers/q-2022-07-07-759/pdf/ |
| work_keys_str_mv | AT edwardfarhi thequantumapproximateoptimizationalgorithmandthesherringtonkirkpatrickmodelatinfinitesize AT jeffreygoldstone thequantumapproximateoptimizationalgorithmandthesherringtonkirkpatrickmodelatinfinitesize AT samgutmann thequantumapproximateoptimizationalgorithmandthesherringtonkirkpatrickmodelatinfinitesize AT leozhou thequantumapproximateoptimizationalgorithmandthesherringtonkirkpatrickmodelatinfinitesize AT edwardfarhi quantumapproximateoptimizationalgorithmandthesherringtonkirkpatrickmodelatinfinitesize AT jeffreygoldstone quantumapproximateoptimizationalgorithmandthesherringtonkirkpatrickmodelatinfinitesize AT samgutmann quantumapproximateoptimizationalgorithmandthesherringtonkirkpatrickmodelatinfinitesize AT leozhou quantumapproximateoptimizationalgorithmandthesherringtonkirkpatrickmodelatinfinitesize |