REVIEW 7 cited by
Quantum Supremacy through the Quantum Approximate Optimization Algorithm
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
read the original abstract
The Quantum Approximate Optimization Algorithm (QAOA) is designed to run on a gate model quantum computer and has shallow depth. It takes as input a combinatorial optimization problem and outputs a string that satisfies a high fraction of the maximum number of clauses that can be satisfied. For certain problems the lowest depth version of the QAOA has provable performance guarantees although there exist classical algorithms that have better guarantees. Here we argue that beyond its possible computational value the QAOA can exhibit a form of Quantum Supremacy in that, based on reasonable complexity theoretic assumptions, the output distribution of even the lowest depth version cannot be efficiently simulated on any classical device. We contrast this with the case of sampling from the output of a quantum computer running the Quantum Adiabatic Algorithm (QADI) with the restriction that the Hamiltonian that governs the evolution is gapped and stoquastic. Here we show that there is an oracle that would allow sampling from the QADI but even with this oracle, if one could efficiently classically sample from the output of the QAOA, the Polynomial Hierarchy would collapse. This suggests that the QAOA is an excellent candidate to run on near term quantum computers not only because it may be of use for optimization but also because of its potential as a route to establishing quantum supremacy.
Forward citations
Cited by 7 Pith papers
-
Warm-Starting MaxCut Relaxation via Low-Depth Quantum Approximate Optimization Algorithm
Depth-1 QAOA pair correlations, mapped to angles for the Burer-Monteiro rank-two MaxCut heuristic, provide a fast warm start that beats random multi-start at small iteration budgets but loses ground at large budgets.
-
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.
-
CVaR-Assisted Custom Penalty Function for Constrained Optimization
A slack-free step-penalty combined with CVaR tail sampling improves VQE optimality gaps on multi-dimensional knapsack benchmarks versus slack-based QUBO.
-
Applying Grover-mixer quantum alternating operator ansatz algorithm to higher-order unconstrained binary optimization problems
Using a Grover mixer instead of a transverse-field mixer makes QAOA's ground-state success probability keep improving with depth on high-order binary optimization instances, and a Gaussian/EVT parameter heuristic come...
-
BloQBench: A Blockchain Benchmarking Framework for Quantum Supremacy
An Ethereum contract generates hard-to-factor integer locks whose on-chain factorization is meant to certify cryptographic quantum supremacy and trigger quantum-secure signatures.
-
From simulatability to universality of continuous-variable quantum computers
A compilation thesis showing that large classes of GKP-based continuous-variable circuits are classically simulatable, while certain resources, including vacuum, can promote them to universality.
-
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). Sign in to comment.