The 2019 Sycamore quantum-supremacy experiment left two linked open questions that its authors stated explicitly: how to verify and fidelity-estimate the output of sampling experiments whose ideal distributions can no longer be classically computed, and how robust any claimed quantum advantage is against advances in classical simulation algorithms. Seven years of follow-up have sharpened both without closing either. Tensor-network simulations have reproduced the original 53-qubit task at equal or better benchmark fidelity, a polynomial-time classical algorithm was proven for asymptotic random-circuit sampling (RCS) at constant noise, and each subsequent 'beyond-classical' claim has been contested by improved classical methods, while 2024–2026 work continues to map the noise-and-size boundary between classically simulable and hard regimes. Meanwhile the only established fiducial benchmark, linear cross-entropy (XEB), still requires exponentially expensive classical amplitude computation, and certified-randomness protocols certify entropy only under restricted adversary models. The open problem is to establish a certified standard of evidence for sampling-based quantum advantage: a sound, scalable verification or fidelity-estimation protocol whose classical cost grows polynomially and whose soundness does not presuppose the classical hardness being verified, together with a delineation of the noisy-RCS regime in which genuine, algorithm-robust quantum advantage exists to be verified.

Background

Random circuit sampling (RCS) is the task of drawing bitstrings from the output distribution of a random quantum circuit built from single-qubit rotations and two-qubit entangling gates applied in layers across a 2D qubit lattice; it is the leading experimental candidate for 'quantum supremacy' or quantum advantage — a programmable quantum device performing a sampling task beyond the practical reach of any classical computer. In 2019 the Google Sycamore processor (53 working qubits, 20 cycles) sampled such circuits in ~200 seconds and estimated ~10,000 years for an equal-fidelity classical simulation (Arute et al. 2019), basing the claim on complexity-theoretic evidence that ideal RCS is hard to sample or verify on average.

Verification is the crux. The benchmark used was the linear cross-entropy fidelity FXEB=2n⟨P(xi)⟩i−1\mathcal{F}_{\mathrm{XEB}} = 2^{n}\langle P(x_i) \rangle_i - 1, where P(xi)P(x_i) is the ideal probability of the measured bitstring xix_i on nn qubits; values near 1 indicate sampling biased toward high-probability outputs, 0 indicates uniform noise. Computing P(xi)P(x_i) requires classical simulation of the ideal circuit, which is exponentially expensive — for the largest Sycamore circuits the authors estimated that verifying the fidelity alone would take millions of years, so they archived the measured bitstrings 'to encourage development and testing of more advanced verification algorithms.' Bouland, Fefferman, Nirkhe and Vazirani (2018) had shown that efficient classical verification of RCS would collapse the same average-case hardness assumptions underlying the advantage claim, so verification cannot simply be assumed cheap.

Both pillars of the claim have since been stressed. On the classical side, tensor-network methods (which compress the circuit's state by exploiting limited entanglement) have repeatedly caught up: Pan and Zhang (2021) generated one million correlated bitstrings from the 53-qubit, 20-cycle Sycamore circuit with XEB fidelity 0.739 on a 60-GPU cluster, and Liu et al. (2021) simulated the full most-challenging Sycamore task in about a week on the Sunway supercomputer. Aharonov, Gao, Landau, Liu and Vazirani (2023) proved that noisy RCS at a constant per-gate error rate is classically simulable in polynomial time in the anti-concentration regime (circuits deep enough that output probabilities are spread out near-uniformly) — evidence against scalable advantage at fixed noise, though not against finite-size experiments. The pattern recurred for later claims: IBM's 127-qubit kicked-Ising 'utility' experiment (Kim et al. 2023) was reproduced by tensor networks (Tindall et al. 2024), and D-Wave's 'beyond-classical' annealing claim (King et al. 2025) was matched by lattice-specific tensor networks (Tindall et al. 2025). Google's 67-qubit, 32-cycle RCS experiment (Morvan et al. 2024) claims a regime whose cost exceeds classical computers 'even when accounting for the inevitable presence of noise,' but its own abstract flags as 'an unanswered question' the extent to which noise makes outputs spoofable by classical computation; its verification still rests on XEB for classically simulable patch and elided circuits (subcircuits obtained by cutting the full circuit into patches or removing gates, small enough to simulate classically) plus extrapolation.

On the verification side, interactive protocols offer a different route: Aaronson and Hung's certified-randomness protocol (2023), demonstrated on Quantinuum's 56-qubit trapped-ion processor (Liu et al. 2025, certifying 71,313 bits against a restricted adversary class under additional assumptions), verifies generated entropy rather than sampling fidelity. Cryptographic proposals for classically verifying quantum advantage (Chia et al. 2023; Yan 2026) remain without practical scalable demonstrations, and as of 2026 Google-authored work still poses the underlying question as open: 'How can quantum outcomes be trusted when reliable classical benchmarks are unavailable?' (Barron et al. 2026, which offers heuristic cross-validation of observables rather than a sound verifier for sampling distributions). In parallel, theory work continues to locate the noise-strength boundary between classically simulable and hard noisy RCS (Go, Oh and Jeong 2026).

Problem Statement

Establish a certified standard of evidence for quantum advantage in random circuit sampling, in the regime beyond the reach of classical simulation of the ideal circuit — the open problem that Arute et al. (2019) left when they archived their supremacy-circuit bitstrings 'to encourage development and testing of more advanced verification algorithms' and asked 'to what extent algorithmic innovation can enhance classical simulations.' The common objective is a verifiable claim of the form 'this device samples the intended hard distribution, in a regime where no known classical algorithm can match it' — the relativized standard of the source paper's own claim ('This dramatic increase in speed compared to all known classical algorithms'), which the theorem branch of component (2) may strengthen into a statement relative to explicitly stated average-case hardness assumptions; the objective decomposes into two jointly necessary, scientifically linked components.

(1) Scalable, sound verification. Construct and demonstrate a protocol — interactive, statistical, cryptographic, or based on provable bounds — that, given the circuit description and outputs of a sampling experiment at sizes where exact classical amplitudes are computationally out of reach (the regime now exemplified by tens of qubits at depth ~30 cycles), estimates the sampled distribution's fidelity to the ideal distribution or certifies an advantage property of it, with classical verification cost scaling polynomially in circuit size and with soundness guarantees whose assumptions do not amount to assuming the classical hardness that the verification is meant to establish. Demonstrate the protocol on an instance at or beyond the current classical-simulation frontier.

(2) A robust advantage regime. Delineate the noise-rate and size regime in which noisy RCS retains genuine computational advantage over all known classical algorithms — via theorem under stated (average-case hardness) assumptions, or via empirical validation against the best available classical methods (for example tensor-network contraction and sampling; big-head and sparsification schemes, i.e., classical heuristics that fix or elide the most influential qubits and amplitudes; and polynomial-time algorithms for high-noise regimes; this enumeration is illustrative and not an exhaustive specification of the known-algorithm class) — so that the object component (1) certifies is well-founded; the delineation of the simulability transition by Go, Oh and Jeong (2026) and the spoofability question posed by Morvan et al. (2024) are open instances of this component.

The two components are inseparable parts of one objective: a verifier for a trivially simulable regime is vacuous, and an advantage claim without scalable verification is unfalsifiable. The problem is completed by achieving both — a sound scalable verification demonstrated on an instance in a regime robust to known classical algorithms. This formulation follows the source paper's framing, which posed both questions as open and expected that lower classical simulation costs 'will be consistently outpaced by hardware improvements on larger quantum processors' rather than treating any particular simulation result as settling them; the boundary of classical intractability has nevertheless repeatedly moved since 2019, so the regime identified under component (2) is tied to the classical algorithms known at the time of a proposed resolution.

References

  1. Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J. C., Barends, R., … Neven, H., Martinis, J. M. (Google AI Quantum and collaborators, 77 authors). 'Quantum supremacy using a programmable superconducting processor.' Nature 574, 505–510 (2019). DOI: 10.1038/s41586-019-1666-5. https://doi.org/10.1038/s41586-019-1666-5 (source of the open problem)
  2. Bouland, A., Fefferman, B., Nirkhe, C., Vazirani, U. 'On the complexity and verification of quantum random circuit sampling.' Nature Physics 15, 159–163 (2019). DOI: 10.1038/s41567-018-0318-2; arXiv:1803.04402. https://arxiv.org/abs/1803.04402
  3. Pan, F., Zhang, P. 'Simulating the Sycamore quantum supremacy circuits.' arXiv:2103.03074 (2021). https://arxiv.org/abs/2103.03074
  4. Liu, X., Guo, C., Liu, Y., Yang, Y., Song, J., Gao, J., Wang, Z., Wu, W., Peng, D., Zhao, P., Li, F., Huang, H.-L., Fu, H., Chen, D. 'Redefining the Quantum Supremacy Baseline With a New Generation Sunway Supercomputer.' arXiv:2111.01066 (2021). https://arxiv.org/abs/2111.01066
  5. Aharonov, D., Gao, X., Landau, Z., Liu, Y., Vazirani, U. 'A polynomial-time classical algorithm for noisy random circuit sampling.' In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023). DOI: 10.1145/3564246.3585234; arXiv:2211.03999. https://arxiv.org/abs/2211.03999
  6. Zlokapa, A., Villalonga, B., Boixo, S., Lidar, D. 'Boundaries of quantum supremacy via random circuit sampling.' npj Quantum Information 9, 36 (2023). DOI: 10.1038/s41534-023-00703-x; arXiv:2005.02464. https://arxiv.org/abs/2005.02464
  7. Kim, Y., Eddins, A., Anand, S., Wei, K. X., et al. (11 authors). 'Evidence for the utility of quantum computing before fault tolerance.' Nature 618, 500–505 (2023). DOI: 10.1038/s41586-023-06096-3. https://doi.org/10.1038/s41586-023-06096-3
  8. Tindall, J., Fishman, M., Stoudenmire, M., Sels, D. 'Efficient tensor network simulation of IBM's Eagle kicked Ising experiment.' PRX Quantum 5, 010308 (2024). DOI: 10.1103/PRXQuantum.5.010308; arXiv:2306.14887. https://arxiv.org/abs/2306.14887
  9. Morvan, A., Villalonga, B., Mi, X., Mandrà, S., Bengtsson, A., Klimov, P. V., et al. (Google Quantum AI and collaborators). 'Phase transitions in random circuit sampling.' Nature 634, 328–333 (2024). DOI: 10.1038/s41586-024-07998-6; arXiv:2304.11119. https://arxiv.org/abs/2304.11119
  10. King, A. D., Nocera, A., Rams, M. M., Dziarmaga, A., Wiersema, J., Bernoudy, W., et al. 'Beyond-classical computation in quantum simulation.' Science 388 (2025). DOI: 10.1126/science.ado6285. https://doi.org/10.1126/science.ado6285
  11. Tindall, J., Mello, A., Fishman, M., Stoudenmire, M., Sels, D. 'Dynamics of disordered quantum systems with two- and three-dimensional tensor networks.' arXiv:2503.05693 (2025). https://arxiv.org/abs/2503.05693
  12. Acharya, A., Abanin, D., et al. (Google Quantum AI and collaborators). 'Quantum error correction below the surface code threshold.' Nature 638, 920–926 (2025). DOI: 10.1038/s41586-024-08449-y; arXiv:2408.13687. https://arxiv.org/abs/2408.13687
  13. Aaronson, S., Hung, S.-H. 'Certified Randomness from Quantum Supremacy.' In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023). DOI: 10.1145/3564246.3585145; arXiv:2303.01625. https://arxiv.org/abs/2303.01625
  14. Liu, M., Shaydulin, R., Niroula, P., et al. (32 authors). 'Certified randomness using a trapped-ion quantum processor.' Nature 640, 343–348 (2025). DOI: 10.1038/s41586-025-08737-1; arXiv:2503.20498. https://arxiv.org/abs/2503.20498
  15. Chia, N.-H., Fu, H., Song, F., Yao, P. 'A Cryptographic Perspective on the Verifiability of Quantum Advantage.' arXiv:2310.14464 (2023). https://arxiv.org/abs/2310.14464
  16. Rudolph, M. S., Tindall, J. 'Simulating and Sampling from Quantum Circuits with 2D Tensor Networks.' arXiv:2507.11424 (2025). https://arxiv.org/abs/2507.11424
  17. Barron, S. V., Mitchell, B., Tripathi, V., Grieco, F., Rosen, I., Pietracaprina, F., et al. (46 authors). 'Observable Estimation in the Absence of Classical Verification.' arXiv:2607.25998 (2026). https://arxiv.org/abs/2607.25998
  18. Go, B., Oh, C., Jeong, H. 'Hardness and Complexity Transition of Noisy Random Circuit Sampling.' arXiv:2607.20804 (2026). https://arxiv.org/abs/2607.20804
  19. Yan, B. 'Classical Verification of Quantum Advantage via Clifford Obfuscation.' arXiv:2608.15963 (2026). https://arxiv.org/abs/2608.15963