A Lean 4 machine-verified proof establishes that depth-p QAOA on the ring of disagrees attains approximation ratio (2p+1)/(2p+2) exactly.
super hub Canonical reference
A Quantum Approximate Optimization Algorithm
Canonical reference. 78% of citing Pith papers cite this work as background.
318
Pith papers citing it
1,803
external citations · Pith
Background
78% of classified citations
abstract
We introduce a quantum algorithm that produces approximate solutions for combinatorial optimization problems. The algorithm depends on a positive integer p and the quality of the approximation improves as p is increased. The quantum circuit that implements the algorithm consists of unitary gates whose locality is at most the locality of the objective function whose optimum is sought. The depth of the circuit grows linearly with p times (at worst) the number of constraints. If p is fixed, that is, independent of the input size, the algorithm makes use of efficient classical preprocessing. If p grows with the input size a different strategy is proposed. We study the algorithm as applied to MaxCut on regular graphs and analyze its performance on 2-regular and 3-regular graphs for fixed p. For p = 1, on 3-regular graphs the quantum algorithm always finds a cut that is at least 0.6924 times the size of the optimal cut.
hub tools
citation-role summary
background 42
method 5
dataset 3
citation-polarity summary
claims ledger
- abstract We introduce a quantum algorithm that produces approximate solutions for combinatorial optimization problems. The algorithm depends on a positive integer p and the quality of the approximation improves as p is increased. The quantum circuit that implements the algorithm consists of unitary gates whose locality is at most the locality of the objective function whose optimum is sought. The depth of the circuit grows linearly with p times (at worst) the number of constraints. If p is fixed, that is, independent of the input size, the algorithm makes use of efficient classical preprocessing. If p
authors
co-cited works
representative citing papers
Forward gradient framework for PQCs unifies SPSA and parameter-shift as limits, introduces QUIVER adaptive optimizer with closed-form measurement allocation, and demonstrates efficient training of 60-qubit circuits on ECG5000 and MNIST.
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.
Hamming Weight Operators and an adaptive QAOA variant confine evolution to feasible states by construction, delivering faster convergence and roughly half the gate count versus penalty methods on finance and physics tasks.
A hybrid lifting theorem unifies classical query-to-communication and quantum approximate-degree lifting to prove c + q² = Ω(max{deg(f), bs(f)} log n) for protocols computing f ∘ G^n.
Efficient learning algorithms for energy estimation imply that stable quantum algorithms cannot prepare low-energy states in systems exhibiting the quantum overlap gap property, as proven for a sparsified quantum p-spin model.
MGT protocols encode the input into a measurement-heralded stabilizer code then apply a logical non-Clifford gate; useful resource states are Clifford-equivalent to diagonal states, and feedforward can often be Pauli.
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.
A hardware-efficient binary-tree ansatz has a closed-form diagonal Fubini–Study metric, enabling metric-aware VQE and time evolution without auxiliary circuits, with linear-in-k pruning for sparse sectors.
The paper formalizes backend identifiability as hypothesis testing, proves anonymity decays at the Chernoff rate under persistent i.i.d. probing, establishes a utility-anonymity trade-off, and demonstrates 87-100% backend classification on real cloud QPUs.
The global transverse-field Ising model with non-monotonic time-dependent transverse field is polynomially equivalent to the gate model of quantum computation.
Analytical expression for dynamical Lie algebra of QAOA-MaxCut on complete graphs with proof that loss variance scales linearly in qubit number.
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.
CLAIMSTAB-QC audits 455 comparative claims from 119 quantum-software papers and identifies a materialization gap where only 8 claims provide enough matched evidence for direct auditing, yielding 2 sustained, 4 unresolved, and 2 reversed outcomes.
A new framework for non-i.i.d. quantum state verification and certification with rigorous bounds on time-averaged expectation values and a spot-checking protocol.
A novel permeability DAG representation is proposed to automate parallelization and memory management in quantum programs by capturing permeability-based commutation properties.
Lie group diffusion models combine a discrete circuit skeleton selector with continuous diffusion on SU(2) ≃ S³ to synthesize hardware-aware quantum circuits, outperforming baselines on three-qubit Hamiltonian simulation targets.
QAOA achieves the conjectured optimal (2p+1)/(2p+2) edge-cut fraction on cycle graphs at depth p by equivalence to Laurent polynomial optimization using quantum signal processing.
A nudged-system optimization method recovers parameters in the Lorenz-63 system from partial noisy observations, with theoretical guarantees on synchronization and identifiability.
MetaMorphQ defines five physics-derived invariants for VQE circuits that enable oracle-free testing with zero false positives and Youden's J of 0.57 on 500 benchmarks versus 0.02 for convergence testing.
A new LLM-guided search method called structured concept evolution discovers competitive lifted-product qLDPC code families including non-abelian constructions.
Presents an end-to-end constraint-aware quantum optimization pipeline using XY-mixer QAOA and Grover Adaptive Search for low-energy defect configurations in doped ZrO2, with QAOA validated against exact enumeration on a high-accuracy QUBO surrogate of MACE energies.
A first-moment operator diagnostic reveals exponentially many inequivalent initialization distributions avoid barren plateaus in variational quantum algorithms, with numerics indicating distinct attained minima.
Presents a continuous-time quantum walk over a product space for CVRP that cuts gate complexity to O(n² log n) and shows faster convergence in simulations up to 8 customers.
citing papers explorer
-
A Machine-Verified Proof of a Quantum-Optimization Conjecture
A Lean 4 machine-verified proof establishes that depth-p QAOA on the ring of disagrees attains approximation ratio (2p+1)/(2p+2) exactly.
-
Adaptive directional gradients for parameterised quantum circuits
Forward gradient framework for PQCs unifies SPSA and parameter-shift as limits, introduces QUIVER adaptive optimizer with closed-form measurement allocation, and demonstrates efficient training of 60-qubit circuits on ECG5000 and MNIST.
-
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.
-
Constraint-Aware Quantum Optimization via Hamming Weight Operators
Hamming Weight Operators and an adaptive QAOA variant confine evolution to feasible states by construction, delivering faster convergence and roughly half the gate count versus penalty methods on finance and physics tasks.
-
A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
A hybrid lifting theorem unifies classical query-to-communication and quantum approximate-degree lifting to prove c + q² = Ω(max{deg(f), bs(f)} log n) for protocols computing f ∘ G^n.
-
Quantum Glassiness From Efficient Learning
Efficient learning algorithms for energy estimation imply that stable quantum algorithms cannot prepare low-energy states in systems exhibiting the quantum overlap gap property, as proven for a sparsified quantum p-spin model.
-
Magic Gate Teleportation: Structure, Useful Resource States, and Simpler Feedforward
MGT protocols encode the input into a measurement-heralded stabilizer code then apply a logical non-Clifford gate; useful resource states are Clifford-equivalent to diagonal states, and feedforward can often be Pauli.
-
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.
-
A hardware-efficient variational ansatz with an exact diagonal metric for real- and imaginary-time evolution and Haar sampling
A hardware-efficient binary-tree ansatz has a closed-form diagonal Fubini–Study metric, enabling metric-aware VQE and time evolution without auxiliary circuits, with linear-in-k pruning for sparse sectors.
-
Routing Anonymity and Identifiability of Noisy Quantum Hardware
The paper formalizes backend identifiability as hypothesis testing, proves anonymity decays at the Chernoff rate under persistent i.i.d. probing, establishes a utility-anonymity trade-off, and demonstrates 87-100% backend classification on real cloud QPUs.
-
Polynomial equivalence of the global transverse-field Ising model and the gate model of quantum computation
The global transverse-field Ising model with non-monotonic time-dependent transverse field is polynomially equivalent to the gate model of quantum computation.
-
The Dynamical Lie Algebra of QAOA-MaxCut on the Complete Graph
Analytical expression for dynamical Lie algebra of QAOA-MaxCut on complete graphs with proof that loss variance scales linearly in qubit number.
-
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.
-
Auditing Empirical Comparisons in Quantum Software
CLAIMSTAB-QC audits 455 comparative claims from 119 quantum-software papers and identifies a materialization gap where only 8 claims provide enough matched evidence for direct auditing, yielding 2 sustained, 4 unresolved, and 2 reversed outcomes.
-
Certifying quantum states without independence assumptions
A new framework for non-i.i.d. quantum state verification and certification with rigorous bounds on time-averaged expectation values and a spot-checking protocol.
-
Automatic quantum function parallelization and memory management in Qrisp
A novel permeability DAG representation is proposed to automate parallelization and memory management in quantum programs by capturing permeability-based commutation properties.
-
Lie Group Diffusion Models for Hardware-Aware Quantum Circuit Synthesis
Lie group diffusion models combine a discrete circuit skeleton selector with continuous diffusion on SU(2) ≃ S³ to synthesize hardware-aware quantum circuits, outperforming baselines on three-qubit Hamiltonian simulation targets.
-
The QAOA on the ring of disagrees
QAOA achieves the conjectured optimal (2p+1)/(2p+2) edge-cut fraction on cycle graphs at depth p by equivalence to Laurent polynomial optimization using quantum signal processing.
-
A Data-Assimilation-Augmented Optimization Framework for Parameter Estimation in Dynamical Systems
A nudged-system optimization method recovers parameters in the Lorenz-63 system from partial noisy observations, with theoretical guarantees on synchronization and identifiability.
-
MetaMorphQ: Physics-Based Metamorphic Testing of Variational Quantum Circuits
MetaMorphQ defines five physics-derived invariants for VQE circuits that enable oracle-free testing with zero false positives and Youden's J of 0.57 on 500 benchmarks versus 0.02 for convergence testing.
-
Large-Language-Model Discovery of Quantum LDPC Codes through Structured Concept Evolution
A new LLM-guided search method called structured concept evolution discovers competitive lifted-product qLDPC code families including non-abelian constructions.
-
Constraint-Aware Quantum Optimization of Defect Configurations in Doped ZrO2: XY-Mixer QAOA and Grover Adaptive Search
Presents an end-to-end constraint-aware quantum optimization pipeline using XY-mixer QAOA and Grover Adaptive Search for low-energy defect configurations in doped ZrO2, with QAOA validated against exact enumeration on a high-accuracy QUBO surrogate of MACE energies.
-
Exponentially many initializations to avoid barren plateaus
A first-moment operator diagnostic reveals exponentially many inequivalent initialization distributions avoid barren plateaus in variational quantum algorithms, with numerics indicating distinct attained minima.
-
Quantum walk-based optimisation for capacitated vehicle routing with homogeneous and heterogeneous fleets
Presents a continuous-time quantum walk over a product space for CVRP that cuts gate complexity to O(n² log n) and shows faster convergence in simulations up to 8 customers.
-
Variational Approach for Uniform Quantum Permutation Generators
Explicit controlled-SWAP variational circuits generate exact uniform permutation distributions on linear nearest-neighbor topologies in O(n) depth, while Beneš-like architectures cannot produce uniform distributions for any parameter choice.
-
High Precision Qubit-Efficient Variational Continuous Optimization via Amplitude Estimation
Proposes encoding continuous variables in single-qubit amplitudes with amplitude estimation readout for qubit-efficient variational continuous optimization on standard qubit hardware.
-
Pure and mixed Dicke state ansatz for equality and inequality constraints in variational quantum eigensolver
A mixed Dicke state ansatz is introduced that encodes Hamming weight equality and inequality constraints directly into the VQE circuit to preserve feasibility without penalty terms.
-
Penalty-free quantum optimization applied to lattice protein folding
A QAOA variant without quadratic penalties, using independent sets in a conflict graph, is applied to lattice protein folding and validated on proteins up to length 14 via simulation and heuristic search.
-
Basis-Adaptive Sparse-State Simulation of Quantum Circuits
BASS adapts qubit bases via single-qubit RDM eigenbases to cluster amplitudes for truncation, yielding up to order-of-magnitude state-overlap gains versus fixed-basis sparse simulation on disordered Ising circuits.
-
Classical State Preparation for Variational Quantum Algorithms via Reinforcement Learning
CRiSP uses neural-guided MCTS and curriculum learning to insert Clifford prefixes before parameterized rotations in VQAs, yielding mean 3.17x and max 45x gains in energy accuracy on 22-qubit QAOA benchmarks versus prior Clifford initializers.
-
A sharp interaction-degree threshold for simulating QAOA
There is a sharp threshold at interaction degree 3 where classical sampling from depth-1 QAOA becomes hard enough to collapse the polynomial hierarchy, contrasting with efficient simulation at degree 2 for logarithmic depth.
-
Truncated-Binary Encoding: Spectral Degree Reduction of Combinatorial Optimization Problems for Quantum Hardware
Truncated-binary encoding approximates high-cardinality CFN problems as low-degree HUBO Hamiltonians with an L^∞ error bound, conditions preserving the global minimum, and a smoothness-based criterion for choosing the cutoff.
-
Bias Analysis and Regularization of Sequential Minimal Optimization in Variational Quantum Eigensolvers
Bias in SMO-VQE can be estimated without extra measurements; a regularization method that mimics error accumulation while preserving unbiased estimates improves performance across system sizes and Hamiltonians.
-
QLAM: A Quantum Long-Attention Memory Approach to Long-Sequence Token Modeling
QLAM extends state-space models with quantum superposition in the hidden state for linear-time long-sequence modeling and reports consistent gains over RNN and transformer baselines on sequential image tasks.
-
QAP-Router: Tackling Qubit Routing as Dynamic Quadratic Assignment with Reinforcement Learning
QAP-Router models qubit routing as dynamic QAP and applies RL with a solution-aware Transformer to cut CNOT counts by 12-30% versus industry compilers on real circuit benchmarks.
-
TuniQ: Autotuning Compilation Passes for Quantum Workloads at Scale for Effectiveness and Efficiency
TuniQ uses RL with a dual-encoder, shaped rewards, and action masking to autotune quantum compilation passes, improving fidelity and speed over Qiskit while generalizing across backends and scaling to large circuits.
-
Multivariate Decoded Quantum Interferometry for Weighted Optimization
Multivariate DQI uses N-variable polynomials for weighted Max-LINSAT, derives closed-form asymptotics for expectation and concentration, provides a single-decoder preparation circuit, and shows outperformance over weighted Prange for some OPI cases while extending to Hamiltonian DQI.
-
Per-Phase Fidelity Attribution for Quantum Compilers using HBR Decomposition
HBR decomposition quantifies per-phase fidelity loss in quantum compilers, revealing that routing causes up to 60% loss in search circuits while synthesis dominates Hamiltonian simulation, and correctly predicts SDK rankings on both simulation and real hardware.
-
Breaking QAOA's Fixed Target Hamiltonian Barrier: A Fully Connected Quantum Boltzmann Machine via Bilevel Optimization
A bilevel optimization method turns QAOA into a fully connected QBM that achieves 0.9559 target state probability noiseless and retains top probability under realistic noise levels.
-
The finite-shot help-harm boundary of zero-noise extrapolation
Zero-noise extrapolation has a finite-shot help-harm boundary below which it increases local mean-squared error due to variance penalties outweighing bias reduction.
-
Adversarial Effects on Expressibility and Trainability in Distributed Variational Quantum Algorithms
Adversaries perturbing shared entanglement in distributed VQAs can manipulate a new Kraus expressibility metric to keep gradients large but steer training to incorrect solutions.
-
Constraint Preserving XY-Mixers under Trotterized Adiabatic Evolution
Trotter errors in XY-mixers scale with individual constraint size and locality rather than total problem size, making them superior to X-mixers for local constraints but inferior for global ones, with a new mixer proposed for TSP-like constraints.
-
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.
-
Formulating Subgroup Discovery as a Quantum Optimization Problem for Network Security
Subgroup discovery is encoded as a QUBO and solved via QAOA on NISQ hardware to find interpretable feature groups that distinguish attack traffic, with results competitive to beam search and better at some multi-feature interactions.
-
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.
-
Hybrid Path-Sums for Hybrid Quantum Programs
Hybrid Path-Sums offer a new symbolic framework with rewriting rules and assertions to represent, simplify, and verify properties of hybrid quantum-classical programs.
-
Exhaustive and feasible parametrisation with applications to the travelling salesperson problem
Exhaustively parametrised feasibility-respecting quantum circuits can reach every feasible solution to problems like TSP with certainty using fixed parameters by leveraging group actions and generating sequences.
-
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.
-
Constrained Quantum Optimization meets Model Reduction
A projection-based model reduction enables exponential state-space reduction for constrained quantum optimization applied to random 3-SAT and agent coordination on graphs.