The DOI matches its Crossref record; 42 of the 42 references it cites were found in a registry or an index.
Quantum advantage with shallow circuits
Open accessAbstract
Quantum outperforms classical: Quantum computers are expected to be better at solving certain computational problems than classical computers. This expectation is based on (well-founded) conjectures in computational complexity theory, but rigorous comparisons between the capabilities of quantum and classical algorithms are difficult to perform. Bravyi et al. proved theoretically that whereas the number of “steps” needed by parallel quantum circuits to solve certain linear algebra problems was independent of the problem size, this number grew logarithmically with size for analogous classical circuits (see the Perspective by Montanaro). This so-called quantum advantage stems from the quantum correlations present in quantum circuits that cannot be reproduced in analogous classical circuits. Science , this issue p. 308 ; see also p. 289
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
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.
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
On the Einstein Podolsky Rosen paradox
Bell, J. S. (1964) · Physics Physique Fizika · doi:10.1103/physicsphysiquefizika.1.195 · Cited by 12,252
Raussendorf, R., & Briegel, H. J. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.5188 · Cited by 4,477
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
Rapid solution of problems by quantum computation
Deutsch, D., & Jozsa, R. (1992) · Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences · doi:10.1098/rspa.1992.0167 · Cited by 2,700
Bell’s theorem without inequalities
Greenberger, D. M., Horne, M. A., Shimony, A., & Zeilinger, A. (1990) · American Journal of Physics · doi:10.1119/1.16243 · Cited by 2,404
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · Cited by 2,371
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
Improved simulation of stabilizer circuits
Aaronson, S., & Gottesman, D. (2004) · Physical Review A · doi:10.1103/physreva.70.052328 · Cited by 1,515
Bernstein, E., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300921 · Cited by 1,503
Extreme quantum entanglement in a superposition of macroscopically distinct states
Mermin, N. D. (1990) · Physical Review Letters · doi:10.1103/physrevlett.65.1838 · Cited by 1,482 · cited 2×
“The proof exploits quantum nonlocality – a form of correlation present in the measurement statistics of entangled quantum states that cannot be reproduced by local hidden variable models [18, 19] even if a limited amount of communication is allowed [20].”
BackgroundError Mitigation for Short-Depth Quantum Circuits
Temme, K., Bravyi, S., & Gambetta, J. M. (2017) · Physical Review Letters · doi:10.1103/physrevlett.119.180509 · Cited by 1,379
Self-citationBernstein, 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
Characterizing 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
Quantum algorithms: an overview
Montanaro, A. (2016) · npj Quantum Information · doi:10.1038/npjqi.2015.23 · Cited by 1,071
Multiparty entanglement in graph states
Hein, M., Eisert, J., & Briegel, H. J. (2004) · Physical Review A · doi:10.1103/physreva.69.062311 · Cited by 915
Quantum Walk Algorithm for Element Distinctness
Ambainis, A. (2007) · SIAM Journal on Computing · doi:10.1137/s0097539705447311 · Cited by 703
Efficient Variational Quantum Simulator Incorporating Active Error Minimization
Li, Y., & Benjamin, S. C. (2017) · Physical Review X · doi:10.1103/physrevx.7.021050 · Cited by 686
A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits
Amy, M., Maslov, D., Mosca, M., & Roetteler, M. (2013) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2013.2244643 · Cited by 549 · cited 2×
“Each CCZ gate can then be decomposed exactly as a product of (a constant number of) one- and two-qubit gates from the Clifford+T gate set [36].”
BackgroundMethodComplexity-Theoretic Foundations of Quantum Supremacy ExperimentsPreprint
Aaronson, S., & Chen, L. (2016) · arXiv (Cornell University) · doi:10.14288/1.0343134 · Cited by 400
Fast Parallel Matrix Inversion Algorithms
Csanky, L. (1976) · SIAM Journal on Computing · doi:10.1137/0205040 · Cited by 397
Quantum Supremacy through the Quantum Approximate Optimization Algorithm
Farhi, E., & Harrow, A. W. (2016) · arXiv · doi:10.48550/arxiv.1602.07674 · Cited by 331
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
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
BQP and the polynomial hierarchy
Aaronson, S. (2010) · Proceedings of the forty-second ACM symposium on Theory of computing · doi:10.1145/1806689.1806711 · Cited by 226
Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes
Bombín, H. (2015) · New Journal of Physics · doi:10.1088/1367-2630/17/8/083002 · Cited by 217
Fast parallel circuits for the quantum Fourier transform
Cleve, R., & Watrous, J. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892140 · Cited by 215
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
Quantum Communication Complexity
Brassard, G. (2003) · Foundations of Physics · doi:10.1023/a:1026009100467 · Cited by 186
Parallel Quantum Computation and Quantum Codes
Moore, C., & Nilsson, M. (2001) · SIAM Journal on Computing · doi:10.1137/s0097539799355053 · Cited by 173
Fault-Tolerant quantum computation with constant overhead
Gottesman, D. (2014) · Quantum Information and Computation · doi:10.26421/qic14.15-16-5 · Cited by 172
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 171
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 122
Quantum communication and complexity
de Wolf, R. (2002) · Theoretical Computer Science · doi:10.1016/s0304-3975(02)00377-8 · Cited by 114
Quantum Supremacy for Simulating a Translation-Invariant Ising Spin Model
Gao, X., Wang, S.-T., & Duan, L. (2017) · Physical Review Letters · doi:10.1103/physrevlett.118.040502 · Cited by 98
Extractors for Circuit Sources
Viola, E. (2011) · SIAM Journal on Computing · doi:10.1109/focs.2011.20 · Cited by 72
Computational Depth Complexity of Measurement-Based Quantum Computation
Browne, D. E., Kashefi, E., & Perdrix, S. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-18073-6_4 · Cited by 62
Local Hamiltonians Whose Ground States Are Hard to Approximate
Eldar, L., & Harrow, A. W. (2017) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2017.46 · Cited by 58
Quantum Fanout is PowerfulPreprint
Høyer, P., & Špalek, R. (2005) · Theory of Computing · Cited by 51
Fault-Tolerant Quantum Computation with Constant OverheadPreprint
Gottesman, D. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1310.2984 · Cited by 35
Modeling Pauli measurements on graph states with nearest-neighbor classical communication
Barrett, J., Caves, C. M., Eastin, B., Elliott, M., & Pironio, S. (2007) · Physical Review A · doi:10.1103/physreva.75.012103 · Cited by 31
Rötteler, M. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03816-7_56 · Cited by 26
How Long Can a Quantum Memory Withstand Depolarizing Noise?
Pastawski, F., Kay, A., Schuch, N., & Cirac, J. I. (2009) · Physical Review Letters · doi:10.1103/physrevlett.103.080501 · Cited by 22
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
Machine learning & artificial intelligence in the quantum domain: a review of recent progress
Dunjko, V., & Briegel, H. J. (2018) · Reports on Progress in Physics · doi:10.1088/1361-6633/aab406 · Cited by 1,055
Materials challenges and opportunities for quantum computing hardware
de Leon, N. P., Itoh, K. M., Kim, D., Mehta, K. K., Northup, T. E., Paik, H., Palmer, B. S., Samarth, N., Sangtawesin, S., & Steuerman, D. W. (2021) · Science · doi:10.1126/science.abb2823 · Cited by 710
A Survey on quantum computing technology
Gyongyosi, L., & Imre, S. (2019) · Computer Science Review · doi:10.1016/j.cosrev.2018.11.002 · Cited by 646
Quantum computing: A taxonomy, systematic review and future directions
Gill, S. S., Kumar, A., Singh, H., Singh, M., Kaur, K., Usman, M., & Buyya, R. (2022) · Software: Practice and Experience · doi:10.1002/spe.3039 · Cited by 476
Metadata
- Authors
- Bravyi, S., Gosset, D., & König, R.
- Venue
- Science
- Published
- 2018-10-19
- Volume
- 362
- Issue
- 6412
- Pages
- 308-311
- ISSN
- 0036-8075 (ISSN-L)
- 1095-9203
- OpenAlex
- W2604467189
- Cited by
- 406
- References
- 42
- FWCI
- 21.92
- Type
- journal article
- Language
- en
- Open access
- green
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.