Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs

Abstract

The $p$-stage Quantum Approximate Optimization Algorithm (QAOA${}_p$) is a promising approach for combinatorial optimization on noisy intermediate-scale quantum (NISQ) devices, but its theoretical behavior is not well understood beyond $p=1$. We analyze QAOA${}_2$ for the maximum cut problem (MAX-CUT), deriving a graph-size-independent expression for the expected cut fraction on any $D$-regular graph of girth $>5$ (i.e. without triangles, squares, or pentagons). We show that for all degrees $D\ge 2$ and every $D$-regular graph $G$ of girth $>5$, QAOA${}_2$ has a larger expected cut fraction than QAOA${}_1$ on $G$. However, we also show that there exists a $2$-local randomized classical algorithm $A$ such that $A$ has a larger expected cut fraction than QAOA${}_2$ on all $G$. This supports our conjecture that for every constant $p$, there exists a local classical MAX-CUT algorithm that performs as well as QAOA${}_p$ on all graphs.

7+10 pages, 2 figures, code online at https://nbviewer.jupyter.org/github/marwahaha/qaoa-local-competitors/blob/master/2-step-comparison.ipynb

References in corpus (10)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Quantum Computing in the NISQ era and beyond
• The theory of variational hybrid quantum-classical algorithms
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Classical and Quantum Bounded Depth Approximation Algorithms
• Quantum Annealing: a journey through Digitalization, Control, and hybrid Quantum Variational schemes
• What do QAOA energies reveal about graphs?

Cited by in corpus (15)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Warm-starting quantum optimization
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
• Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
• Scaling Quantum Approximate Optimization on Near-term Hardware
• Quantum-Enhanced Greedy Combinatorial Optimization Solver
• Analytical Framework for Quantum Alternating Operator Ansätze
• Bounds on approximating Max $k$XOR with quantum and classical local algorithms
• Reinforcement Learning Assisted Recursive QAOA
• Recursive QAOA outperforms the original QAOA for the MAX-CUT problem on complete graphs
• Iterative Layerwise Training for Quantum Approximate Optimization Algorithm
• A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz
• Performance Analysis of Multi-Angle QAOA for p > 1
• Digital Zero-Noise Extrapolation with Quantum Circuit Unoptimization
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm