REVIEW 8 cited by
The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
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
abstract
The Quantum Approximate Optimization Algorithm can be applied to search problems on graphs with a cost function that is a sum of terms corresponding to the edges. When conjugating an edge term, the QAOA unitary at depth p produces an operator that depends only on the subgraph consisting of edges that are at most p away from the edge in question. On random d-regular graphs, with d fixed and with p a small constant time log n, these neighborhoods are almost all trees and so the performance of the QAOA is determined only by how it acts on an edge in the middle of tree. Both bipartite random d-regular graphs and general random d-regular graphs locally are trees so the QAOA's performance is the same on these two ensembles. Using this we can show that the QAOA with $(d-1)^{2p} < n^A$ for any $A<1$, can only achieve an approximation ratio of 1/2 for Max-Cut on bipartite random d-regular graphs for d large. For Maximum Independent Set, in the same setting, the best approximation ratio is a d-dependent constant that goes to 0 as d gets big.
Forward citations
Cited by 8 Pith papers
-
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.
-
Measurements Number Scaling in the Quantum Approximate Optimization Algorithm for MaxCut: A Statistical Analysis
Under extensivity and local-structure assumptions, the shot budget for fixed relative QAOA MaxCut performance scales as 1/m while SGD iterations stay size-independent.
-
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.
-
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.
-
Enhanced Quantum behavior on frustrated Ising model: Quantum Approximate Optimization Algorithm study
QAOA simulations of a 4x4 frustrated Ising model show larger deviations from the exact ground state energy near the FM-to-stripe transition, and the paper labels these deviations quantum fluctuations.
Discussion (0). Continue with ORCID to comment.