The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples

Abstract

The Quantum Approximate Optimization Algorithm can be applied to search problems on graphs with a cost function that is a sum of terms corresponding to the edges. When conjugating an edge term, the QAOA unitary at depth p produces an operator that depends only on the subgraph consisting of edges that are at most p away from the edge in question. On random d-regular graphs, with d fixed and with p a small constant time log n, these neighborhoods are almost all trees and so the performance of the QAOA is determined only by how it acts on an edge in the middle of tree. Both bipartite random d-regular graphs and general random d-regular graphs locally are trees so the QAOA's performance is the same on these two ensembles. Using this we can show that the QAOA with $(d-1{)}^{2p}<n^A$ for any $A<1$, can only achieve an approximation ratio of 1/2 for Max-Cut on bipartite random d-regular graphs for d large. For Maximum Independent Set, in the same setting, the best approximation ratio is a d-dependent constant that goes to 0 as d gets big.

6 pages, no figures

References in corpus (7)

• A Quantum Approximate Optimization Algorithm
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Extremal Cuts of Sparse Random Graphs
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• Random MAX SAT, Random MAX CUT, and Their Phase Transitions
• Cubic graphs with small independence ratio

Cited by in corpus (26)

• Noisy intermediate-scale quantum (NISQ) algorithms
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• MAXCUT QAOA performance guarantees for p >1
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Hybrid quantum-classical algorithms for approximate graph coloring
• Fast quantum circuit cutting with randomized measurements
• Error mitigation for variational quantum algorithms through mid-circuit measurements
• Exploiting Symmetry Reduces the Cost of Training QAOA
• 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
• Analytical Framework for Quantum Alternating Operator Ansätze
• Error Mitigation for Deep Quantum Optimization Circuits by Leveraging Problem Symmetries
• Approaches to Constrained Quantum Approximate Optimization
• Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization
• Exponentially tighter bounds on limitations of quantum error mitigation
• Networked Quantum Services
• Quantum Local Search with the Quantum Alternating Operator Ansatz
• High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
• Classical algorithms and quantum limitations for maximum cut on high-girth graphs
• Space-efficient binary optimization for variational computing
• Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• Limits of Short-Time Evolution of Local Hamiltonians
• Improving the Quantum Approximate Optimization Algorithm with postselection
• Vanishing performance of the parity-encoded quantum approximate optimization algorithm applied to spin-glass models