A Lean 4 machine-verified proof establishes that depth-p QAOA on the ring of disagrees attains approximation ratio (2p+1)/(2p+2) exactly.
hub
The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case, April 2020
14 Pith papers cite this work. Polarity classification is still indexing.
14
Pith papers citing it
abstract
The Quantum Approximate Optimization Algorithm can naturally be applied to combinatorial search problems on graphs. The quantum circuit has p applications of a unitary operator that respects the locality of the graph. On a graph with bounded degree, with p small enough, measurements of distant qubits in the state output by the QAOA give uncorrelated results. We focus on finding big independent sets in random graphs with dn/2 edges keeping d fixed and n large. Using the Overlap Gap Property of almost optimal independent sets in random graphs, and the locality of the QAOA, we are able to show that if p is less than a d-dependent constant times log n, the QAOA cannot do better than finding an independent set of size .854 times the optimal for d large. Because the logarithm is slowly growing, even at one million qubits we can only show that the algorithm is blocked if p is in single digits. At higher p the algorithm "sees" the whole graph and we have no indication that performance is limited.
hub tools
citation-role summary
background 2
citation-polarity summary
roles
background 1polarities
support 1representative citing papers
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.
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.
Ancilla-assisted multi-seed superposition plus excitation-preserving VQE and classical post-processing recovers exact MIS on 64-, 99-, and 180-node graphs, with partial hardware transfer.
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).
Global Bradley-Terry rankings of LLMs are misleading due to structured heterogeneity in user preferences, and small (λ, ν)-portfolios recover coherent subpopulations that cover over 96% of votes with just five rankings.
Compositional quantum circuits with symmetry-induced invariant losses produce trainable equivariant quantum GNNs that generalize on max-clique problems and improve hybrid recursive search accuracy and scalability.
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.
QUACOD decomposes drone-scheduling QUBOs into small blocks solved by VQE and reports up to ~5x more drones and ~35x more routes than QUADRO, though the largest claim is overstated.
Generic QAOA's claimed exponential feasibility bottleneck on permutation-constrained problems is not proven; the main bound has a 2^N normalization error and is false as stated.
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.
Classical solvers solve random Ising models on heavy-hex graphs efficiently, with Gurobi showing linear or weakly quadratic scaling up to 100k variables and simulated annealing showing exponential time-to-solution without cubic terms.
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.
-
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.
-
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 Variational Approaches to the Maximum Independent Set Problem at Utility Scale
Ancilla-assisted multi-seed superposition plus excitation-preserving VQE and classical post-processing recovers exact MIS on 64-, 99-, and 180-node graphs, with partial hardware transfer.
-
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).
-
Why Global LLM Leaderboards Are Misleading: Small Portfolios for Heterogeneous Supervised ML
Global Bradley-Terry rankings of LLMs are misleading due to structured heterogeneity in user preferences, and small (λ, ν)-portfolios recover coherent subpopulations that cover over 96% of votes with just five rankings.
-
Compositional Quantum Heuristics for Max-Clique Detection
Compositional quantum circuits with symmetry-induced invariant losses produce trainable equivariant quantum GNNs that generalize on max-clique problems and improve hybrid recursive search accuracy and scalability.
-
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.
-
QUACOD: Quantum Optimization via Coordinate Descent for Scalable Drone Scheduling
QUACOD decomposes drone-scheduling QUBOs into small blocks solved by VQE and reports up to ~5x more drones and ~35x more routes than QUADRO, though the largest claim is overstated.
-
Fundamental Limitations of QAOA on Constrained Problems and a Route to Exponential Enhancement
Generic QAOA's claimed exponential feasibility bottleneck on permutation-constrained problems is not proven; the main bound has a 2^N normalization error and is false as stated.
-
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.
-
Classical Combinatorial Optimization Scaling for Random Ising Models on 2D Heavy-Hex Graphs
Classical solvers solve random Ising models on heavy-hex graphs efficiently, with Gurobi showing linear or weakly quadratic scaling up to 100k variables and simulated annealing showing exponential time-to-solution without cubic terms.
- Promise of Graph Sparsification and Decomposition for Noise Reduction in QAOA: Analysis for Trapped-Ion Compilations