Analytical Framework for Quantum Alternating Operator Ansätze

Abstract

We develop a framework for analyzing layered quantum algorithms such as quantum alternating operator ansätze. 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 QAOAp 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 application to QAOA circuits using mixing unitaries beyond the transverse-field mixer through two examples of constrained optimization, Max Independent Set and Graph Coloring.

Updated to match published version

References in corpus (22)

• A Quantum Approximate Optimization Algorithm
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Counterdiabaticity and the quantum approximate optimization algorithm
• Gradients of parameterized quantum gates using the parameter-shift rule and gate decomposition
• Quantum Algorithms for Fixed Qubit Architectures
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• Quantum approximate optimization is computationally universal
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Feedback-based quantum optimization
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances
• Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs
• Expectation Values from the Single-Layer Quantum Approximate Optimization Algorithm on Ising Problems
• Exploiting Symmetry Reduces the Cost of Training QAOA
• Quantum algorithms with local particle number conservation: noise effects and error correction
• Observations Outside the Light-Cone: Algorithms for Non-Equilibrium and Thermal States
• Bounds on approximating Max $k$XOR with quantum and classical local algorithms
• What do QAOA energies reveal about graphs?
• Optimizing QAOA: Success Probability and Runtime Dependence on Circuit Depth
• A Quantum Approximate Optimization Algorithm for continuous problems
• Noise reduction using past causal cones in variational quantum algorithms

Cited by in corpus (13)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Scaling Quantum Approximate Optimization on Near-term Hardware
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Towards a Linear-Ramp QAOA protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems
• PCA and t-SNE analysis in the study of QAOA entangled and non-entangled mixing operators
• Fermionic Quantum Approximate Optimization Algorithm
• High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
• Mixer-Phaser Ansätze for Quantum Optimization with Hard Constraints
• A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz
• Performance Analysis of Multi-Angle QAOA for p > 1
• Diagrammatic Analysis for Parameterized Quantum Circuits
• Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios
• Interference and Measurement: Changing amplitude phase information to amplitude magnitude information