The DOI matches its Crossref record; 369 of the 377 references it cites were found in a registry or an index.
Computational advantage of quantum random sampling
Open accessAbstract
Quantum computers have improved and recent experiments have claimed quantum advantage -- completion of a computational task that is evidently hard for any conventional computer. The problem solved is that of obtaining samples, by quantum measurement, from a certain probability distribution. This review shows in what precise way quantum random sampling can be seen as a computation. It explains what that computation solves, in what way it outperforms classical computations, and what methods of verification are available. Quantum random sampling becomes a first test of the presumed exponential computational advantage of quantum computers over classical ones.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
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?
In the citing paper
“At the same time, because the classical difficulty of sampling from the outputs of random quantum circuits has been extremely well studied over the past decade100, RCS provides a well-vetted benchmark for the computational power of a quantum computer.”
From A 98-qubit trapped-ion quantum computer with all-to-all connectivity (2026) · cites this paper as [100]
Citations
Cites
Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?
Einstein, A., Podolsky, B., & Rosen, N. (1935) · Physical Review · doi:10.1103/physrev.47.777 · Cited by 16,654
Ror2 signaling regulates Golgi structure and transport through IFT20 for tumor invasiveness
Nishita, M., Park, S.-Y., Nishio, T., Kamizaki, K., Wang, Z., Tamada, K., Takumi, T., Hashimoto, R., Otani, H., Pazour, G. J., et al. (2017) · Scientific Reports · doi:10.1038/s41598-016-0028-x · Cited by 15,947
On the Einstein Podolsky Rosen paradox
Bell, J. S. (1964) · Physics Physique Fizika · doi:10.1103/physicsphysiquefizika.1.195 · Cited by 12,252
(2012) · Cited by 9,062
A fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830
Algorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
Many-body physics with ultracold gases
Bloch, I., Dalibard, J., & Zwerger, W. (2008) · Reviews of Modern Physics · doi:10.1103/revmodphys.80.885 · Cited by 8,114
Quantum 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
Simulating physics with computers
Feynman, R. P. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02650179 · Cited by 7,691
Research works printed but not linked: 13
- 10.4086/toc.2013.v009a004 · DOI
- Aaronson, S., 2017, Proceeding of the 32nd Computational Complexity Conference (CCC 2017), Riga, 2017
- Barak, B., 2021, Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), 2021
- 10.1002/(SICI)1098-2418(1999010)14:1<29::AID-RSA2>3.0.CO;2-X · DOI
- Bernstein, E., 1993, Proceedings of the 25th Annual ACM Symposium on the Theory of Computing (STOC ’93), San Diego, 1993
- Björklund, A., 2012, Proceedings of the 2012 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’12), Kyoto, 2012, 10.1137/1.9781611973099.73 · DOI
- Bouland, A., 2018, Proceedings of the 33rd Computational Complexity Conference (CCC 2018), San Diego, 2018
- Clifford, P., 2018, Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’18), New Orleans, 2018, 10.1137/1.9781611975031.10 · DOI
- de Finetti, B., 1937, Ann. Inst. Henri Poincaré, 7, 1
- 10.4086/toc.2015.v011a006 · DOI
- 10.1126/science.abi8378 · DOI
- 10.1038/s41534-018-0113-z · DOI
- 10.1038/s41534-018-0113-z · DOI
Cited by
Sorted by citations
Deng, Y., Gu, Y.-C., Liu, H.-L., Gong, S.-Q., Su, H., Zhang, Z.-J., Tang, H., Jia, M.-H., Xu, J., Chen, M.-C., et al. (2023) · Physical Review Letters · doi:10.1103/physrevlett.131.150601 · Cited by 176
Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial
Mele, A. A. (2024) · Quantum · doi:10.22331/q-2024-05-08-1340 · Cited by 237
Towards provably efficient quantum algorithms for large-scale machine-learning models
Liu, J., Liu, M., Liu, J.-P., Ye, Z., Wang, Y., Alexeev, Y., Eisert, J., & Jiang, L. (2024) · Nature Communications · doi:10.1038/s41467-023-43957-x · Cited by 121
Self-citationUnderstanding quantum machine learning also requires rethinking generalization
Gil-Fuster, E., Eisert, J., & Bravo-Prieto, C. (2024) · Nature Communications · doi:10.1038/s41467-024-45882-z · Cited by 109
Self-citationBenchmarking quantum computers
Proctor, T. J., Young, K. C., Baczewski, A., & Blume-Kohout, R. (2025) · Nature Reviews Physics · doi:10.1038/s42254-024-00796-z · Cited by 116
Metadata
- Authors
- Hangleiter, D., & Eisert, J.
- Affiliations
- National Institute of Standards and Technology (US)
- Corresponding author
- Hangleiter, Dominik
- Venue
- Reviews of Modern Physics
- Publisher
- American Physical Society (APS)
- Published
- 2023-07-20
- Volume
- 95
- Issue
- 3
- ISSN
- 0034-6861 (ISSN-L)
- 1539-0756
- OpenAlex
- W4384935381
- Cited by
- 145
- References
- 377
- Citations by year
- 2026: 29 · 2025: 66 · 2024: 36 · 2023: 12
- FWCI
- 12.66
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- Locations
- Reviews of Modern Physics (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- Refubium (Universitätsbibliothek der Freien Universität Berlin) (submittedVersion)
- HZB Repository (Helmholtz-Zentrum Berlin für Materialien und Energie GmbH (HZB)) (submittedVersion)
- Fraunhofer-Publica (Fraunhofer-Gesellschaft) (submittedVersion)
- arXiv (Cornell University)
- Universitätsbibliothek der FU Berlin Hochschulschriftenstelle u. Dokumentenserver
- Funders
- U.S. Department of Defense
- Simons Institute for the Theory of Computing, University of California Berkeley
- Deutsche Forschungsgemeinschaft (CRC 183, EI 519/21-1)
- Bundesministerium für Bildung und Forschung
- QuantERA
- Einstein Stiftung Berlin
- Horizon 2020 Framework Programme (817482)
- German Federal Ministry of Economics and Climate Protection
- Munich Quantum Valley
- 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 Mechanics and Applications
- Keywords
- quantum advantage, quantum measurement, probability distributions
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
