Analytical framework for quantum alternating operator ansatze

We develop a framework for analyzing layered quantum algorithms such as quantum alternating operator ansatze (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 QAOA(1) 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 QAOA(1) in the small-parameter regime, i.e. that produces bitstring samples with the same probabilities as QAOA(1) 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.

Automated summary

We propose a framework for analyzing layered quantum algorithms and demonstrate its applications in various settings. The framework provides interpretable and insightful analysis of quantum alternating operator ansatze (QAOA) behavior and allows for the derivation of exact expressions for expectation values. Furthermore, we show that for certain parameter regimes, probability flows from lower to higher cost states in the QAOA(1) circuit. We also develop a classical random algorithm that emulates QAOA(1) with small error in the small-parameter regime. In addition, we extend the framework to deeper QAOA(p) circuits and demonstrate its superiority over random guessing in various scenarios.