Analytical framework for Quantum Alternating Operator Ansätze

We develop a framework for analyzing quantum alternating operator ansätze circuits, in particular the quantum approximate optimization algorithm (QAOA). 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. For QAOA we show exact series expansions in the algorithm parameters and cost gradient operators, which enable novel insight and analysis in different parameter regimes. For single-layer QAOA-1 we show that leading-order changes in the solution probabilities and cost expectation value are determined by cost differences; for sufficiently small positive parameters probability provably flows from lower to higher cost states on average. We further show a classical random algorithm emulating QAOA-1 in the small-parameter regime, i.e., that samples with the same probabilities up to small error. Our results are general and apply under minimal cost function assumptions. For deeper QAOA-p circuits we derive analogous results in several settings. We outline applications of our framework to performance analysis, parameter setting, and design of more effective QAOA mixing operators.