Anticoncentration theorems for schemes showing a quantum speedup
Open accessThe DOI matches its Crossref record; 73 of the 73 references it cites were found in a registry or an index.
Abstract
One of the main milestones in quantum information science is to realise quantum devices that exhibit an exponential computational advantage over classical ones without being universal quantum computers, a state of affairs dubbed quantum speedup, or sometimes "quantum computational supremacy". The known schemes heavily rely on mathematical assumptions that are plausible but unproven, prominently results on anticoncentration of random prescriptions. In this work, we aim at closing the gap by proving two anticoncentration theorems and accompanying hardness results, one for circuit-based schemes, the other for quantum quench-type schemes for quantum simulations. Compared to the few other known such results, these results give rise to a number of comparably simple, physically meaningful and resource-economical schemes showing a quantum speedup in one and two spatial dimensions. At the heart of the analysis are tools of unitary designs and random circuits that allow us to conclude that universal random circuits anticoncentrate as well as an embedding of known circuit-based schemes in a 2D translation-invariant architecture.
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
Figures




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
“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 [99]
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
Colloquium: Nonequilibrium dynamics of closed interacting quantum systems
Polkovnikov, A., Sengupta, K., Silva, A., & Vengalattore, M. (2011) · Reviews of Modern Physics · doi:10.1103/revmodphys.83.863 · Cited by 2,562
Haake, F. (2010) · Springer Series in Synergetics · doi:10.1007/978-3-642-05428-0 · Cited by 2,006
Gottesman, D., & Chuang, I. L. (1999) · Nature · doi:10.1038/46503 · Cited by 1,860
Measurement-based quantum computation on cluster states
Raussendorf, R., Browne, D. E., & Briegel, H. J. (2003) · Physical Review A · doi:10.1103/physreva.68.022312 · Cited by 1,655
Strengths and Weaknesses of Quantum Computing
Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300933 · Cited by 1,470
Quantum computations: algorithms and error correction
Kitaev, A. Y. (1997) · Russian Mathematical Surveys · doi:10.1070/rm1997v052n06abeh002155 · Cited by 1,424
Classical and Quantum Computation
Kitaev, A., Shen, A., & Vyalyi, M. (2002) · Graduate Studies in Mathematics · doi:10.1090/gsm/047 · Cited by 1,387
Quantum many-body systems out of equilibrium
Eisert, J., Friesdorf, M., & Gogolin, C. (2015) · Nature Physics · doi:10.1038/nphys3215 · Cited by 1,255
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
Trotzky, S., Chen, Y.-A., Flesch, A., McCulloch, I. P., Schollwöck, U., Eisert, J., & Bloch, I. (2012) · Nature Physics · doi:10.1038/nphys2232 · Cited by 1,058
Self-citationExploring the many-body localization transition in two dimensions
Choi, J.-Y., Hild, S., Zeiher, J., Schauß, P., Rubio-Abadal, A., Yefsah, T., Khemani, V., Huse, D. A., Bloch, I., & Gross, C. (2016) · Science · doi:10.1126/science.aaf8834 · Cited by 979
Fault-tolerant quantum computation
Shor, P. W. (2002) · Proceedings of 37th Conference on Foundations of Computer Science · doi:10.1109/sfcs.1996.548464 · Cited by 892
Exact and approximate unitary 2-designs and their application to fidelity estimation
Dankert, C., Cleve, R., Emerson, J., & Livine, E. (2009) · Physical Review A · doi:10.1103/physreva.80.012304 · Cited by 685
Some connections between nonuniform and uniform complexity classes
Karp, R. M., & Lipton, R. J. (1980) · Proceedings of the twelfth annual ACM symposium on Theory of computing - STOC '80 · doi:10.1145/800141.804678 · Cited by 577
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
Local Random Quantum Circuits are Approximate Polynomial-Designs
Brandão, F. G. S. L., Harrow, A. W., & Horodecki, M. (2016) · Communications in Mathematical Physics · doi:10.1007/s00220-016-2706-8 · Cited by 404
Evenly distributed unitaries: On the structure of unitary designs
Gross, D., Audenaert, K., & Eisert, J. (2007) · Journal of Mathematical Physics · doi:10.1063/1.2716992 · Cited by 358
Self-citationResilient quantum computation: error models and thresholds
Knill, E., Laflamme, R., & Zurek, W. H. (1998) · Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.1998.0166 · Cited by 346
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
Quantum computing, postselection, and probabilistic polynomial-time
Aaronson, S. (2005) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2005.1546 · Cited by 311
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
Quantum computing and the entanglement frontier
Preskill, J. (2012) · arXiv · doi:10.48550/arxiv.1203.5813 · Cited by 308
Average-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
Zyczkowski, K., & Kus, M. (1994) · Journal of Physics A: Mathematical and General · doi:10.1088/0305-4470/27/12/028 · Cited by 272
Universal Fault-Tolerant Quantum Computation with Only Transversal Gates and Error Correction
Paetznick, A., & Reichardt, B. W. (2013) · Physical Review Letters · doi:10.1103/physrevlett.111.090505 · Cited by 242
Pseudo-Random Unitary Operators for Quantum Information Processing
Emerson, J., Weinstein, Y. S., Saraceno, M., Lloyd, S., & Cory, D. G. (2003) · Science · doi:10.1126/science.1090790 · Cited by 233
Complexity-Theoretic Foundations of Quantum Supremacy Experiments
Aaronson, S., & Chen, L. (2016) · arXiv · doi:10.48550/arxiv.1612.05903 · Cited by 218
The Computational Complexity of Linear OpticsPreprint
Aaronson, S., & Arkhipov, A. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1011.3245 · Cited by 210
The Clifford group fails gracefully to be a unitary 4-designPreprint
Zhu, H., Kueng, R., Grassl, M., & Gross, D. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1609.08172 · Cited by 200
The complexity of approximate counting
Stockmeyer, L. (1983) · Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC '83 · doi:10.1145/800061.808740 · Cited by 196
A new universal and fault-tolerant quantum basis
Boykin, P. O., Mor, T., Pulver, M., Roychowdhury, V., & Vatan, F. (2000) · Information Processing Letters · doi:10.1016/s0020-0190(00)00084-3 · Cited by 194
Emergence of coherence and the dynamics of quantum phase transitions
Braun, S., Friesdorf, M., Hodgman, S. S., Schreiber, M., Ronzheimer, J. P., Riera, A., del Rey, M., Bloch, I., Eisert, J., & Schneider, U. (2015) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1408861112 · Cited by 193
Self-citationBoth Toffoli and Controlled-NOT need little help to universal quantum computing
Shi, Y.-Y. (2003) · Quantum Information and Computation · doi:10.26421/qic3.1-7 · Cited by 193
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
How to generate random matrices from the classical compact groups
Mezzadri, F. (2006) · arXiv (Cornell University) · doi:10.48550/arxiv.math-ph/0609050 · Cited by 185
Quantum sampling problems, BosonSampling and quantum supremacy
Lund, A. P., Bremner, M. J., & Ralph, T. C. (2017) · npj Quantum Information · doi:10.1038/s41534-017-0018-2 · Cited by 183
Impagliazzo, R., & Paturi, R. (2003) · Proceedings. Fourteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference) (Cat.No.99CB36317) · doi:10.1109/ccc.1999.766282 · Cited by 159
Exponential Time Complexity of the Permanent and the Tutte Polynomial
Dell, H., Husfeldt, T., Marx, D., Taslaman, N., & Wahlén, M. (2014) · ACM Transactions on Algorithms · doi:10.1145/2635812 · Cited by 140
Universal quantum computation with metaplectic anyons
Cui, S. X., & Wang, Z. (2015) · Journal of Mathematical Physics · doi:10.1063/1.4914941 · Cited by 135
Composed ensembles of random unitary matrices
Pozniak, M., Zyczkowski, K., & Kus, M. (1998) · Journal of Physics A: Mathematical and General · doi:10.1088/0305-4470/31/3/016 · Cited by 128
Adaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin Games
Terhal, B. M., & DiVincenzo, D. P. (2004) · Quantum Information and Computation · doi:10.26421/qic4.2-5 · Cited by 107
Architectures for Quantum Simulation Showing a Quantum Speedup
Bermejo-Vega, J., Hangleiter, D., Schwarz, M., Raussendorf, R., & Eisert, J. (2018) · Physical Review X · doi:10.1103/physrevx.8.021010 · Cited by 99
Self-citationThreshold Accuracy for Quantum Computation
Knill, E., Laflamme, R., & Zurek, W. (1996) · arXiv · doi:10.48550/arxiv.quant-ph/9610011 · Cited by 99
Quantum Supremacy for Simulating a Translation-Invariant Ising Spin Model
Gao, X., Wang, S.-T., & Duan, L.-M. (2017) · Physical Review Letters · doi:10.1103/physrevlett.118.040502 · Cited by 93
Nash, J. F., Rassias, M. T., & Publishing, S. I. (2016) · Springer eBooks · doi:10.1007/978-3-319-32162-2 · Cited by 90
Both Toffoli and Controlled-NOT need little help to do universal quantum computation
Shi, Y. (2002) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0205115 · Cited by 89
Mixing Properties of Stochastic Quantum Hamiltonians
Onorati, E., Buerschaper, O., Kliesch, M., Brown, W., Werner, A. H., & Eisert, J. (2017) · Communications in Mathematical Physics · doi:10.1007/s00220-017-2950-6 · Cited by 88
Self-citationOn Universal and Fault-Tolerant Quantum Computing
Boykin, P. O., Mor, T., Pulver, M., Roychowdhury, V., & Vatan, F. (1999) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9906054 · Cited by 79
How to efficiently select an arbitrary Clifford group element
Koenig, R., & Smolin, J. A. (2014) · Journal of Mathematical Physics · doi:10.1063/1.4903507 · Cited by 72
Direct certification of a class of quantum simulations
Hangleiter, D., Kliesch, M., Schwarz, M., & Eisert, J. (2017) · Quantum Science and Technology · doi:10.1088/2058-9565/2/1/015004 · Cited by 68
Self-citationEfficient synthesis of probabilistic quantum circuits with fallback
Bocharov, A., Roetteler, M., & Svore, K. M. (2015) · Physical Review A · doi:10.1103/physreva.91.052317 · Cited by 59
Commuting quantum circuits and complexity of Ising partition functions
Fujii, K., & Morimae, T. (2017) · New Journal of Physics · doi:10.1088/1367-2630/aa5fdb · Cited by 48
On the simulation of quantum circuits
Jozsa, R. (2006) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0603163 · Cited by 48
Morimae, T. (2017) · Physical Review A · doi:10.1103/physreva.96.040302 · Cited by 46
Boson-Sampling in the light of sample complexity
Gogolin, C., Kliesch, M., Aolita, L., & Eisert, J. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1306.3995 · Cited by 40
Self-citationGenerating a state t-design by diagonal quantum circuits
Nakata, Y., Koashi, M., & Murao, M. (2014) · New Journal of Physics · doi:10.1088/1367-2630/16/5/053043 · Cited by 38
Simulating Quantum Circuits with Sparse Output DistributionsPreprint
Schwarz, M., & den Nest, M. V. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1310.6749 · Cited by 38
Self-citationMiller, J., Sanders, S. K., & Miyake, A. (2017) · Physical Review A · doi:10.1103/physreva.96.062320 · Cited by 35
Quantum pseudorandomness from cluster-state quantum computation
Brown, W., Weinstein, Y. S., & Viola, L. (2008) · Physical Review A · doi:10.1103/physreva.77.040303 · Cited by 24
Strengths and Weaknesses of Quantum Computing
Bennett, C. H., Bernstein, E., Brassard, G., et al. (1997) · doi:10.48550/arxiv.quant-ph/9701001 · 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 21
Matrix-element distributions as a signature of entanglement generation
Weinstein, Y. S., & Hellberg, C. S. (2005) · Physical Review A · doi:10.1103/physreva.72.022331 · Cited by 20
Near-linear constructions of exact unitary 2-designsPreprint
Cleve, R., Leung, D., Liu, L., et al. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1501.04592 · Cited by 14
Quantum Computing, Postselection, and Probabilistic Polynomial-TimePreprint
Aaronson, S. (2004) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0412187 · Cited by 9
The complexity of approximating complex-valued Ising and Tutte partition functionsPreprint
Goldberg, L. A., & Guo, H. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1409.5627 · Cited by 7
Fault-tolerant quantum computationPreprint
Shor, P. W. (1996) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9605011 · Cited by 7
Adaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin GamesPreprint
Terhal, B. M., & Divincenzo, D. P. (2002) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0205133 · Cited by 4
Beyond NP: the work and legacy of Larry Stockmeyer
Fortnow, L. (2005) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1060590.1060609 · Cited by 3
Classical simulation complexity of extended Clifford circuitsPreprint
Jozsa, R., & den Nest, M. V. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1305.6190 · Cited by 2
Probing the relaxation towards equilibrium in an isolated strongly correlated 1D Bose gasPreprint
Trotzky, S., Chen, Y.-A., Flesch, A., et al. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1101.2659
BosonSampling Is Far From UniformPreprint
Aaronson, S., & Arkhipov, A. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1309.7460
A blueprint for demonstrating quantum supremacy with superconducting qubitsPreprint
Neill, C., Roushan, P., Kechedzhi, K., et al. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1709.06678
Exploring the many-body localization transition in two dimensions
Choi, J.-Y., Hild, S., Zeiher, J., et al. (2016) · Max Planck Digital Library · doi:10.48550/arxiv.1604.04178
Research works printed but not linked: 5
- 16. T. Kapourniotis and A. Datta, (2017), arXiv:1703.09568 . · arXiv
- 26. G. Kuperberg, Theory of Computing 11, 183 (2015). · doi:10.4086/toc.2015.v011a006
- 28. A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, (2018), arXiv:1803.04402 . · arXiv
- 51. M. A. Nielsen and I. L. Chuang, Quantum com- putation and quantum information, Cambridge Series on Information and the Natural Sciences (Cambridge University Press, 2000).
- 59. J. Eisert, M. Friesdorf, and C. Gogolin, Nature Phys 11, 124 (2015), arXiv:1408.5148 . · arXiv
Cited by
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 .”
MethodSelf-citationOn the complexity and verification of quantum random circuit sampling
Bouland, A., Fefferman, B., Nirkhe, C., & Vazirani, U. (2019) · Nature Physics · doi:10.1038/s41567-018-0318-2 · Cited by 287
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 466
Harrow, A. W., & Mehraban, S. (2023) · Communications in Mathematical Physics · doi:10.1007/s00220-023-04675-z · Cited by 126
Theory of Quantum System Certification
Kliesch, M., & Roth, I. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.010201 · Cited by 139
Metadata
- Authors
- Hangleiter, D., Bermejo-Vega, J., Schwarz, M., & Eisert, J.
- Affiliations
- Freie Universität Berlin (DE)
- Venue
- Quantum
- Published
- 2018-05-22
- Volume
- 2
- Pages
- 65
- ISSN
- 2521-327X (ISSN-L)
- OpenAlex
- W2756364467
- Cited by
- 58
- References
- 49
- Citations by year
- 2026: 8 · 2025: 12 · 2024: 7 · 2023: 7 · 2022: 7 · 2021: 7 · 2020: 4 · 2019: 5 · 2018: 1
- FWCI
- 2.39
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Locations
- Quantum (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion)
- arXiv (Cornell University) (cc-by)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Keywords
- anti-concentration, quantum advantage, random circuits, unitary designs, quantum quench, quantum simulation, hardness results, two-dimensional quantum systems
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.