The Quantum Alternating Operator Ansatz (QAOA) represents a branch of quantum algorithms for solving combinatorial optimization problems. A specific variant, the Grover-Mixer Quantum Alternating Operator Ansatz (GM-QAOA), ensures uniform amplitude across states that share equivalent objective values. This property makes the algorithm independent of the problem structure, focusing instead on the distribution of objective values within the problem. In this work, we prove the probability upper bound for measuring a computational basis state from a GM-QAOA circuit with a given depth, which is a critical factor in QAOA cost. Using this, we derive the upper bounds for the probability of sampling an optimal solution, and for the approximation ratio of maximum optimization problems, both dependent on the objective value distribution. Through numerical analysis, we link the distribution to the problem size and build the regression models that relate the problem size, QAOA depth, and performance upper bound. Our results suggest that the GM-QAOA provides a quadratic enhancement in sampling probability and requires circuit depth that scales exponentially with problem size to maintain consistent performance.
The Quantum Alternating Operator Ansatz (QAOA) represents a branch of quantum algorithms for solving combinatorial optimization problems. A specific variant, the Grover-Mixer Quantum Alternating Operator Ansatz (GM-QAOA), ensures uniform amplitude across states that share equivalent objective values. This property makes the algorithm independent of the problem structure, focusing instead on the distribution of objective values within the problem. In this work, we prove the probability upper bound for measuring a computational basis state from a GM-QAOA circuit with a given depth, which is a critical factor in QAOA cost. Using this, we derive the upper bounds for the probability of sampling an optimal solution, and for the approximation ratio of maximum optimization problems, both dependent on the objective value distribution. Through numerical analysis, we link the distribution to the problem size and build the regression models that relate the problem size, QAOA depth, and performance upper bound. Our results suggest that the GM-QAOA provides a quadratic enhancement in sampling probability and requires circuit depth that scales exponentially with problem size to maintain consistent performance.
The quantum alternating operator ansatz (QAOA) represents a branch of quantum algorithms for solving combinatorial optimization problems. A specific variant, the Grover-mixer (GM) QAOA, ensures uniform amplitude across states that share equivalent objective values. This property makes the algorithm independent of the problem structure, focusing instead on the distribution of objective values within the problem. In this work we provide an alternative proof for the upper bound on the probability of measuring a computational basis state from a GM QAOA circuit with a given depth, which is a critical factor in QAOA cost. Using this, we derive the upper bounds for the probability of sampling an optimal solution and for the approximation ratio of maximum optimization problems, both dependent on the objective value distribution. Through numerical analysis, we link the distribution to the problem size and build the regression models that relate the problem size, QAOA depth, and performance upper bound. Our results suggest that the GM QAOA provides a quadratic enhancement in sampling probability and requires circuit depth that scales exponentially with problem size to maintain consistent performance.
The Grover mixer operator is a variational version of Grover's diffusion operator, introduced as a mixing operator for the quantum alternating operator ansatz (QAOA) and used in a variant known as Grover mixer QAOA (GM-QAOA). An important property of the 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, 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. We apply that bound on the max-cut problem to the particular class of complete bipartite graphs and argue that the number of rounds required to achieve guarantees for any approximation ratio must grow exponentially with the number of vertices or edges, a severe limitation on the performance of the algorithm.
The Quantum Alternating Operator Ansatz (QAOA) is a promising quantum heuristic to combinatorial optimization, designed for the Noisy Intermediate-Scale Quantum (NISQ) era. A key quantum operator of the algorithm is the mixing, which introduces quantum interference. This work investigates analytically the performance of QAOA with the Grover mixer, a mixing operator inspired by Grover’s algorithm. A critical feature of QAOA with Grover mixer is that it depends only on the probability distribution of the solutions, ignoring the structure of the problem. Due to this, it was conjectured that QAOA with this mixer is bounded to the quadratic speed-up of Grover’s algorithm over the classical brute force on the unstructured search problem. On the other hand, this feature allows the development of a statistical approach, which we explore in this work. For a variant of QAOA called Grover mixing QAOA (GM-QAOA), the analysis leads to an expression for the expectation value whose number of terms depends exponentially on the number of layers of the QAOA. In contrast, for Grover mixer Threshold QAOA (GM-Th-QAOA), a simpler variant that has an intimate relationship with Grover’s algorithm, we obtain a constant-time expression, which allows us to get bounds for different performance metrics, such as the statistical quantities of standard score and quantile. Subsequently, we generalized QAOA with the Grover mixer in a framework we called Grover-based QAOA. By using a contradiction argument with the optimality of Grover’s algorithm, we extend all the bounds of GM-Th-QAOA to the general context of Grover-based QAOA. As a result, we get the main contribution of this work: the proof of the aforementioned conjecture on the performance of QAOA with Grover mixer. We apply our bounds to the class of complete bipartite graphs on the Max-Cut problem, demonstrating that we cannot obtain a polynomial-time algorithm with Grover-based QAOA for these instances, showing that the performance limitation of the Grover mixer can be very severe. Our results suggest that achieving competitive performance with QAOA requires a mixing operator capable of leveraging the structure of combinatorial optimization problems.
The quantum approximate optimization algorithm (QAOA) is among the leading candidates for achieving quantum advantage on near-term processors. While typically implemented with a transverse-field mixer (XM-QAOA), the Grover-mixer variant (GM-QAOA) offers a compelling alternative due to its global search capabilities. This work investigates the application of GM-QAOA to higher-order unconstrained binary optimization (HUBO) problems, also known as polynomial unconstrained binary optimization (PUBO), which form a general class of combinatorial optimization problems involving multivariable interactions. We present a comprehensive numerical study demonstrating that GM-QAOA, unlike XM-QAOA, exhibits monotonic improvement in performance with circuit depth and achieves superior results for HUBO problems within a layerwise optimization framework. An important component of our approach is an analytical framework for modeling GM-QAOA dynamics, which enables a classical approximation of the optimal parameters and helps reduce the optimization overhead. Our resource-efficient parametrized version of GM-QAOA nearly matches the performance of the version optimized using the layerwise approach while being significantly less demanding, making it a highly effective approach for complex optimization tasks. These findings highlight the potential of GM-QAOA and provide a practical pathway for its implementation on current quantum hardware.
We propose and study Th-QAOA (pronounced Threshold QAOA), a variation of the Quantum Alternating Operator Ansatz (QAOA) that replaces the standard phase separator operator, which encodes the objective function, with a threshold function that returns a value 1 for solutions with an objective value above the threshold and a 0 otherwise. We vary the threshold value to arrive at a quantum optimization algorithm. We focus on a combination with the Grover Mixer operator; the resulting GM-Th-QAOA can be viewed as a generalization of Grover’s quantum search algorithm and its minimum/maximum finding cousin to approximate optimization.Our main findings include: (i) we provide intuitive arguments and show empirically that the optimum parameter values of GM-Th-QAOA (angles and threshold value) can be found with O(log(p) × log M) iterations of the classical outer loop, where p is the number of QAOA rounds and M is an upper bound on the solution value (often the number of vertices or edges in an input graph), thus eliminating the notorious outer-loop parameter finding issue of other QAOA algorithms; (ii) GM-Th-QAOA can be simulated classically with little effort up to 100 qubits through a set of tricks that cut down memory requirements; (iii) somewhat surprisingly, GM-Th-QAOA outperforms non-thresholded GM-QAOA in terms of approximation ratios achieved. This third result holds across a range of optimization problems (MaxCut, Max k-VertexCover, Max k-DensestSubgraph, MaxBisection) and various experimental design parameters, such as different input edge densities and constraint sizes.
The Quantum Alternating Operator Ansatz is a generalization of the Quantum Approximate Optimization Algorithm (QAOA) designed for finding approximate solutions to combinatorial optimization problems with hard constraints. In this paper, we study Maximum k-Vertex Cover under this ansatz due to its modest complexity, while still being more complex than the well studied problems of Max-Cut and Max E3-LIN2. Our approach includes (i) a performance comparison between easy-to-prepare classical states and Dicke states as starting states, (ii) a performance comparison between two XY-Hamiltonian mixing operators: the ring mixer and the complete graph mixer, (iii) an analysis of the distribution of solutions via Monte Carlo sampling, and (iv) the exploration of efficient angle selection strategies. Our results are: (i) Dicke states improve performance compared to easy-to-prepare classical states, (ii) an upper bound on the simulation of the complete graph mixer, (iii) the complete graph mixer improves performance relative to the ring mixer, (iv) numerical results indicating the standard deviation of the distribution of solutions decreases exponentially inp(the number of rounds in the algorithm), requiring an exponential number of random samples to find a better solution in the next round, and (v) a correlation of angle parameters which exhibit high quality solutions that behave similarly to a discretized version of the Quantum Adiabatic Algorithm.