Small-parameter and operator series approaches for quantum approximate optimization*

We show a calculus for analyzing algorithms based on quantum alternating operator ansatze, in particular the quantum approximate optimization algorithm (QAOA). Our framework relates cost gradient operators, derived from the cost and mixing Hamiltonians, to classical cost difference functions that reflect cost function structure. For QAOA we show an exact series expansion in the algorithm parameters and cost gradient operators. This enables analysis in different parameter regimes which yields novel insights. In the small-parameter regime, for single-layer QAOA-1 the leading-order change in solution probability is determined by cost differences; for sufficiently small parameters probability provably flows from lower to higher cost states on average (or vice versa via parameter selection). On the other hand, we derive a classical random algorithm which emulates QAOA-1 in the same small-parameter regime, i.e. outputs samples with the same probabilities up to small error. Our results apply generally under minimal cost function assumptions. For deeper QAOA-p circuits we derive analogous results in several settings. We discuss applications to performance, parameter setting, and design of more effective QAOA mixing operators.