CoChat
Sign Up
Cited by 152Quantum Computing Algorithms and ArchitectureQuantum Information and CryptographyQuantum Mechanics and Applications

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 access
Hangleiter, Dominik, Eisert, Jens·2023·Reviews of Modern Physics
DOI 10.1103/revmodphys.95.035001
Open this paper in CoChat — free accountOpen PDF

Abstract

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

Crossref · 10.1103/revmodphys.95.035001

Cites

369 of 369 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

We couldn’t retrieve this paper’s full text, so its claims and self-check weren’t run. The registry and citation checks still apply.

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?

Citations

Cites

Flagged first, then by citations

Show all 377 references

8 of the 377 references couldn’t be matched to a known paper.

Research works printed but not linked: 13

  1. 10.4086/toc.2013.v009a004 · DOI
  2. Aaronson, S., 2017, Proceeding of the 32nd Computational Complexity Conference (CCC 2017), Riga, 2017
  3. Barak, B., 2021, Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), 2021
  4. 10.1002/(SICI)1098-2418(1999010)14:1<29::AID-RSA2>3.0.CO;2-X · DOI
  5. Bernstein, E., 1993, Proceedings of the 25th Annual ACM Symposium on the Theory of Computing (STOC ’93), San Diego, 1993
  6. 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
  7. Bouland, A., 2018, Proceedings of the 33rd Computational Complexity Conference (CCC 2018), San Diego, 2018
  8. 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
  9. de Finetti, B., 1937, Ann. Inst. Henri Poincaré, 7, 1
  10. 10.4086/toc.2015.v011a006 · DOI
  11. 10.1126/science.abi8378 · DOI
  12. 10.1038/s41534-018-0113-z · DOI
  13. 10.1038/s41534-018-0113-z · DOI

Cited by

Sorted by citations

Items 101–152 of 152

Related

See all

Metadata

Authors
Hangleiter, D., & Eisert, J.
Affiliations
National Institute of Standards and Technology (US)
Corresponding author
Hangleiter, Dominik
ORCID
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
DOI
10.1103/revmodphys.95.035001
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
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