Source-linked AI summary
For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances
Fernando G. S. L. Brandao, Michael Broughton, Edward Farhi, Sam Gutmann, Hartmut Neven
TL;DR
The paper addresses the need for strategies to choose QAOA parameters for combinatorial search problems. It shows that, for fixed parameters, typical instances share nearly the same objective-function landscape, and that parameters performing well on smaller instances can perform well on larger ones.
Problem
QAOA requires strategies for picking parameters that optimize performance.
Method
The paper studies QAOA objective functions on randomly generated combinatorial-search instances, including low-depth circuits and large 3-regular MaxCut graphs.
Results
For fixed γ and β, the objective function has nearly the same value across typical generated instances, while parameters yielding good performance at smaller sizes also perform well at 20 and 24 bits.
Takeaways & Limitations
These findings motivate QAOA strategies that can reduce or eliminate outer-loop optimization and amortize parameter selection across instances.
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
QAOA applies shallow parameterized quantum circuits to combinatorial optimization, but choosing parameters that optimize performance remains challenging. The paper studies random instance distributions and shows that the objective-function landscape is nearly instance independent, enabling parameters learned on one instance to transfer to others.
- I. INTRODUCTION: At shallow depth, QAOA performance guarantees beat random guessing but do not surpass the best classical algorithms discussed.Whether higher-depth QAOA outperforms classical algorithms remains an open question requiring analysis, simulation, and experiments on quantum hardware.
- I. INTRODUCTION: QAOA uses shallow-depth quantum circuits whose parameters must be chosen to optimize performance on combinatorial search problems.The algorithm alternates cost-dependent and mixing operators, with separate parameters for each layer.
- I. INTRODUCTION: For random instances, the objective-function landscape is nearly independent of the chosen instance.The paper focuses on MaxCut instances drawn uniformly from all 3-regular graphs and states that the argument generalizes beyond this example.
- I. INTRODUCTION: Parameters optimized on one instance can yield good cost-function values on other randomly chosen instances.The paper presents this transfer as a way to amortize the cost of parameter selection across instances.
- I. INTRODUCTION: The paper asks how the QAOA parameter landscape varies across instances drawn from a fixed distribution.The landscape consists of objective-function values over the 2p control parameters for a fixed instance and circuit depth.
II. FIXED p WITH n LARGE
For fixed p and large n, QAOA objective values concentrate across typical graph instances because the relevant local subgraph frequencies concentrate. This holds for several sparse graph distributions and extends to related combinatorial problems under bounded-occurrence conditions.
- 3-regular graphs: On random 3-regular graphs, neighborhood fractions concentrate, with tree-like neighborhoods dominating as n grows.The dominant tree fraction approaches 1, while the other two fractions are of order 1/n.
- 3-regular graphs: Regardless of fixed parameter values, typical 3-regular graphs have objective functions agreeing up to order 1/n.The result is obtained by expressing the total objective as a sum over local edge environments.
- Local structure: For fixed p, each edge’s QAOA contribution depends only on a neighborhood extending at most p graph steps.The number of relevant subgraph types is therefore fixed independently of the number of bits.
- Other graph distributions: For fixed p, objective values also concentrate for graphs sampled with edge probability 3/(n −1), despite isolated vertices and disconnected components.Here multiple tree types occur, producing fluctuations in tree-type counts while preserving concentration.
- Scope and limitation: The argument extends to other combinatorial search problems when each variable appears in a bounded or slowly growing number of clauses.If relevant subgraphs cover the instance multiple times, the fixed-p arguments no longer apply.
III. NUMERICS THAT SHOW CONCENTRATION
Numerical experiments show that fixed QAOA parameters produce nearly identical objective values across random 3-regular graph instances. This concentration persists as circuit depth increases.
- Experimental setup: The simulations used 20-node 3-regular graphs with 30 edges and, in some regimes, restricted every graph to MaxCut value 26.This restriction makes the largest possible cost-function value identical across the sampled graphs.
- Experimental setup: Randomly selected parameters were expected to yield objective values near 15, while other fixed parameters were selected to produce lower or higher values.The three parameter regimes were designed to test concentration away from a random-state baseline.
- Numerical evidence: The numerical concentration remained evident as p increased from 2 to 7.Table 1 reports sample means and standard deviations for the 25 graphs.
IV. HIGHER p
For fixed parameters, concentration persists at higher circuit depth: numerical results show nearly instance-independent objective values, while weak correlations support a Law of Large Numbers explanation.
- Higher-depth concentration: At p = 7, the objective function still concentrates despite leaving the fixed-p, large-n regime.The authors therefore seek an explanation beyond the earlier low-depth argument.
- Higher-depth concentration: The objective function is a sum of bounded clause terms, so weak inter-term correlations can produce concentration as the number of clauses grows.Under the Law of Large Numbers, independent terms have fluctuations controlled by the standard deviation of the sum.
- Correlation analysis: For MaxCut on 3-regular graphs, individual clause terms are correlated because edges belong to the same graph.Random edge relabeling makes the covariance structure comparable across pairs of terms.
- Correlation analysis: Near-zero observed correlation coefficients provide evidence that the terms contributing to F have only tiny correlations.The simulations used random 3-regular graphs and several fixed parameter sets at p = 8.
- Correlation analysis: The correlation coefficient is small across all tested parameter sets, including low, medium, high, and random choices.The authors expect correlations to decrease on larger graphs as edges become farther apart.
V. FROM SMALL TO LARGE INSTANCES
Parameters that perform well on small instances also perform well on larger ones in the reported simulations, although fixed-depth parameters cannot capture arbitrarily large-graph structure.
- Transfer across instance sizes: Parameters producing high objective values at low bit number also produce high values on larger instances when p is fixed.This cross-size transfer is reported as a key finding of the section.
- Numerical example: An angle set found at 10 bits with p = 8 achieved an approximation ratio of 0.984.The parameters were obtained through 200 random optimization restarts on a laptop.
- Numerical example: The reported 24-qubit performance was high and required no searching at 24 qubits.This illustrates transfer of parameters from a smaller instance to larger instances.
- Scope boundary: Fixed p = 8 parameters cannot work well on arbitrarily large graphs because their local neighborhoods do not cover large loops.For very large 3-regular graphs, QAOA cannot distinguish large even-length loops from large odd-length loops.
VI. FUTURE OUTLOOK
The paper argues that fixed-parameter objective landscapes concentrate across typical instances and that parameter transfer can reduce quantum optimization costs. It proposes staged scaling strategies while retaining explicit distribution and locality assumptions.
- Main finding: For fixed γ and β, the objective function has the same value on typical instances from a reasonable distribution.This is presented as the paper’s main finding and applies to the objective landscape rather than only one optimum.
- Assumptions and evidence: The concentration argument for growing p relies on the Law of Large Numbers and an assumption that individual objective-function terms are not strongly correlated.The authors state that numerical experiments support these arguments.
- Parameter reuse: Good parameters found for one typical instance can be reused on other typical instances, reducing or eliminating blind outer-loop searches beyond the first instance.A narrow local search may still be used when further per-instance improvement is worthwhile.
- Leapfrogging strategy: Numerical simulations found good parameters at 10 bits that also performed well at 20 and 24 bits without additional optimization.The authors use this result to motivate transferring parameters across increasing instance sizes.
- Leapfrogging strategy: The proposed leapfrogging strategy scales parameters from smaller to larger instances, with optional local refinement at each stage.The example progresses from 20 to 50 to 100 qubits while carrying forward the parameter set.
- Future outlook: The strategies are intended to reduce quantum-computer function calls relative to direct variational approaches and support experiments beyond classical simulation.The paper states that this may shorten the path to testing QAOA on near-term devices.