REVIEW 23 cited by
For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
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.
Forward citations
Cited by 23 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.
-
Transferred QAOA Parameters Remember the Penalty Scale: A $\lambda$-Resonance Law for Constrained Quantum Optimization
At fixed QAOA angles, feasible probability is a trigonometric polynomial in the penalty weight λ whose frequencies lie on the lattice generated by the trained γ's, so transfer feasibility is a resonance peaked at the ...
-
Weak Poincar\'e Inequalities via Approximate Stochastic Localization: Application to Sampling the Sherrington-Kirkpatrick Model
Approximate stochastic localization plus conductance transfers yield a weak Poincaré inequality for the SK model at β < 1/2, enabling efficient Glauber sampling from a warm start.
-
Quantum machine learning models for graphs
Characterizes constituents of n-qubit graph quantum ML models and supplies a toolbox enabling integration with classical models, generalization of prior GQML approaches, and classical pre-training.
-
SAFE ma-QAOA: Surrogate-Assisted and Fine-Tuning Enhanced Multi-Angle QAOA with Parameter Distillation
SAFE ma-QAOA achieves 64.3% fewer active parameters and 94.5% lower estimated QPU workload via surrogate pre-training and parameter distillation on Sherrington-Kirkpatrick, 2D spin glass, and Max-Cut instances.
-
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.
-
Measurements Number Scaling in the Quantum Approximate Optimization Algorithm for MaxCut: A Statistical Analysis
Under extensivity and local-structure assumptions, the shot budget for fixed relative QAOA MaxCut performance scales as 1/m while SGD iterations stay size-independent.
-
Quantum-Informed Portfolio Selection: An End-to-End Pipeline Validated on Trapped-Ion Hardware with Real Market Data
qReduMIS, using QAOA frozen-node signals plus classical reductions, solves real market MIS portfolio instances up to 225 assets on Helios with far better success and TTS scaling than standalone QAOA.
-
Feasibility-driven QAOA with penalty scheduling
Introduces Λ-lr-QAOA and piecewise-ramp QAOA that promote penalty schedules to variational parameters and use a feasibility-driven loss on budget-constrained MWIS satellite planning instances.
-
Challenges in Barren Plateau Mitigation with Dynamic Parameterized Quantum Circuits
Dynamic parameterized quantum circuits still leave a significant fraction of parameters untrainable despite cost anti-concentration, implying BP mitigation via DPQCs is at least as hard as designing BP-free unitaries.
-
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.
-
Landscape-Similarity-Guided Optimization in Divide-and-Conquer QAOA
DO-QAOA shows that the 2^m subproblems in frozen-qubit divide-and-conquer QAOA share near-identical variational landscapes, so training one representative and transferring its parameters cuts training cost from expone...
-
Diagnosing Simulation and Hardware Barriers to Cross-Size Transfer in Equivariant Quantum Reinforcement Learning
Abstract claims zero-shot 5-to-10-city EQC transfer beats target-size training only in exact simulation, degrading by 31.3% under sampling noise and 45.3% on hardware; the supplied body omits these experiments.
-
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.
-
Hamiltonian-Guided Leverage Embedding: Robust Subspace Compression for Efficient QAOA Parameter Estimation
HGLE encodes QAOA samples into a weighted Ising matrix and applies leverage-score row sampling to preserve the dominant subspace, enabling cheaper trust-region optimization of QAOA parameters with formal rank and ener...
-
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 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.
-
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.
-
Setting angles in quantum approximate optimization at utility-scale
The paper benchmarks approximation techniques and transfer learning for setting QAOA angles at utility scale and extracts operational guidance from hardware-validated results.
Discussion (0). Sign in to comment.