The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model

Abstract

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.

39 pages, 7 figures, 5 tables. Full version of the paper in TQC 2022

References in corpus (2)

• A Quantum Approximate Optimization Algorithm
• An explicit vector algorithm for high-girth MaxCut

Cited by in corpus (18)

• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
• Graph neural network initialisation of quantum approximate optimisation
• Parameter Setting in Quantum Approximate Optimization of Weighted Problems
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
• Transfer learning of optimal QAOA parameters in combinatorial optimization
• Characterizing Error Mitigation by Symmetry Verification in QAOA
• Performance Analysis of Multi-Angle QAOA for p > 1
• Trainability Barriers in Low-Depth QAOA Landscapes
• Emergence of noise-induced barren plateaus in arbitrary layered noise models
• Improving the performance of quantum approximate optimization for preparing non-trivial quantum states without translational symmetry
• Equilibrium dynamics of infinite-range quantum spin glasses in a field
• Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era
• Quantum-classical tradeoffs and multi-controlled quantum gate decompositions in variational algorithms
• Alleviating the quantum Big-$M$ problem
• The Overlap Gap Property limits limit swapping in the QAOA
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming
• Vanishing performance of the parity-encoded quantum approximate optimization algorithm applied to spin-glass models