The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model
Joao Basso, Edward Farhi, Kunal Marwaha et al. · arXiv (Cornell University) · 2021
The Quantum Approximate Optimization Algorithm (QAOA) finds approximate solutions to combinatorial optimization problems. Its performance monotonically improves with its depth $p$. We apply the QAOA to MaxCut on large-girth $D$-regular graphs. We give an iterative formula to evaluate performance for any $D$ at any depth $p$. Looking at random $D$-regular graphs, at optimal parameters and as $D$ goes to infinity, we find that the $p=11$ QAOA beats all classical algorithms (known to the authors) that are free of unproven conjectures. While the iterative formula for these $D$-regular graphs is derived by looking at a single tree subgraph, we prove that it also gives the ensemble-averaged performance of the QAOA on the Sherrington-Kirkpatrick (SK) model defined on the complete graph. We also generalize our formula to Max-$q$-XORSAT on large-girth regular hypergraphs. Our iteration is a compact procedure, but its computational complexity grows as $O(p^2 4^p)$. This iteration is more efficient than the previous procedure for analyzing QAOA performance on the SK model, and we are able to numerically go to $p=20$. Encouraged by our findings, we make the optimistic conjecture that the QAOA, as $p$ goes to infinity, will achieve the Parisi value. We analyze the performance of the quantum algorithm, but one needs to run it on a quantum computer to produce a string with the guaranteed performance.
Cited by 42 works. doi:10.4230/lipics.tqc.2022.7 Open-access PDF
Authors
References
- OpenMP: an industry standard API for shared-memory programming
- A Quantum Approximate Optimization Algorithm
- Toward a mean field theory for spin glasses
- Gadgets, Approximation, and Linear Programming
- Quantum approximate optimization algorithm for MaxCut: A fermionic view
- The Sherrington-Kirkpatrick Model
- The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
- Optimization of the Sherrington-Kirkpatrick Hamiltonian
- Extremal cuts of sparse random graphs
- MaxCut quantum approximate optimization algorithm performance guarantees for p>1