REVIEW 16 cited by
The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
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
The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
read the original 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.
Forward citations
Cited by 16 Pith papers
-
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.
-
Fundamental Limitations of QAOA on Constrained Problems and a Route to Exponential Enhancement
Standard QAOA faces an intrinsic feasibility bottleneck on permutation problems that CE QAOA overcomes with an exponential gain in feasible probability for sublinear-to-linear depths under mild hypergraph growth.
-
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-sp...
-
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
Variational quantum methods with spectral preprocessing, CVaR optimization, and ancilla-assisted superposition solve maximum independent set to optimality on graphs up to 180 vertices, claimed as the largest such gate...
-
QUACOD: Quantum Optimization via Coordinate Descent for Scalable Drone Scheduling
QUACOD decomposes drone scheduling into quantum-solvable subproblems via coordinate descent, outperforming prior quantum methods in completion time while scaling to 5x more drones and 35x more routes.
-
Promise of Graph Sparsification and Decomposition for Noise Reduction in QAOA: Analysis for Trapped-Ion Compilations
Graph sparsification and decomposition reduce worst-case H_Ising pulses from O(n²) to O(n log(n/ε)) and Pauli-X flips from O(n²) to O(n log(n/ε)/ε²) for (1-ε) Max-Cut approximation in trapped-ion QAOA compilations.
-
Quantum Variational Approaches to the Maximum Independent Set Problem at Utility Scale
Variational quantum methods with spectral reordering, sparsification, CVaR optimization, and ancilla-assisted superposition solve MIS to optimality on 64-, 99-, and 180-vertex graphs, the largest such gate-based demon...
-
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 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.
-
Mind the gaps: The fraught road to quantum advantage
The authors identify four transitions needed to reach fault-tolerant application-scale quantum computing from current NISQ devices.
-
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 wit...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.