An efficiently verifiable quantum advantage that survives a public classical-spoofing challenge for 12 months

Sampling and benchmark experiments. Google's 2019 random circuit sampling experiment (53 qubits; Nature 2019), whose classical cost Google estimated at about 10,000 years on a supercomputer, was followed by tensor-network simulations of the same circuits, such as Pan, Chen and Zhang (PRL 2022). IBM's 2023 "utility" experiment on a 127-qubit processor (Nature 2023) was classically reproduced by Tindall et al. (PRX Quantum 2024) and Begušić and Chan (arXiv 2023), among others. D-Wave's March 2025 quantum-annealing simulation result (King et al., Science 2025) was challenged by a Flatiron Institute belief-propagation tensor-network simulation of the same spin-glass dynamics (Tindall et al., Science, 21 May 2026). In October 2025 Google reported "Quantum Echoes", an out-of-time-order correlator measurement on its Willow chip (Nature, 22 October 2025), estimating that the classical computation would take about 13,000 times longer on a supercomputer, and calling the result verifiable in the weaker sense that the measured expectation values can be reproduced on other quantum devices; the authors report that a related NMR demonstration is not yet beyond classical. Gharibyan et al. (BlueQubit and collaborators) ran "peaked circuit" instances on Quantinuum's 56-qubit H2 trapped-ion device and estimated a classical cost of years (arXiv, October 2025, preprint); Kremer and Dupuis (arXiv April 2026, preprint) report that the largest instance can be contracted classically in about an hour on one GPU. Martiel et al. (IBM and collaborators; arXiv July 2026, preprint) sampled a 64-qubit, depth-73 Clifford circuit doped with 314 T gates, encoded in error-detecting codes, and certified a fidelity lower bound of 0.349 at 95% confidence under device-dependent noise assumptions; it is not refereed and has not been independently challenged.

Provable but not yet useful. Yamakawa and Zhandry (J. ACM 2024) proved a verifiable quantum-classical separation relative to a random oracle. Liu et al. (Nature, March 2025) generated certified randomness on a trapped-ion processor; certification relied on supercomputer-scale classical verification and on a complexity assumption against classical spoofing. Decoded quantum interferometry (Nature 2025) targets optimisation; Parekh (arXiv 2025; TQC 2026) showed that the MaxCut instances on which it attains a nontrivial asymptotic guarantee are solvable exactly in classical polynomial time, and Kramer et al. (arXiv, 1 October 2026, preprint) claim a provable gap in approximation ratio for a variant of the underlying problem in an oracle model.

Useful, provable, but needs fault tolerance. Shor's algorithm is both verifiable and useful but needs error-corrected machines far beyond current devices. For search problems, Brehm and Weggemans (Quantum 2026) found that fault-tolerant speedups of quantum backtracking and Grover search for -SAT largely vanish, even asymptotically, once minimal structure is introduced, when compared against the 2023 SAT Competition main-track winner.

A confirmed verifiable advantage would be the first experimental evidence that a quantum device does something classical computers cannot reproduce at scale, and would calibrate resource estimates for error-corrected machines. It has no direct commercial use unless the task is itself useful (certified randomness is the nearest candidate); this problem requires verifiability and robustness to spoofing, not usefulness.

A published experiment meeting (i)–(iii) above, followed by a public challenge window of 12 months in which no classical method matches the certified score, with the classical-hardness assumption stated explicitly. Resolved negatively for a given task if a classical algorithm reproduces the certified score at the claimed size.