This study numerically investigates the thermal sampling properties of QAOA, the Quantum Alternating Operator Ansatz which was generalized from the original Quantum Approximate Optimization Algorithm. Specifically, the ability of QAOA to sample from the Gibbs distribution, equivalently the Boltzmann distribution, defined by a classical Ising model, specifically a fully connected disordered spin glass (Sherrington-Kirkpatrick) model. We focus on two different QAOA mixers; the standard transverse field X mixer, and the Grover mixer. At a QAOA depth of one we examine, for a single full QAOA parameter search space period, the energy landscape, the Shannon entropy landscape of the QAOA probability distribution, and the tradeoff between Boltzmann distribution sampling temperature and error rate (how close to the true Boltzmann distribution is the QAOA distribution). We find that at very high temperatures one-round Grover mixer QAOA can sample from the Boltzmann distribution more accurately than the standard X mixer QAOA at one round. Both X mixer and Grover mixer depth one QAOA can serve as approximate Boltzmann distribution samplers, and how good this approximation is depends heavily on the QAOA angle choice.
This study numerically investigates the thermal sampling properties of QAOA, the Quantum Alternating Operator Ansatz which was generalized from the original Quantum Approximate Optimization Algorithm. Specifically, the ability of QAOA to sample from the Gibbs distribution, equivalently the Boltzmann distribution, defined by a classical Ising model, specifically a fully connected disordered spin glass (Sherrington-Kirkpatrick) model. We focus on two different QAOA mixers; the standard transverse field X mixer, and the Grover mixer. At a QAOA depth of one we examine, for a single full QAOA parameter search space period, the energy landscape, the Shannon entropy landscape of the QAOA probability distribution, and the tradeoff between Boltzmann distribution sampling temperature and error rate (how close to the true Boltzmann distribution is the QAOA distribution). We find that at very high temperatures one-round Grover mixer QAOA can sample from the Boltzmann distribution more accurately than the standard X mixer QAOA at one round. Both X mixer and Grover mixer depth one QAOA can serve as approximate Boltzmann distribution samplers, and how good this approximation is depends heavily on the QAOA angle choice.
The quantum alternating operator ansatz, a generalization of the quantum approximate optimization algorithm (QAOA), is a quantum algorithm used for approximately solving combinatorial optimization problems. QAOA typically uses the transverse field mixer as the driving Hamiltonian. One of the interesting properties of the transverse field driving Hamiltonian is that it results in nonuniform sampling of degenerate ground states of optimization problems. In this study, we numerically examine the fair sampling properties of the transverse field mixer QAOA, and Grover mixer QAOA (GM-QAOA), which provides theoretical guarantees of fair sampling of degenerate optimal solutions, up to a large enough p such that the mean expectation value converges to an optimal approximation ratio of 1. This comparison is performed with high-quality heuristically computed, but not necessarily optimal, QAOA angles, which give strictly monotonically improving solution quality as p increases. These angles are computed using the Julia based numerical simulation software JuliQAOA. Fair sampling of degenerate ground states is quantified using the Shannon entropy of the ground-state amplitudes distribution. The fair sampling properties are reported on several quantum signature Hamiltonians from previous quantum annealing fair sampling studies. Small random fully connected spin glasses are shown, which exhibit exponential suppression of some degenerate ground states with transverse field mixer QAOA. The transverse field mixer QAOA simulations show that some problem instances clearly saturate the Shannon entropy of 0 with a maximally biased distribution that occurs when the learning converges to an approximation ratio of 1 while other problem instances never deviate from a maximum Shannon entropy (uniform distribution) at any p step.
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 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 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) was originally proposed to find approximate solutions to combinatorial optimization problems on quantum computers. However, the algorithm has also attracted interest for sampling purposes since it was theoretically demonstrated under reasonable complexity assumptions that one layer of the algorithm already engineers a probability distribution beyond what can be simulated by classical computers. In this regard, a recent study has also shown that, in universal Ising models, this global probability distribution resembles pure but thermal-like distributions at a temperature that depends on the internal correlations of the spin model. In this work, through an interferometric interpretation of the algorithm, we extend the theoretical derivation of the amplitudes of the eigenstates and the Boltzmann distributions generated by a single-layer QAOA. We also review the implications of this behavior from practical and fundamental perspectives.