On the complexity and verification of quantum random circuit sampling
The DOI matches its Crossref record; 36 of the 37 references it cites were found in a registry or an index, and 1 are not checked yet.
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
“for which we also provide numerical evidence of so-called anticoncentration99,100.”
From Logical quantum processor based on reconfigurable atom arrays (2024) · cites this paper as [100]
Citations
Cites
Quantum Computing in the NISQ era and beyond
Preskill, J. (2018) · Quantum · doi:10.22331/q-2018-08-06-79 · Cited by 8,830
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1999) · SIAM Review · doi:10.1137/s0036144598347011 · Cited by 3,904
Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets
Kandala, A., Mezzacapo, A., Temme, K., Takita, M., Brink, M., Chow, J. M., & Gambetta, J. M. (2017) · Nature · doi:10.1038/nature23879 · Cited by 2,982
The complexity of computing the permanent
Valiant, L. G. (1979) · Theoretical Computer Science · doi:10.1016/0304-3975(79)90044-6 · Cited by 2,705
Bernstein, E., & Vazirani, U. (1993) · Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 · doi:10.1145/167088.167097 · Cited by 1,284
Self-citationCharacterizing quantum supremacy in near-term devices
Boixo, S., Isakov, S. V., Smelyanskiy, V. N., Babbush, R., Ding, N., Jiang, Z., Bremner, M. J., Martinis, J. M., & Neven, H. (2018) · Nature Physics · doi:10.1038/s41567-018-0124-x · Cited by 1,175
Observation of a many-body dynamical phase transition with a 53-qubit quantum simulator
Zhang, J., Pagano, G., Hess, P. W., Kyprianidis, A., Becker, P., Kaplan, H., Gorshkov, A. V., Gong, Z.-X., & Monroe, C. (2017) · Nature · doi:10.1038/nature24654 · Cited by 1,079
Holographic quantum error-correcting codes: toy models for the bulk/boundary correspondence
Pastawski, F., Yoshida, B., Harlow, D., & Preskill, J. (2015) · Journal of High Energy Physics · doi:10.1007/jhep06(2015)149 · Cited by 958
The 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
Boson Sampling on a Photonic Chip
Spring, J. B., Metcalf, B. J., Humphreys, P. C., Kolthammer, W. S., Jin, X.-M., Barbieri, M., Datta, A., Thomas-Peter, N., Langford, N. K., Kundys, D., et al. (2013) · Science · doi:10.1126/science.1231692 · Cited by 837
Tillmann, M., Dakić, B., Heilmann, R., Nolte, S., Szameit, A., & Walther, P. (2013) · Nature Photonics · doi:10.1038/nphoton.2013.102 · Cited by 709
Integrated multimode interferometers with arbitrary designs for photonic boson sampling
Crespi, A., Osellame, R., Ramponi, R., Brod, D. J., Galvão, E. F., Spagnolo, N., Vitelli, C., Maiorino, E., Mataloni, P., & Sciarrino, F. (2013) · Nature Photonics · doi:10.1038/nphoton.2013.112 · Cited by 662 · cited 1×
“As an added bonus, Aaronson and Arkhipov realized that BosonSampling might be experimentally feasible in the near term, and helped jump-start the quest for quantum supremacy more than half a decade ago 11–14 .”
BackgroundPhotonic Boson Sampling in a Tunable Circuit
Broome, M. A., Fedrizzi, A., Rahimi-Keshari, S., Dove, J., Aaronson, S., Ralph, T. C., & White, A. G. (2013) · Science · doi:10.1126/science.1231440 · Cited by 634
On the power of quantum computation
Simon, D. R. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365701 · Cited by 491
A blueprint for demonstrating quantum supremacy with superconducting qubits
Neill, C., Roushan, P., Kechedzhi, K., Boixo, S., Isakov, S. V., Smelyanskiy, V., Megrant, A., Chiaro, B., Dunsworth, A., Arya, K., et al. (2018) · Science · doi:10.1126/science.aao4309 · Cited by 458
Random Quantum Circuits are Approximate 2-designs
Harrow, A. W., & Low, R. A. (2009) · Communications in Mathematical Physics · doi:10.1007/s00220-009-0873-6 · Cited by 324
Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
Bremner, M. J., Jozsa, R., & Shepherd, D. J. (2011) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2010.0301 · Cited by 308 · cited 2×
“For example, the ability to sample one particular output x of a quantum circuit with the correct probability D ( x ) is known to be hard for classical computers, under standard complexity assumptions (for example, refs 10,20–23 ).”
BackgroundAverage-Case Complexity Versus Approximate Simulation of Commuting Quantum Computations
Bremner, M. J., Montanaro, A., & Shepherd, D. J. (2016) · Physical Review Letters · doi:10.1103/physrevlett.117.080501 · Cited by 299
Commercialize quantum technologies in five years
Mohseni, M., Read, P., Neven, H., Boixo, S., Denchev, V., Babbush, R., Fowler, A., Smelyanskiy, V., & Martinis, J. (2017) · Nature · doi:10.1038/543171a · Cited by 268
Lipton, R. (1991) · DIMACS Series in Discrete Mathematics and Theoretical Computer Science · doi:10.1090/dimacs/002/13 · Cited by 255
Complexity-Theoretic Foundations of Quantum Supremacy Experiments
Aaronson, S., & Chen, L. (2016) · arXiv · doi:10.48550/arxiv.1612.05903 · Cited by 218
Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
Bremner, M. J., Jozsa, R., Shepherd, D. J., et al. (2010) · Cited by 216
Achieving quantum supremacy with sparse and noisy commuting quantum computations
Bremner, M. J., Montanaro, A., & Shepherd, D. J. (2017) · Quantum · doi:10.22331/q-2017-04-25-8 · Cited by 191
Self-testing/correcting for polynomials and for approximate functions
Gemmell, P., Lipton, R., Rubinfeld, R., Sudan, M., & Wigderson, A. (1991) · Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC '91 · doi:10.1145/103418.103429 · Cited by 181
Classical boson sampling algorithms with superior performance to near-term experiments
Neville, A., Sparrow, C., Clifford, R., Johnston, E., Birchall, P. M., Montanaro, A., & Laing, A. (2017) · Nature Physics · doi:10.1038/nphys4270 · Cited by 178
The Classical Complexity of Boson Sampling
Clifford, P., & Clifford, R. (2018) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611975031.10 · Cited by 157
Hardness of Classically Simulating the One-Clean-Qubit Model
Morimae, T., Fujii, K., & Fitzsimons, J. F. (2014) · Physical Review Letters · doi:10.1103/physrevlett.112.130502 · Cited by 70
Exponential quantum speed-ups are generic
Brandão, F. G. S. L., & Horodecki, M. (2013) · Quantum Information and Computation · doi:10.26421/qic13.11-12-1 · Cited by 65
Anticoncentration theorems for schemes showing a quantum speedup
Hangleiter, D., Bermejo-Vega, J., Schwarz, M., & Eisert, J. (2018) · Quantum · doi:10.22331/q-2018-05-22-65 · Cited by 58
Complexity-Theoretic Foundations of Quantum Supremacy Experiments
Aaronson, S., & Chen, L. (2016) · arXiv (Cornell University) · doi:10.14288/1.0343134 · Cited by 54
Complexity Classification of Conjugated Clifford Circuits
Bouland, A., Fitzsimons, J. F., & Koh, D. E. (2017) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.ccc.2018.21 · Cited by 50
Self-citationAnticoncentration theorems for schemes showing a quantum speedup
Hangleiter, D., Bermejo-Vega, J., Schwarz, M., & Eisert, J. (2018) · Refubium (Universitätsbibliothek der Freien Universität Berlin) · doi:10.17169/refubium-250 · Cited by 48
Morimae, T. (2017) · Physical Review A · doi:10.1103/physreva.96.040302 · Cited by 46
Exponential quantum speed-ups are generic
Brandão, F. G. S. L., & Horodecki, M. (2013) · CaltechAUTHORS (California Institute of Technology) · doi:10.5555/2535639.2535640 · Cited by 23
On the Complexity of Random Quantum Computations and the Jones PolynomialPreprint
Mann, R. L., & Bremner, M. J. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1711.00686 · Cited by 22
Complexity classification of two-qubit commuting hamiltoniansPreprint
Bouland, A., Mančinska, L., & Zhang, X. J. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1602.04145 · Cited by 17
Self-citationThe Power of Quantum Fourier Sampling
Fefferman, B., & Umans, C. (2016) · Conference on Theory of Quantum Computation, Communication and Cryptography · doi:10.7907/6hjb-mc69 · Cited by 8
Self-citation
Research works printed but not linked: 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).
- Farhi, E. & Harrow, A. W. Quantum supremacy through the quantum approximate optimization algorithm. Preprint at https://arxiv.org/abs/1602.07674 (2016). · arXiv
- 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
- Welch, L. & Berlekamp, E. Error correction for algebraic block codes. US patent 4,633,470 (1986).
Cited by
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
Logical quantum processor based on reconfigurable atom arrays
Bluvstein, D., Evered, S. J., Geim, A. A., Li, S. H., Zhou, H., Manovitz, T., Ebadi, S., Cain, M., Kalinowski, M., Hangleiter, D., et al. (2024) · Nature · doi:10.1038/s41586-023-06927-3 · Cited by 1,119
“Our implemented circuits are equivalent to IQP circuits 98 , which gives a theoretical basis for understanding why our circuits could be classically hard to simulate, for which we also provide numerical evidence of so-called anticoncentration 99,100 .”
BackgroundMethodStrong Quantum Computational Advantage Using a Superconducting Quantum Processor
Wu, Y., Bao, W.-S., Cao, S., Chen, F., Chen, M.-C., Chen, X., Chung, T.-H., Deng, H., Du, Y., Fan, D., et al. (2021) · Physical Review Letters · doi:10.1103/physrevlett.127.180501 · Cited by 1,059
Theory of the phase transition in random unitary circuits with measurements
Bao, Y., Choi, S., & Altman, E. (2020) · Physical Review B · doi:10.1103/physrevb.101.104301 · Cited by 467
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 472
Metadata
- Authors
- Bouland, A., Fefferman, B., Nirkhe, C., & Vazirani, U.
- Affiliations
- University of California, Berkeley (US)
- National Institute of Standards and Technology (US)
- Corresponding author
- Fefferman, Bill
- Venue
- Nature Physics
- Published
- 2018-10-29
- Volume
- 15
- Issue
- 2
- Pages
- 159-163
- ISSN
- 1745-2473 (ISSN-L)
- 1745-2481
- OpenAlex
- W2897579646
- Cited by
- 287
- References
- 37
- Citations by year
- 2026: 27 · 2025: 58 · 2024: 42 · 2023: 42 · 2022: 36 · 2021: 46 · 2020: 28 · 2019: 7 · 2018: 1
- FWCI
- 11.48
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- www.springer.com/tdm (tdm)
- Locations
- Nature Physics (publishedVersion)
- 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, average-case hardness, anti-concentration, verification measures, quantum computing, computational complexity, experimental noise
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
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.