REVIEW 6 cited by
Threshold for Fault-tolerant Quantum Advantage with 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
abstract
Optimization is often cited as a promising application of quantum computers. However, the low degree of provable quantum speedups has led prior rigorous end-to-end resource analyses to conclude that a quantum computer is unlikely to surpass classical state-of-the-art on optimization problems under realistic assumptions. In this work, we compile and analyze the Quantum Approximate Optimization Algorithm (QAOA) combined with Amplitude Amplification (AA) applied to random 8-SAT at the satisfiability threshold. Our compilation involves careful optimization of circuits for Hamiltonian simulation, which may be of independent interest. We use the analytical scaling of the time-to-solution for QAOA identified by PRX Quantum 5, 030348 (2024) and find that with QAOA depth $p=623$, QAOA+AA achieves a crossover with state-of-the-art classical heuristics at 179 variables and 14.99 hours of runtime when executed on a surface-code-based fault-tolerant quantum computer with 73.91 million physical qubits, a physical error rate of $10^{-3}$, and a $1~\mu$s code cycle time. Notably, we allow the classical solver to be parallelized as long as its total energy consumption is equal to that required for decoding in the surface code. We further show that this restriction on classical solver energy consumption can be relaxed given optimistic but plausible reductions in physical error rates and fault-tolerance overheads, enabling a crossover of 2.94 hours using 8.88 million physical qubits against a classical solver running on a supercomputer with $725,760$ CPU cores. These findings support the hypothesis that large-scale fault-tolerant quantum computers will be useful for optimization.
Forward citations
Cited by 6 Pith papers
-
Quantum-Informed Portfolio Selection: An End-to-End Pipeline Validated on Trapped-Ion Hardware with Real Market Data
qReduMIS, using QAOA frozen-node signals plus classical reductions, solves real market MIS portfolio instances up to 225 assets on Helios with far better success and TTS scaling than standalone QAOA.
-
Practical protein-pocket hydration-site prediction for drug discovery on a quantum computer
A QUBO-based hydration-site prediction workflow, executed on IBM Heron hardware up to 123 qubits, locates protein-pocket crystal waters with accuracy comparable to leading classical methods.
-
Role of Nonstabilizerness in Quantum Optimization
QAOA on Sherrington-Kirkpatrick models shows a peak in nonstabilizerness at intermediate depth followed by a decline toward the solution, a magic barrier that also appears in adiabatic quantum annealing.
-
Non-Variational Quantum Random Access Optimization with Alternating Operator Ansatz
Non-variational QAOA with fixed angles solves QRAO's relaxed MaxCut Hamiltonian with performance close to optimized parameters and about three times fewer qubits than standard QAOA.
-
Awesome Quantum Computing Experiments: Benchmarking Experimental Progress Towards Fault-Tolerant Quantum Computation
Experimental quantum hardware metrics follow exponential trends with reported doubling or halving times of about one to six years across platforms.
-
Near-term Application Engineering Challenges in Emerging Superconducting Qudit Processors
A review identifying near-term application opportunities and hardware engineering challenges for transmon-cavity qudit processors, with no new experimental or theoretical result.
Discussion (0). Continue with ORCID to comment.