The Overlap Gap Property limits limit swapping in the QAOA

Abstract

The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm designed for Combinatorial Optimization Problem (COP). We show that if a local algorithm is limited in performance at logarithmic depth for a spin glass type COP with an underlying Erdös--Rényi hypergraph, then a random regular hypergraph is similarly limited in performance as well. As such, we re-derived the fact that the average-case value obtained by the QAOA for even $q\ge 4$, Max-$q$-XORSAT is bounded away from optimality when optimised using asymptotic analysis due to the Overlap Gap Property (OGP). While this result was proven before, the proof is rather technical compared to ours. In addition, we show that the earlier result implicitly also implies limitation at logarithmic depth $p\le \epsilon \log n$ providing an improvement over limitation at constant depth. Furthermore, the extension to logarithmic depth leads to a tightening of the upper bound that the QAOA outputs at logarithmic depth for MaxCUT and Max-$q$-XORSAT problems. We also provide some numerical evidence the limitation should be extended to odd $q$ by showing that the OGP exists for the Max-$3$-XORSAT on random regular graphs.

26 pages, 5 figures, to be published in the journal of quantum information and computation

References in corpus (17)

• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Clustering of solutions in the random satisfiability problem
• Extremal Cuts of Sparse Random Graphs
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• Suboptimality of local algorithms for a class of max-cut problems
• The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model
• Disordered Systems Insights on Computational Hardness
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
• Algorithmic Thresholds in Mean Field Spin Glasses
• Embedding the Erdős-Rényi Hypergraph into the Random Regular Hypergraph and Hamiltonicity
• Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations
• Local algorithms and the failure of log-depth quantum advantage on sparse random CSPs
• The Overlap Gap Property limits limit swapping in the QAOA
• Algorithmic Threshold for Multi-Species Spherical Spin Glasses
• Limitations of Quantum Approximate Optimization in Solving Generic Higher-Order Constraint-Satisfaction Problems

Cited by in corpus (2)

• The Overlap Gap Property limits limit swapping in the QAOA
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm