REVIEW 13 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
Signed reviews
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 13 Pith papers
-
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.
-
Universal energy-space localization and stable quantum phases against time-dependent perturbations
For q-local Hamiltonians with bounded change, an initial eigenstate remains exponentially concentrated in a macroscopic energy window under arbitrary time-dependent perturbations.
-
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 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...
-
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.
-
Optimizing Cost Hamiltonian Compilation for Max-Cut QAOA on Unweighted Graphs Using Global Controls and Qubit Bit Flips
For unweighted graphs, path graphs require at least n-1 global coupling layers, every graph can be compiled in at most 2.5n+2 layers, and perfect matching compilations are tied to Hadamard matrices.
-
Quantum-informed surrogate sampling for combinatorial optimization
QISS classically samples a pairwise model built from O(N) low-weight QAOA correlators and outperforms standard QAOA at larger depths on MaxCut and MIS benchmarks.
-
Landscape-Similarity-Guided Optimization in Divide-and-Conquer QAOA
DO-QAOA shows that the 2^m subproblems in frozen-qubit divide-and-conquer QAOA share near-identical variational landscapes, so training one representative and transferring its parameters cuts training cost from expone...
-
Evolving Hard Maximum Cut Instances for Quantum Approximate Optimization Algorithms
The authors evolve max-cut graph instances in a graph autoencoder's latent space that are easy or hard for RQAOA relative to the Goemans-Williamson algorithm, then analyze their features.
-
Improving Quantum Optimization to Achieve Quadratic Time Complexity
Penta-O sets QAOA parameters level by level using five energy measurements per level, cutting parameter-setting cost to O(p^2) circuit executions for depth p.
-
Separating Geometry From Interference in Constrained Quantum Optimization
For product-space constrained quantum optimization, the mixer's absolute amplitude transport reduces to a Hamming-shell Markov chain; a certified success bound then requires a phase-alignment condition that the paper ...
-
Near-Optimal Parameter Tuning of Level-1 QAOA for Ising Models
For p=1 QAOA on Ising models, the paper derives analytic bandwidth bounds, eliminates the mixer angle to reduce optimization to a one-dimensional line search, and proves that for regular graphs the global optimum coin...
-
Networked Quantum Services
A survey of networked quantum services, from distributed quantum computers and cloud platforms to programming languages and standardization efforts.
Discussion (0). Continue with ORCID to comment.