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.

arXiv commentUpdated to match published version

References in corpus (65)

• Elementary gates for quantum computation
• Barren plateaus in quantum neural network training landscapes
• A Quantum Approximate Optimization Algorithm
• Noise-Induced Barren Plateaus in Variational Quantum Algorithms
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Instantaneous non-local computation of low T-depth quantum circuits
• The Heisenberg Representation of Quantum Computers
• A Theory of Trotter Error
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Quantum advantage with shallow circuits
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• Algorithms for entanglement renormalization
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Finding Exponential Product Formulas of Higher Orders
• $XY$-mixers: analytical and numerical results for QAOA
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• Optimizing Variational Quantum Algorithms using Pontryagin's Minimum Principle
• Reachability Deficits in Quantum Approximate Optimization
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Optimal Protocols in Quantum Annealing and QAOA Problems
• Counterdiabaticity and the quantum approximate optimization algorithm
• MAXCUT QAOA performance guarantees for p >1
• Quantum Annealing for Constrained Optimization
• 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
• On the representation of Boolean and real functions as Hamiltonians for quantum computing
• Training A Quantum Optimizer
• On the Universality of the Quantum Approximate Optimization Algorithm
• Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
• A quantum algorithm to train neural networks using low-depth circuits
• Quantum approximate optimization is computationally universal
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Feedback-based quantum optimization
• MAX 2-SAT with up to 108 qubits
• Classical algorithms for quantum mean values
• Driver Hamiltonians for constrained optimization in quantum annealing
• Characterizing local noise in QAOA circuits
• 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
• A quantum walk assisted approximate algorithm for bounded NP optimisation problems
• Classical and Quantum Bounded Depth Approximation Algorithms
• Low depth mechanisms for quantum optimization
• 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
• An energetic perspective on rapid quenches in quantum annealing
• Quantum Optimization for Maximum Independent Set Using Rydberg Atom Arrays
• Quantum algorithms with local particle number conservation: noise effects and error correction
• Quantum Algorithms for Scientific Computing and Approximate Optimization
• Observations Outside the Light-Cone: Algorithms for Non-Equilibrium and Thermal States
• Bounds on approximating Max $k$XOR with quantum and classical local algorithms
• Performance of QAOA on Typical Instances of Constraint Satisfaction Problems with Bounded Degree
• Quantum Optimization
• 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
• Duality in Quantum Quenches and Classical Approximation Algorithms: Pretty Good or Very Bad
• Noise reduction using past causal cones in variational quantum algorithms
• Higher Jacobi identities

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