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.
hub
For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances
25 Pith papers cite this work, alongside 50 external citations. Polarity classification is still indexing.
25
Pith papers citing it
50
external citations · Pith
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.
hub tools
citation-role summary
background 3
citation-polarity summary
roles
background 2representative citing papers
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.
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.
Classical RNNs trained on small instances provide parameter initializations for QAOA and VQE that reduce total optimization iterations and generalize across problem sizes.
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.
Analytical reweighting rules for QAOA parameters on hypergraphs improve performance by adjusting mixing terms beyond previous graph-based methods.
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.
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.
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.
Adding non-unitary gadgets to variational quantum circuits can create an illusion of trainability — the cost varies, but most parameters remain exponentially hard to train.
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).
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.
Iterative orthogonal-basis interpolation constructs high-quality QAOA parameter schedules for depths exceeding 1000 layers, outperforming prior methods on SK, portfolio, and LABS benchmarks.
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 of graphs up to 77 qubits.
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 dimensions.
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.
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 energy guarantees.
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.
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 to 156 qubits, with hardware runs confirming gains up to p=10.
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.
Noise characteristics of superconducting qubits bound the optimal QAOA depth, contrary to the expectation that higher depth always improves performance.
Combining a truncated classical surrogate, angle pruning, and exact fine-tuning cuts the number of active angles and estimated fine-tuning cost of ma-QAOA on small spin-glass and Max-Cut instances while preserving near-optimal approximation ratios.
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.
The paper benchmarks approximation techniques and transfer learning for setting QAOA angles at utility scale and extracts operational guidance from hardware-validated results.
citing papers explorer
-
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.
-
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.
-
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.
-
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.
-
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
Adding non-unitary gadgets to variational quantum circuits can create an illusion of trainability — the cost varies, but most parameters remain exponentially hard to train.
-
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.
-
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.
-
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 of graphs up to 77 qubits.
-
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 dimensions.
-
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.
-
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 energy guarantees.
-
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 to 156 qubits, with hardware runs confirming gains up to p=10.
-
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.
-
SAFE ma-QAOA: Surrogate-Assisted and Fine-Tuning Enhanced Multi-Angle QAOA with Parameter Distillation
Combining a truncated classical surrogate, angle pruning, and exact fine-tuning cuts the number of active angles and estimated fine-tuning cost of ma-QAOA on small spin-glass and Max-Cut instances while preserving near-optimal approximation ratios.
-
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.
-
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.