For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances
read the original abstract
The Quantum Approximate Optimization Algorithm, QAOA, uses a shallow depth quantum circuit to produce a parameter dependent state. For a given combinatorial optimization problem instance, the quantum expectation of the associated cost function is the parameter dependent objective function of the QAOA. We demonstrate that if the parameters are fixed and the instance comes from a reasonable distribution then the objective function value is concentrated in the sense that typical instances have (nearly) the same value of the objective function. This applies not just for optimal parameters as the whole landscape is instance independent. We can prove this is true for low depth quantum circuits for instances of MaxCut on large 3-regular graphs. Our results generalize beyond this example. We support the arguments with numerical examples that show remarkable concentration. For higher depth circuits the numerics also show concentration and we argue for this using the Law of Large Numbers. We also observe by simulation that if we find parameters which result in good performance at say 10 bits these same parameters result in good performance at say 24 bits. These findings suggest ways to run the QAOA that reduce or eliminate the use of the outer loop optimization and may allow us to find good solutions with fewer calls to the quantum computer.
This paper has not been read by Pith yet.
Forward citations
Cited by 18 Pith papers
-
Reductions of QAOA Induced by Classical Symmetries: Theoretical Insights and Practical Implications
Symmetry reductions in QAOA for MaxCut can collapse DLA dimensions from exponential to quadratic depending on the fixed variable, with graph embeddings ensuring expressivity and improved trainability.
-
Q3SAT-GPT: A Generative Model for Discovering Quantum Circuits for the 3-SAT Problem
A generative model learns patterns from adaptive QAOA circuits to generate high-quality shallow quantum circuits for Max-E3-SAT that scale better than variational baselines.
-
QAOA Parameter Transfer for Hypergraphs
Analytical reweighting rules for QAOA parameters on hypergraphs improve performance by adjusting mixing terms beyond previous graph-based methods.
-
Graph-Conditioned Meta-Optimizer for QAOA Parameter Generation on Multiple Problem Classes
A graph-conditioned meta-optimizer learns QAOA parameter trajectories from one problem class and transfers them to others, yielding better initializations than standard methods in an empirical study of 64 settings.
-
Query-Efficient Quantum Approximate Optimization via Graph-Conditioned Trust Regions
A GNN predicts Gaussians over QAOA parameters to create graph-conditioned trust regions that reduce circuit evaluations for MaxCut from 85-343 down to 45 while keeping approximation ratios within 3 points of heuristics.
-
Learning to learn with quantum neural networks via classical neural networks
Classical RNNs trained on small instances provide parameter initializations for QAOA and VQE that reduce total optimization iterations and generalize across problem sizes.
-
Mechanism of Efficacy in QAOA for Random k-SAT: From Adiabatic Manifold to Sublinear Parameter Optimization
QAOA for random k-SAT derives efficacy from an adiabatic manifold that supports rigorous performance guarantees at depth Θ(n²) and sublinear parameter optimization via SAMP at depth O(n).
-
Efficient Fourier-Based Linear Combination of Unitaries and Applications in Quantum Optimization
Fourier-based LCU decomposes diagonal and non-diagonal unitaries into hardware-friendly forms for QAOA-style optimization, trading circuit depth for sampling overhead with performance guarantees.
-
SCALAR: A Neurosymbolic Framework for Automated Conjecture and Reasoning in Quantum Circuit Analysis
SCALAR generates conjectures linking optimal QAOA parameters to graph invariants, recovers known periodicity and parameter-transfer properties, and identifies correlations with optimization landscapes across thousands...
-
Tensor network surrogate models for variational quantum computation
Tensor network simulations act as effective surrogate models for training QAOA on large 2D lattices, overcoming limits of parameter transfer from small instances and remaining classically feasible with moderate bond d...
-
Iterative Interpolation Schedules for Quantum Approximate Optimization Algorithm
Iterative orthogonal-basis interpolation constructs high-quality QAOA parameter schedules for depths exceeding 1000 layers, outperforming prior methods on SK, portfolio, and LABS benchmarks.
-
Going off Pattern? QAOA Parameter Heuristics and Potentials of Parsimony
Numerical experiments on QAOA show optimal parameters often break expected patterns, performance becomes less parameter-sensitive with depth, and component-wise iterative fixing performs competitively or better at low depth.
-
Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms
Systematic numerical study of QAOA parameter transfer on heavy-hex Ising models with local cubic terms shows transferred angles from small instances yield improving expectation values up to 49 layers on instances up t...
-
Optimisation-Free Recursive QAOA for the Binary Paint Shop Problem
Optimization-free Recursive QAOA solves the Binary Paint Shop Problem near-optimally with reduced quantum resources and robustness to parameter choice compared to standard QAOA.
-
Analysis of Quantum Approximate Optimization Algorithm under Realistic Noise in Superconducting Qubits
Noise characteristics of superconducting qubits bound the optimal QAOA depth, contrary to the expectation that higher depth always improves performance.
-
Mind the gaps: The fraught road to quantum advantage
The authors identify four transitions needed to reach fault-tolerant application-scale quantum computing from current NISQ devices.
-
Light Cone Cancellation for Variational Quantum Eigensolver in Solving Noisy Max-Cut
Light cone cancellation decomposes VQE circuits for Max-Cut into smaller subcircuits, yielding higher approximation ratios on simulated noisy backends up to 100 qubits compared to standard VQE.
-
Mind the gaps: The fraught road to quantum advantage
The paper identifies four key hurdles in the transition from NISQ to FASQ quantum computers and argues that targeting them will accelerate progress toward useful quantum advantage.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.