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 (12)

• A Quantum Approximate Optimization Algorithm
• Quantum circuits for strongly correlated quantum systems
• Efficient Quantum Circuits for Schur and Clebsch-Gordan Transforms
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• Generalized swap networks for near-term quantum computing
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• A Divide-and-Conquer Approach to Dicke State Preparation
• Fast-forwarding quantum evolution
• Short-Depth Circuits for Dicke State Preparation
• 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