Recognition: unknown
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 6 Pith papers
-
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.
-
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...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.