Classical and Quantum Bounded Depth Approximation Algorithms

Abstract

We consider some classical and quantum approximate optimization algorithms with bounded depth. First, we define a class of "local" classical optimization algorithms and show that a single step version of these algorithms can achieve the same performance as the single step QAOA on MAX-3-LIN-2. Second, we show that this class of classical algorithms generalizes a class previously considered in the literature, and also that a single step of the classical algorithm will outperform the single-step QAOA on all triangle-free MAX-CUT instances. In fact, for all but $4$ choices of degree, existing single-step classical algorithms already outperform the QAOA on these graphs, while for the remaining $4$ choices we show that the generalization here outperforms it. Finally, we consider the QAOA and provide strong evidence that, for any fixed number of steps, its performance on MAX-3-LIN-2 on bounded degree graphs cannot achieve the same scaling as can be done by a class of "global" classical algorithms. These results suggest that such local classical algorithms are likely to be at least as promising as the QAOA for approximate optimization.

arXiv comment17 pages, 8 figures; v2 minor typo corrections

Cited by in corpus (34)

• Noisy intermediate-scale quantum (NISQ) algorithms
• Noise-Induced Barren Plateaus in Variational Quantum Algorithms
• General parameter-shift rules for quantum gradients
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Warm-starting quantum optimization
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• Reachability Deficits in Quantum Approximate Optimization
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Parameter Concentration in Quantum Approximate Optimization
• MAXCUT QAOA performance guarantees for p >1
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Error mitigation for variational quantum algorithms through mid-circuit measurements
• A perspective on protein structure prediction using quantum computers
• Training Saturation in Layerwise Quantum Approximate Optimisation
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
• Abrupt Transitions in Variational Quantum Circuit Training
• Low depth mechanisms for quantum optimization
• Prospects and challenges of quantum finance
• Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
• Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs
• Quantum algorithms with local particle number conservation: noise effects and error correction
• Analytical Framework for Quantum Alternating Operator Ansätze
• Bounds on approximating Max $k$XOR with quantum and classical local algorithms
• Alibaba Cloud Quantum Development Platform: Applications to Quantum Algorithm Design
• What do QAOA energies reveal about graphs?
• Robustness to spontaneous emission of a variational quantum algorithm
• Classical algorithms and quantum limitations for maximum cut on high-girth graphs
• Progress towards analytically optimal angles in quantum approximate optimisation
• Space-efficient binary optimization for variational computing
• A quantum algorithm to count weighted ground states of classical spin Hamiltonians
• Approximate optimization of MAXCUT with a local spin algorithm
• An explicit vector algorithm for high-girth MaxCut
• Policy Gradient Approach to Compilation of Variational Quantum Circuits
• Improving the Quantum Approximate Optimization Algorithm with postselection