The DOI matches its Crossref record; 52 of the 52 references it cites were found in a registry or an index.
Characterizing quantum supremacy in near-term devices
Open accessAbstract
A critical question for quantum computing in the near future is whether quantum devices without error correction can perform a well-defined computational task beyond the capabilities of supercomputers. Such a demonstration of what is referred to as quantum supremacy requires a reliable evaluation of the resources required to solve tasks with classical approaches. Here, we propose the task of sampling from the output distribution of random quantum circuits as a demonstration of quantum supremacy. We extend previous results in computational complexity to argue that this sampling task must take exponential time in a classical computer. We introduce cross-entropy benchmarking to obtain the experimental fidelity of complex multiqubit dynamics. This can be estimated and extrapolated to give a success metric for a quantum supremacy demonstration. We study the computational cost of relevant classical algorithms and conclude that quantum supremacy can be achieved with circuits in a two-dimensional lattice of 7 × 7 qubits and around 40 clock cycles. This requires an error rate of around 0.5% for two-qubit gates (0.05% for one-qubit gates), and it would demonstrate the basic building blocks for a fault-tolerant quantum computer. As a benchmark for the development of a future quantum computer, sampling from random quantum circuits is suggested as a task that will lead to quantum supremacy—a calculation that cannot be carried out classically.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The cited source says what the claim attributes to it.
In the citing paper
“This definition differs from [13, 14] and loosely coincides with the complexity of classically simulating the model circuits.”
From Validating quantum computers using randomized model circuits (2019) · cites this paper as [13]
The cited source says what the claim attributes to it.
In the citing paper
“Although the fidelity of such circuits can in principle be inferred by running them and performing cross-entropy benchmarking101, evaluating the cross-entropy requires exact simulation of the circuits in question and is infeasible except for small depth or qubit number.”
From A 98-qubit trapped-ion quantum computer with all-to-all connectivity (2026) · cites this paper as [101]
The cited source says what the claim attributes to it.
In the citing paper
“50 qubits is a significant milestone, because that's beyond what can be simulated by brute force using the most powerful existing digital supercomputers.”
From Quantum Computing in the NISQ era and beyond (2018) · cites this paper as [11]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Surface codes: Towards practical large-scale quantum computation
Fowler, A. G., Mariantoni, M., Martinis, J. M., & Cleland, A. N. (2012) · Physical Review A · doi:10.1103/physreva.86.032324 · Cited by 3,059
Self-citationRandom-matrix theory of quantum transport
Beenakker, C. W. J. (1997) · Reviews of Modern Physics · doi:10.1103/revmodphys.69.731 · Cited by 2,551
Superconducting quantum circuits at the surface code threshold for fault tolerance
Barends, R., Kelly, J., Megrant, A., Veitia, A., Sank, D., Jeffrey, E., White, T. C., Mutus, J., Fowler, A. G., Campbell, B., et al. (2014) · Nature · doi:10.1038/nature13171 · Cited by 1,733
Self-citationFluctuations of Nuclear Reaction Widths
Porter, C. E., & Thomas, R. G. (1956) · Physical Review · doi:10.1103/physrev.104.483 · Cited by 1,199
Randomized benchmarking of quantum gates
Knill, E., Leibfried, D., Reichle, R., Britton, J., Blakestad, R. B., Jost, J. D., Langer, C., Ozeri, R., Seidelin, S., & Wineland, D. J. (2008) · Physical Review A · doi:10.1103/physreva.77.012307 · Cited by 1,019
State preservation by repetitive error detection in a superconducting quantum circuit
Kelly, J., Barends, R., Fowler, A. G., Megrant, A., Jeffrey, E., White, T. C., Sank, D., Mutus, J. Y., Campbell, B., Chen, Y., et al. (2015) · Nature · doi:10.1038/nature14270 · Cited by 916
Self-citationThe computational complexity of linear optics
Aaronson, S., & Arkhipov, A. (2011) · Proceedings of the forty-third annual ACM symposium on Theory of computing · doi:10.1145/1993636.1993682 · Cited by 874
Haake, F. (1991) · NATO ASI Series · doi:10.1007/978-1-4899-3698-1_38 · Cited by 840
Evidence for quantum annealing with more than one hundred qubits
Boixo, S., Rønnow, T. F., Isakov, S. V., Wang, Z., Wecker, D., Lidar, D. A., Martinis, J. M., & Troyer, M. (2014) · Nature Physics · doi:10.1038/nphys2900 · Cited by 810
Self-citationScalable and Robust Randomized Benchmarking of Quantum Processes
Magesan, E., Gambetta, J. M., & Emerson, J. (2011) · Physical Review Letters · doi:10.1103/physrevlett.106.180504 · Cited by 724
Research works printed but not linked: 4
- Brown, W. & Fawzi, O. Scrambling speed of random quantum circuits. Preprint at https://arxiv.org/abs/1210.6644 (2012). · arXiv
- Mehta, M. L. Random Matrices Vol. 142 (Academic, San Diego, CA, 2004).
- Boixo, S., Smelyanskiy, V. N. & Neven, H. Fourier analysis of sampling from noisy chaotic quantum circuits. Preprint at https://arxiv.org/abs/1708.01875 (2017). · arXiv
- Boixo, S., Isakov, S. V., Smelyanskiy, V. N. & Neven, H. Simulation of low-depth quantum circuits as complex undirected graphical models. Preprint at https://arxiv.org/abs/1712.05384 (2017). · arXiv
Cited by
Quantum Computing in the NISQ era and beyond
Preskill, J. (2018) · Quantum · doi:10.22331/q-2018-08-06-79 · Cited by 8,830
“In particular, the resources needed in a classical simulation depend on the depth (number of time steps) of the quantum circuit, as well as on the number of qubits [11, 12, 13].”
BackgroundQuantum supremacy using a programmable superconducting processor
Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J. C., Barends, R., Biswas, R., Boixo, S., Brandao, F. G. S. L., Buell, D. A., et al. (2019) · Nature · doi:10.1038/s41586-019-1666-5 · Cited by 7,720
Self-citationProbing many-body dynamics on a 51-atom quantum simulator
Bernien, H., Schwartz, S., Keesling, A., Levine, H., Omran, A., Pichler, H., Choi, S., Zibrov, A. S., Endres, M., Greiner, M., et al. (2017) · Nature · doi:10.1038/nature24622 · Cited by 2,460
A quantum engineer's guide to superconducting qubits
Krantz, P., Kjaergaard, M., Yan, F., Orlando, T. P., Gustavsson, S., & Oliver, W. D. (2019) · Applied Physics Reviews · doi:10.1063/1.5089550 · Cited by 2,004
Barren plateaus in quantum neural network training landscapes
McClean, J. R., Boixo, S., Smelyanskiy, V. N., Babbush, R., & Neven, H. (2018) · Nature Communications · doi:10.1038/s41467-018-07090-4 · Cited by 2,329
Self-citation
Metadata
- Authors
- Boixo, S., Isakov, S. V., Smelyanskiy, V. N., Babbush, R., Ding, N., Jiang, Z., Bremner, M. J., Martinis, J. M., & Neven, H.
- Affiliations
- Google (United States) (US)
- Google (Switzerland) (CH)
- University of Technology Sydney (AU)
- Corresponding author
- Boixo, Sergio
- ORCID
- Venue
- Nature Physics
- Published
- 2018-04-23
- Volume
- 14
- Issue
- 6
- Pages
- 595-600
- ISSN
- 1745-2473 (ISSN-L)
- 1745-2481
- OpenAlex
- W2482126025
- Semantic Scholar
- a68a7a57efa3de462b6f4884573f69dd4cf0f815
- Cited by
- 1,175
- References
- 50
- Citations by year
- 2026: 77 · 2025: 178 · 2024: 139 · 2023: 147 · 2022: 124 · 2021: 160 · 2020: 126 · 2019: 110 · 2018: 75
- FWCI
- 65.41
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- www.springer.com/tdm (tdm)
- Locations
- Nature Physics (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) (submittedVersion)
- UTS ePRESS (University of Technology Sydney) (submittedVersion)
- arXiv (Cornell University)
- Funders
- U.S. Department of Energy (05CH11231, DE AC02 05CH11231, CE170100012)
- Intel Corporation
- Office of Science (DEAC02–05CH11231)
- Australian Research Council (FT110101044)
- Centre of Excellence for Quantum Computation and Communication Technology, Australian Research Council (CE170100012)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Keywords
- quantum advantage, random quantum circuits, exponential time lower bounds, fault-tolerant quantum computing, error rate
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Characterizing quantum supremacy in near-term devices. https://app.cochat.ai/papers/10.1038/s41567-018-0124-x
- The paper
- Boixo, S., Isakov, S. V., Smelyanskiy, V. N., Babbush, R., Ding, N., Jiang, Z., Bremner, M. J., Martinis, J. M., & Neven, H. (2018). Characterizing quantum supremacy in near-term devices. Nature Physics. https://doi.org/10.1038/s41567-018-0124-x
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.