The DOI matches its Crossref record; 71 of the 71 references it cites were found in a registry or an index.
Anticoncentration theorems for schemes showing a quantum speedup
Open accessAbstract
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.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Figures




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.
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
Exploring 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
Research works printed but not linked: 6
- T. Kapourniotis and A. Datta, (2017), arXiv:1703.09568. · arXiv
- G. Kuperberg, Theory of Computing 11, 183 (2015). · doi:10.4086/toc.2015.v011a006
- A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, (2018), arXiv:1803.04402. · arXiv
- M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information, Cambridge Series on Information and the Natural Sciences (Cambridge University Press, 2000).
- J. Eisert, M. Friesdorf, and C. Gogolin, Nature Phys 11, 124 (2015), arXiv:1408.5148. · arXiv
- S. Aaronson and L. Chen, (2016), arXiv:1612.05903. · 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 254
Harrow, A. W., & Mehraban, S. A. (2023) · Communications in Mathematical Physics · doi:10.1007/s00220-023-04675-z · Cited by 193
Theory of Quantum System Certification
Kliesch, M., & Roth, I. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.010201 · Cited by 169
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Anticoncentration theorems for schemes showing a quantum speedup. https://app.cochat.ai/papers/10.22331/q-2018-05-22-65
- The paper
- Hangleiter, D., Bermejo-Vega, J., Schwarz, M., & Eisert, J. (2018). Anticoncentration theorems for schemes showing a quantum speedup. Quantum. https://doi.org/10.22331/q-2018-05-22-65
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.