Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models

Abstract

The Quantum Approximate Optimization Algorithm (QAOA) is a general purpose quantum algorithm designed for combinatorial optimization. We analyze its expected performance and prove concentration properties at any constant level (number of layers) on ensembles of random combinatorial optimization problems in the infinite size limit. These ensembles include mixed spin models and Max-$q$-XORSAT on sparse random hypergraphs. Our analysis can be understood via a saddle-point approximation of a sum-over-paths integral. This is made rigorous by proving a generalization of the multinomial theorem, which is a technical result of independent interest. We then show that the performance of the QAOA at constant levels for the pure $q$-spin model matches asymptotically the ones for Max-$q$-XORSAT on random sparse Erdős-Rényi hypergraphs and every large-girth regular hypergraph. Through this correspondence, we establish that the average-case value produced by the QAOA at constant levels is bounded away from optimality for pure $q$-spin models when $q\ge 4$ and is even. This limitation gives a hardness of approximation result for quantum algorithms in a new regime where the whole graph is seen.

13+47 pages, updated introduction

References in corpus (15)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum computational advantage using photons
• A Quantum Approximate Optimization Algorithm
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• MAXCUT QAOA performance guarantees for p >1
• 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
• Quantum approximate optimization is computationally universal
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
• Solving boolean satisfiability problems with the quantum approximate optimization algorithm
• Predicting parameters for the Quantum Approximate Optimization Algorithm for MAX-CUT from the infinite-size limit
• Instance Independence of Single Layer Quantum Approximate Optimization Algorithm on Mixed-Spin Models at Infinite Size
• Circuit Lower Bounds for the p-Spin Optimization Problem

Cited by in corpus (12)

• Challenges and Opportunities in Quantum Optimization
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Parameter Setting in Quantum Approximate Optimization of Weighted Problems
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
• Scaling Whole-Chip QAOA for Higher-Order Ising Spin Glass Models on Heavy-Hex Graphs
• Performance Analysis of Multi-Angle QAOA for p > 1
• Convergence of Digitized-Counterdiabatic QAOA: circuit depth versus free parameters
• Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations
• Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras
• The Overlap Gap Property limits limit swapping in the QAOA
• Resource-Efficient Quantum Optimization via Higher-Order Encoding