Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios

Abstract

The quantum approximate optimization algorithm, also known in its generalization as the quantum alternating operator ansatz, (QAOA) is a heuristic hybrid quantum-classical algorithm for finding high-quality approximate solutions to combinatorial optimization problems, such as maximum satisfiability. While the QAOA is well studied, theoretical results as to its runtime or approximation ratio guarantees are still relatively sparse. We provide some of the first lower bounds for the number of rounds (the dominant component of QAOA runtimes) required for the QAOA. For our main result, we (i) leverage a connection between quantum annealing times and the angles of the QAOA to derive a lower bound on the number of rounds of the QAOA with respect to the guaranteed approximation ratio. We apply and calculate this bound with Grover-style mixing unitaries and (ii) show that this type of QAOA requires at least a polynomial number of rounds to guarantee any constant approximation ratios for most problems. We also (iii) show that the bound depends only on the statistical values of the objective functions, and when the problem can be modeled as a $k$-local Hamiltonian, can be easily estimated from the coefficients of the Hamiltonians. For the conventional transverse-field mixer, (iv) our framework gives a trivial lower bound to all bounded-occurrence local cost problems and for all strictly $k$-local cost Hamiltonians matching known results that constant approximation ratio is obtainable with a constant-round QAOA for a few optimization problems from these classes. Using our proof framework, (v) we recover the Grover lower bound for unstructured search and, with small modification, show that our bound applies to any QAOA-style search protocol that starts in the ground state of the mixing unitaries.

20 pages, comments welcome, close to the published version

References in corpus (16)

• Variational Quantum Algorithms
• Spatial search by quantum walk
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Counterdiabaticity and the quantum approximate optimization algorithm
• MAXCUT QAOA performance guarantees for p >1
• Quadratic speedup for spatial search by continuous-time quantum walk
• Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
• Low depth mechanisms for quantum optimization
• Analytical Framework for Quantum Alternating Operator Ansätze
• On Circuit Depth Scaling For Quantum Approximate Optimization
• Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement
• Lower Bounds on Quantum Annealing Times
• Ultrafast critical ground state preparation via bang-bang protocols
• Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations
• Problem-Size Independent Angles for a Grover-Driven Quantum Approximate Optimization Algorithm

Cited by in corpus (1)

• Applying Grover-mixer quantum alternating operator ansatz algorithm to higher-order unconstrained binary optimization problems