Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization

Abstract

Despite much recent work, the true promise and limitations of the Quantum Alternating Operator Ansatz (QAOA) are unclear. A critical question regarding QAOA is to what extent its performance scales with the input size of the problem instance, in particular the necessary growth in the number of QAOA rounds to reach a high approximation ratio. We present numerical evidence for an exponential speed-up of QAOA over Grover-style unstructured search in finding approximate solutions to constrained optimization problems. Our result provides a strong hint that QAOA is able to exploit the structure of an optimization problem and thus overcome the lower bound for unstructured search. To this end, we conduct a comprehensive numerical study on several Hamming-weight constrained optimization problems for which we include combinations of all standardly studied mixer and phase separator Hamiltonians (Ring mixer, Clique mixer, Objective Value phase separator) as well as quantum minimum-finding inspired Hamiltonians (Grover mixer, Threshold-based phase separator). We identify Clique-Objective-QAOA with an exponential speed-up over Grover-Threshold-QAOA and tie the latter's scaling to that of unstructured search, with all other QAOA combinations coming in at a distant third. Our result suggests that maximizing QAOA performance requires a judicious choice of mixer and phase separator, and should trigger further research into other QAOA variations.

References in corpus (32)

• A Quantum Approximate Optimization Algorithm
• Strengths and Weaknesses of Quantum Computing
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Quantum Simulation of Electronic Structure with Linear Depth and Connectivity
• A Quantum Algorithm for Finding the Minimum
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Improving Variational Quantum Optimization using CVaR
• $XY$-mixers: analytical and numerical results for QAOA
• Quantum circuits for strongly correlated quantum systems
• Efficient Quantum Circuits for Schur and Clebsch-Gordan Transforms
• Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization
• Reachability Deficits in Quantum Approximate Optimization
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• Deterministic Preparation of Dicke States
• Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
• Quantum Optimization with a Novel Gibbs Objective Function and Ansatz Architecture Search
• MAXCUT QAOA performance guarantees for p >1
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• Generalized swap networks for near-term quantum computing
• Variationally Learning Grover's Quantum Search Algorithm
• The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• A Divide-and-Conquer Approach to Dicke State Preparation
• Fourier transform of fermionic systems and the spectral tensor network
• Fast-forwarding quantum evolution
• Short-Depth Circuits for Dicke State Preparation
• Evaluation of QAOA based on the approximation ratio of individual samples
• Tensor Network Quantum Simulator With Step-Dependent Parallelization
• Threshold-Based Quantum Optimization
• The Quantum Alternating Operator Ansatz for Satisfiability Problems
• Twisted hybrid algorithms for combinatorial optimization

Cited by in corpus (12)

• Challenges and Opportunities in Quantum Optimization
• Provable bounds for noise-free expectation values computed from noisy samples
• Scaling Whole-Chip QAOA for Higher-Order Ising Spin Glass Models on Heavy-Hex Graphs
• High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
• Quantum Speedup of the Dispersion and Codebook Design Problems
• Trainability Barriers in Low-Depth QAOA Landscapes
• Hierarchical Multigrid Ansatz for Variational Quantum Algorithms
• Quantum Approximation Optimization Algorithm for the Trellis based Viterbi Decoding of Classical Error Correcting Codes
• The Lie Algebra of XY-mixer Topologies and Warm Starting QAOA for Constrained Optimization
• Heuristic Time Complexity of NISQ Shortest-Vector-Problem Solvers
• Quantum Circuit Design for Decoded Quantum Interferometry
• Resource-Efficient Quantum Optimization via Higher-Order Encoding