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, alongside 90 external citations. Polarity classification is still indexing.
14
Pith papers citing it
90
external citations · Pith
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.
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
-
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.