Analytical results for the Quantum Alternating Operator Ansatz with Grover Mixer

Abstract

An important property of QAOA with Grover mixer is that its expectation value is invariant over any permutation of states. As a consequence, the algorithm is independent of the structure of the problem. If, on the one hand, this characteristic raises serious doubts about the capacity of the algorithm to overcome the bound of the unstructured search problem, on the other hand, it can pave the way to its analytical study. In this sense, a prior work introduced a statistical approach to analyze GM-QAOA that results in an analytical expression for the expectation value depending on the probability distribution associated with the problem Hamiltonian spectrum. Although the method provides surprising simplifications in calculations, the expression depends exponentially on the number of layers, which makes direct analytical treatment unfeasible. In this work, we extend the analysis to the more simple context of Grover Mixer Threshold QAOA (GM-Th-QAOA), a variant that replaces the phase separation operator of GM-QAOA to encode a threshold function. As a result, we obtain an expression for the expectation value independent of the number of layers and, with it, we provide bounds for different performance metrics. Furthermore, we extend the analysis to a more general context of QAOA with Grover mixer, which we called Grover-based QAOA. In that framework, which allows the phase separation operator to encode any compilation of the cost function, we generalize all the bounds by using an argument by contradiction with the optimality of Grover's algorithm on the unstructured search problem. As a result, we get the main contribution of this work, an asymptotic lower bound on the quantile achieved by the expectation value that formalizes the notion that the Grover mixer, at most, reflects a quadratic Grover-style speed-up over classical brute force.

23 pages, 8 figures. Improved text for clarity, added references, corrected typos

References in corpus (27)

• Quantum Computing in the NISQ era and beyond
• Quantum Mechanics helps in searching for a needle in a haystack
• Variational Quantum Algorithms
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Strengths and Weaknesses of Quantum Computing
• Quantum random walks - an introductory overview
• Quantum Computation and Decision Trees
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Grover's quantum searching algorithm is optimal
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Improving Variational Quantum Optimization using CVaR
• $XY$-mixers: analytical and numerical results for QAOA
• Challenges and Opportunities in Quantum Optimization
• Grover Adaptive Search for Constrained Polynomial Binary Optimization
• Reachability Deficits in Quantum Approximate Optimization
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• Quantum Optimization with a Novel Gibbs Objective Function and Ansatz Architecture Search
• MAXCUT QAOA performance guarantees for p >1
• Variationally Learning Grover's Quantum Search Algorithm
• Constrained mixers for the quantum approximate optimization algorithm
• A quantum walk assisted approximate algorithm for bounded NP optimisation problems
• Combinatorial optimisation via highly efficient quantum walks
• Evaluation of QAOA based on the approximation ratio of individual samples
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Lower Bounds on Quantum Annealing Times
• Problem-Size Independent Angles for a Grover-Driven Quantum Approximate Optimization Algorithm

Cited by in corpus (4)

• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering
• Efficient Large-Scale Quantum Optimization via Counterdiabatic Ansatz
• Applying Grover-mixer quantum alternating operator ansatz algorithm to higher-order unconstrained binary optimization problems
• Counting with the quantum alternating operator ansatz