Abstract We develop a framework for analyzing layered quantum algorithms such as quantum alternating operator ansätze (QAOA). In the context of combinatorial optimization, our framework relates quantum cost gradient operators, derived from the cost and mixing Hamiltonians, to classical cost difference functions that reflect cost function neighborhood structure. By considering QAOA circuits from the Heisenberg picture, we derive exact general expressions for expectation values as series expansions in the algorithm parameters, cost gradient operators, and cost difference functions. This enables novel interpretability and insight into QAOA behavior in various parameter regimes. For single-level QAOA1 we show the leading-order changes in the output probabilities and cost expectation value explicitly in terms of classical cost differences, for arbitrary cost functions. This demonstrates that, for sufficiently small positive parameters, probability flows from lower to higher cost states on average. By selecting signs of the parameters, we can control the direction of flow. We use these results to derive a classical random algorithm emulating QAOA1 in the small-parameter regime, i.e. that produces bitstring samples with the same probabilities as QAOA1 up to small error. For deeper QAOA p circuits we apply our framework to derive analogous and additional results in several settings. In particular we show QAOA always beats random guessing. We describe how our framework incorporates cost Hamiltonian locality for specific problem classes, including causal cone approaches, and applies to QAOA performance analysis with arbitrary parameters. We illuminate our results with a number of examples including applications to QUBO problems, MaxCut, and variants of MaxSAT. We illustrate the generalization of our framework to QAOA circuits using mixing unitaries beyond the transverse-field mixer through two examples of constrained optimization problems, Max Independent Set and Graph Coloring. We conclude by outlining some of the further applications we envision for the framework.
Abstract We develop a framework for analyzing layered quantum algorithms such as quantum alternating operator ansätze (QAOA). In the context of combinatorial optimization, our framework relates quantum cost gradient operators, derived from the cost and mixing Hamiltonians, to classical cost difference functions that reflect cost function neighborhood structure. By considering QAOA circuits from the Heisenberg picture, we derive exact general expressions for expectation values as series expansions in the algorithm parameters, cost gradient operators, and cost difference functions. This enables novel interpretability and insight into QAOA behavior in various parameter regimes. For single-level QAOA1 we show the leading-order changes in the output probabilities and cost expectation value explicitly in terms of classical cost differences, for arbitrary cost functions. This demonstrates that, for sufficiently small positive parameters, probability flows from lower to higher cost states on average. By selecting signs of the parameters, we can control the direction of flow. We use these results to derive a classical random algorithm emulating QAOA1 in the small-parameter regime, i.e. that produces bitstring samples with the same probabilities as QAOA1 up to small error. For deeper QAOA p circuits we apply our framework to derive analogous and additional results in several settings. In particular we show QAOA always beats random guessing. We describe how our framework incorporates cost Hamiltonian locality for specific problem classes, including causal cone approaches, and applies to QAOA performance analysis with arbitrary parameters. We illuminate our results with a number of examples including applications to QUBO problems, MaxCut, and variants of MaxSAT. We illustrate the generalization of our framework to QAOA circuits using mixing unitaries beyond the transverse-field mixer through two examples of constrained optimization problems, Max Independent Set and Graph Coloring. We conclude by outlining some of the further applications we envision for the framework.
The quantum approximate optimization algorithm (QAOA) is a near-term quantum algorithm aimed at solving combinatorial optimization problems. Since its introduction, various generalizations have emerged, spanning modifications to the initial state, phase unitaries, and mixer unitaries. In this work, we present an analytical study of broad families of QAOA variants. We begin by examining a family of QAOA with product mixers, which includes single-body mixers parametrized by multiple variational angles, and derive exact analytical expressions for the cost expectation on weighted problem graphs in the single-layer ansatz setting. We then analyze a family of QAOA that employs many-body Grover-type mixers, deriving analogous analytical expressions for weighted problem hypergraphs in the setting of arbitrarily many circuit ansatz layers. For both families, we allow individual phase angles for each node and edge (hyperedge) in the problem graph (hypergraph). Our results reveal that, in contrast to product mixers, the Grover mixer is sensitive to contributions from cycles of all lengths in the problem graph, exhibiting a form of non-locality. Our study advances the understanding of QAOA's behavior in general scenarios, providing a foundation for further theoretical exploration.
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 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 generalized approach for solving challenging optimization problems that builds on the alternating structure of the quantum approximate optimization algorithm. Finding high-quality parameters efficiently for QAOA remains a major challenge in practice. In this work, we introduce a classical strategy for parameter setting, suitable for cases in which the number of distinct cost values grows only polynomially with the problem size, such as is common for constraint-satisfaction problems. The crux of our strategy is that we replace the cost function expectation value step of QAOA with a classical model that can be efficiently evaluated classically and has parameters which play an analogous role to the QAOA parameters. This model is based on empirical observations that, in some QAOA states, variable configurations with the same cost have the same amplitudes from step to step. We define this class of states as homogeneous states. For problems with particular symmetries, QAOA states are guaranteed to be homogeneous. More generally, high overlaps between QAOA states and homogeneous states have been empirically observed in a number of settings. Building on this idea, we define a classical homogeneous proxy for QAOA in which this property holds exactly and which yields information describing both states and expectation values. We then classically determine high-quality parameters for this proxy and then use these parameters in QAOA, an approach we label the homogeneous heuristic for parameter setting. We numerically examine this heuristic for MaxCut on unweighted Erdős-Rényi random graphs. For up to three QAOA levels we demonstrate that the heuristic is easily able to find parameters that match approximation ratios corresponding to previously found globally optimized approaches. For levels up to 20 we obtain parameters using our heuristic with approximation ratios monotonically increasing with depth, while a strategy that uses parameter transfer instead fails to converge with comparable classical resources. These results suggest that our heuristic may find good parameters in regimes that are intractable with noisy intermediate-scale quantum devices. Finally, we outline how our heuristic may be applied to wider classes of problems. Published by the American Physical Society 2024
The Quantum Approximate Optimization Algorithm and its generalization to Quantum Alternating Operator Ansatz (QAOA) is a promising approach for applying quantum computers to challenging problems such as combinatorial optimization and computational chemistry. In this paper, we study the underlying mechanisms governing the behavior of QAOA circuits beyond shallow depth in the practically relevant setting of gradually varying unitaries. We use the discrete adiabatic theorem, which complements and generalizes the insights obtained from the continuous-time adiabatic theorem primarily considered in prior work. Our analysis explains some general properties that are conspicuously depicted in the recently introduced QAOA performance diagrams. For parameter sequences derived from continuous schedules (e.g. linear ramps), these diagrams capture the algorithm's performance over different parameter sizes and circuit depths. Surprisingly, they have been observed to be qualitatively similar across different performance metrics and application domains. Our analysis explains this behavior as well as entails some unexpected results, such as connections between the eigenstates of the cost and mixer QAOA Hamiltonians changing based on parameter size and the possibility of reducing circuit depth without sacrificing performance.
Quantum Approximate Optimization Algorithm, further generalized as Quantum Alternating Operator Ansatz (QAOA), is a family of algorithms for combinatorial optimization problems. It is a leading candidate to run on emerging universal quantum computers to gain insight into quantum heuristics. In constrained optimization, penalties are often introduced so that the ground state of the cost Hamiltonian encodes the solution (a standard practice in quantum annealing). An alternative is to choose a mixing Hamiltonian such that the constraint corresponds to a constant of motion and the quantum evolution stays in the feasible subspace. Better performance of the algorithm is speculated due to a much smaller search space. We consider problems with a constant Hamming weight as the constraint. We also compare different methods of generating the generalized W-state, which serves as a natural initial state for the Hamming-weight constraint. Using graph-coloring as an example, we compare the performance of using XY model as a mixer that preserves the Hamming weight with the performance of adding a penalty term in the cost Hamiltonian.