CoChat
Sign Up
Cited by 702

The DOI matches its Crossref record; 15 of the 15 references it cites were found in a registry or an index.

Quantum computational supremacy

Harrow, Aram W., Montanaro, Ashley·2017·Nature
DOI 10.1038/nature23458
Open this paper in CoChat — free account

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1038/nature23458

Cites

15 of 15 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

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 first experimental demonstrations of Boson sampling were reported with n = 3 photons, mainly in integrated photonics.

    “The first experimental demonstrations of Boson sampling were reported with n = 3 photons [91-95], mainly in integrated photonics.”

    From Integrated photonic quantum technologies (2020) · cites this paper as [94]

    The Boson sampling section says several groups made early small-scale experimental demonstrations, supporting that part of the claim. It describes experiments with up to four coincident photons, however, and does not specify that the first demonstrations used three photons or were mainly in integrated photonics; the References list a photonic-chip experiment but do not establish that it was the predominant approach. (LLM, conf=0.84)

    Experimental — accuracy not yet measured

  • The scalability of parametric down-conversion sources and the relevance of non-ideal detector efficiencies have been addressed and investigated experimentally in 2015 with the Scattershot implementation.

    “Furthermore, the scalability of parametric down-conversion sources and the relevance of non-ideal detectors' efficiencies have been addressed in Ref. [579] and investigated experimentally in 2015 with the Scattershot implementation [580,581]”

    From Photonic quantum information processing: a review (2019) · cites this paper as [579]

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

Flagged first, then by citations

Research works printed but not linked: 41

  1. Preskill, J. Quantum computing and the entanglement frontier. Preprint at http://arXiv.org/abs/1203.5813 (2012) · arXiv
  2. Papadimitriou, C. Computational Complexity (Addison-Wesley, 1994)
  3. Cheuk, L. W. et al. Observation of spatial charge and spin correlations in the 2D Fermi-Hubbard model. Science 353, 1260–1264 (2016) · DOI · Paper page
  4. Terhal, B. M. & DiVincenzo, D. P. Adaptive quantum computation, constant-depth quantum circuits and Arthur-Merlin games. Quantum Inf. Comput. 4, 134–145 (2004). This paper gave the first complexity-theoretic argument that a simple class of quantum circuits should be hard to simulate classically
  5. Shepherd, D. & Bremner, M. J. Temporally unstructured quantum computation. Proc. R. Soc. A 465, 1413–1439 (2009) · DOI · Paper page
  6. Boixo, S. et al. Characterizing quantum supremacy in near-term devices. Preprint at http://arXiv.org/abs/1608.00263 (2016). This paper described a proposal for a near-term quantum-supremacy experiment · arXiv
  7. Lund, A., Bremner, M. & Ralph, T. Quantum sampling problems, BosonSampling and quantum supremacy. Preprint at http://arXiv.org/abs/1702.03061 (2017) · DOI
  8. Impagliazzo, R. & Paturi, R. On the complexity of k-SAT. J. Comput. Syst. Sci. 62, 367–375 (2001) · DOI
  9. Cheeseman, P., Kanefsky, B. & Taylor, W. Where the really hard problems are. In Proc. 12th Int. Joint Conf. on Artificial Intelligence (IJCAI ’91) (eds Mylopoulos, J. & Reiter, R. ) 331–337 (Morgan Kaufmann, 1991)
  10. Mertens, S., Mézard, M. & Zecchina, R. Threshold values of random k-SAT from the cavity method. Random Struct. Algorithms 28, 340–373 (2006)
  11. Levin, L. A. Average case complete problems. SIAM J. Comput. 15, 285–286 (1986) · DOI
  12. Bremner, M. J., Montanaro, A. & Shepherd, D. J. Average-case complexity versus approximate simulation of commuting quantum computations. Phys. Rev. Lett. 117, 080501 (2016) · DOI · Paper page
  13. Gao, X., Wang, S.-T. & Duan, L.-M. Quantum supremacy for simulating a translation-invariant Ising spin model. Phys. Rev. Lett. 118, 040502 (2017) · DOI
  14. Aaronson, S. & Chen, L. Complexity-theoretic foundations of quantum supremacy experiments. Preprint at http://arXiv.org/abs/1612.05903 (2016) · arXiv
  15. Knill, E., Laflamme, R. & Zurek, W. Resilient quantum computation. Science 279, 342–345 (1998) · DOI · Paper page
  16. Markov, I. L. & Shi, Y. Simulating quantum computation by contracting tensor networks. SIAM J. Comput. 38, 963–981 (2008) · DOI · Paper page
  17. Bravyi, S. & Gosset, D. Improved classical simulation of quantum circuits dominated by Clifford gates. Phys. Rev. Lett. 116, 250501 (2016) · DOI
  18. Morimae, T., Fujii, K. & Fitzsimons, J. On the hardness of classically simulating the one-clean-qubit model. Phys. Rev. Lett. 112, 130502 (2014) · DOI · Paper page
  19. Fujii, K. & Tamate, S. Computational quantum-classical boundary of noisy commuting quantum circuits. Sci. Rep. 6, 25598 (2016) · DOI
  20. Watrous, J. Quantum computational complexity. In Encyclopedia of Complexity and Systems Science 7174–7201 (Springer, 2009) · DOI
  21. Aaronson, S. & Gottesman, D. Improved simulation of stabilizer circuits. Phys. Rev. A 70, 052328 (2004) · DOI · Paper page
  22. Tichy, M., Mayer, K., Buchleitner, A. & Mølmer, K. Stringent and efficient assessment of boson-sampling devices. Phys. Rev. Lett. 113, 020502 (2014) · DOI · Paper page
  23. Aaronson, S. & Arkhipov, A. BosonSampling is far from uniform. Quantum Inf. Comput. 14, 1383–1423 (2014)
  24. Spagnolo, N. et al. General rules for bosonic bunching in multimode interferometers. Phys. Rev. Lett. 111, 130503 (2013) · DOI
  25. Carolan, J. et al. On the experimental verification of quantum complexity in linear optics. Nat. Photon. 8, 621–626 (2014) · DOI
  26. Hangleiter, D., Kliesch, M., Schwarz, M. & Eisert, J. Direct certification of a class of quantum simulations. Preprint at http://arXiv.org/abs/1602.00703 (2016) · arXiv
  27. Gosset, D., Terhal, B. & Vershynina, A. Universal adiabatic quantum computation via the space-time circuit-to-Hamiltonian construction. Phys. Rev. Lett. 114, 140501 (2015) · DOI
  28. Broadbent, A., Fitzsimons, J. & Kashefi, E. Universal blind quantum computation. In Proc. 50th Annual Symp. Foundations of Computer Science 517–526 (IEEE, 2009) · DOI · Paper page
  29. Aharonov, D. & Vazirani, U. in Computability: Turing, Gödel, Church, and Beyond (MIT Press, 2013)
  30. Rahimi-Keshari, S., Ralph, T. C. & Caves, C. M. Sufficient conditions for efficient classical simulation of quantum optics. Phys. Rev. X 6, 021039 (2016)
  31. Kalai, G. & Kindler, G. Gaussian noise sensitivity and BosonSampling. Preprint at http://arXiv.org/abs/1409.3093 (2014) · arXiv
  32. Bravyi, S., DiVincenzo, D., Oliveira, R. & Terhal, B. The complexity of stoquastic local Hamiltonian problems. Quant. Inf. Comput. 8, 0361–0385 (2008)
  33. Dickson, N. G. et al. Thermally assisted quantum annealing of a 16-qubit problem. Nat. Commun. 4, 1903 (2013) · DOI
  34. Nishimura, K., Nishimori, H., Ochoa, A. J. & Katzgraber, H. G. Retrieving the ground state of spin glasses using thermal noise: performance of quantum annealing at finite temperatures. Phys. Rev. E 94, 032105 (2016) · DOI
  35. Spring, J. B. et al. Boson sampling on a photonic chip. Science 339, 798–801 (2013) · DOI · Paper page
  36. Tillmann, M. et al. Experimental boson sampling. Nat. Photon. 7, 540–544 (2013) · DOI · Paper page
  37. Wang, H. et al. High-efficiency multiphoton boson sampling. Nat. Photon. 11, 361–365 (2017) · DOI
  38. Bentivegna, M. et al. Experimental scattershot boson sampling. Sci. Adv. 1, e1400255 (2015) · DOI · Paper page
  39. Han, Y., Hemaspaandra, L. & Thierauf, T. Threshold computation and cryptographic security. SIAM J. Comput. 26, 59–78 (1997) · DOI
  40. Aaronson, S. Quantum computing, postselection, and probabilistic polynomial-time. Proc. R. Soc. A 461, 3473 (2005) · DOI
  41. Toda, S. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20, 865–877 (1991) · DOI

Cited by

Sorted by citations

Metadata

Authors
Harrow, A. W., & Montanaro, A.
Venue
Nature
Publisher
Springer Science and Business Media LLC
Published
2017-09
Volume
549
Issue
7671
Pages
203-209
ISSN
  • 0028-0836
  • 1476-4687
DOI
10.1038/nature23458
Cited by
702
References
15
Language
en
Licence
www.springer.com/tdm (tdm)

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