Classical and Quantum Computation
The DOI matches its Crossref record.
Abstract
Introduction Classical computation Quantum computation Solutions Elementary number theory Bibliography Index.
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
“It is now known that this problem -along with many others -is Quantum Merlin -Arthur (QMA)-complete. 79,80”
From Quantum algorithms: an overview (2016) · cites this paper as [79]
In the citing paper
“most of the available quantum processors utilize gate-based models of quantum computation34,35 for realizing desired computations.”
In the citing paper
“Despite these pessimistic beliefs, Shor discovered a scheme to reduce the effect of decoherence[63].”
From Fault-Tolerant Quantum Computation with Constant Error Rate (2008) · cites this paper as [63]
In the citing paper
“A diverse set of experimental groups worldwide have already implemented various variational quantum algorithms on their physical systems 52-59 .”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [54]
Citations
Cites
Still being checked.
Cited by
Non-Abelian anyons and topological quantum computation
Nayak, C., Simon, S. H., Stern, A., Freedman, M., & Das Sarma, S. (2008) · Reviews of Modern Physics · doi:10.1103/revmodphys.80.1083 · Cited by 6,861
Surface codes: Towards practical large-scale quantum computation
Fowler, A. G., Mariantoni, M., Martinis, J. M., & Cleland, A. N. (2012) · Physical Review A · doi:10.1103/physreva.86.032324 · Cited by 3,059
Quantum Chemistry in the Age of Quantum Computing
Cao, Y., Romero, J., Olson, J. P., Degroote, M., Johnson, P. D., Kieferová, M., Kivlichan, I. D., Menke, T., Peropadre, B., Sawaya, N. P. D., et al. (2019) · Chemical Reviews · doi:10.1021/acs.chemrev.8b00803 · Cited by 1,560
Error bounds for approximations with deep ReLU networks
Yarotsky, D. (2017) · Neural Networks · doi:10.1016/j.neunet.2017.07.002 · Cited by 1,085
Quantum algorithms: an overview
Montanaro, A. (2016) · npj Quantum Information · doi:10.1038/npjqi.2015.23 · Cited by 1,071
Universal Computation by Quantum Walk
Childs, A. M. (2009) · Physical Review Letters · doi:10.1103/physrevlett.102.180501 · Cited by 1,002
Preparation of entangled states by quantum Markov processes
Kraus, B., Büchler, H. P., Diehl, S., Kantian, A., Micheli, A., & Zoller, P. (2008) · Physical Review A · doi:10.1103/physreva.78.042307 · Cited by 760
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
The Complexity of the Local Hamiltonian Problem
Kempe, J., Kitaev, A., & Regev, O. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539704445226 · Cited by 648
Self-citationRoads towards fault-tolerant universal quantum computation
Campbell, E. T., Terhal, B. M., & Vuillot, C. (2017) · Nature · doi:10.1038/nature23460 · Cited by 596
A Modular Functor Which is Universal¶for Quantum Computation
Freedman, M. H., Larsen, M., & Wang, Z. (2002) · Communications in Mathematical Physics · doi:10.1007/s002200200645 · Cited by 573
Fault-Tolerant Quantum Computation with Constant Error Rate
Aharonov, D., & Ben-Or, M. (2008) · SIAM Journal on Computing · doi:10.1137/s0097539799359385 · Cited by 513
Characterizing quantum gates via randomized benchmarking
Magesan, E., Gambetta, J. M., & Emerson, J. (2012) · Physical Review A · doi:10.1103/physreva.85.042311 · Cited by 464
Digitized adiabatic quantum computing with a superconducting circuit
Barends, R., Shabani, A., Lamata, L., Kelly, J., Mezzacapo, A., Heras, U. L., Babbush, R., Fowler, A. G., Campbell, B., Chen, Y., et al. (2016) · Nature · doi:10.1038/nature17658 · Cited by 463
Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation
Aharonov, D., van Dam, W., Kempe, J., Landau, Z., Lloyd, S., & Regev, O. (2007) · SIAM Journal on Computing · doi:10.1137/s0097539705447323 · Cited by 457
Hand-waving and interpretive dance: an introductory course on tensor networks
Bridgeman, J. C., & Chubb, C. T. (2017) · Journal of Physics A: Mathematical and Theoretical · doi:10.1088/1751-8121/aa6dc3 · Cited by 407
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
Training Variational Quantum Algorithms Is NP-Hard
Bittel, L., & Kliesch, M. (2021) · Physical Review Letters · doi:10.1103/physrevlett.127.120502 · Cited by 398
Exact Results for Spin Dynamics and Fractionalization in the Kitaev Model
Baskaran, G., Mandal, S., & Shankar, R. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.247201 · Cited by 390
An introduction to quantum error correction and fault-tolerant quantum computation
Gottesman, D. (2010) · Proceedings of Symposia in Applied Mathematics · doi:10.1090/psapm/068/2762145 · Cited by 370
Grand Unification of Quantum Algorithms
Martyn, J. M., Rossi, Z. M., Tan, A. K., & Chuang, I. L. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.040203 · Cited by 366
Simulating Chemistry Using Quantum Computers
Kassal, I., Whitfield, J. D., Perdomo-Ortiz, A., Yung, M.-H., & Aspuru-Guzik, A. (2011) · Annual Review of Physical Chemistry · doi:10.1146/annurev-physchem-032210-103512 · Cited by 352
Moore, C., & Mertens, S. (2011) · doi:10.1093/acprof:oso/9780199233212.001.0001 · Cited by 347
Quantum algorithms for algebraic problems
Childs, A. M., & van Dam, W. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.1 · Cited by 344
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 Low-Density Parity-Check Codes
Breuckmann, N. P., & Eberhardt, J. N. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.040101 · Cited by 328
PERFECT, EFFICIENT, STATE TRANSFER AND ITS APPLICATION AS A CONSTRUCTIVE TOOL
KAY, A. (2010) · International Journal of Quantum Information · doi:10.1142/s0219749910006514 · Cited by 319
Computational complexity of projected entangled pair states
Schuch, N., Wolf, M. M., Verstraete, F., & Cirac, J. I. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.140506 · Cited by 313
Can one trust quantum simulators?
Hauke, P., Cucchietti, F. M., Tagliacozzo, L., Deutsch, I., & Lewenstein, M. (2012) · Reports on Progress in Physics · doi:10.1088/0034-4885/75/8/082401 · Cited by 315
Temme, K., Osborne, T. J., Vollbrecht, K. G., Poulin, D., & Verstraete, F. (2011) · Nature · doi:10.1038/nature09770 · Cited by 305
Modular Forms, a Computational Approach
Stein, W. (2007) · Graduate Studies in Mathematics · doi:10.1090/gsm/079 · Cited by 297
Self-consistent quantum process tomography
Merkel, S. T., Gambetta, J. M., Smolin, J. A., Poletto, S., Córcoles, A. D., Johnson, B. R., Ryan, C. A., & Steffen, M. (2013) · Physical Review A · doi:10.1103/physreva.87.062119 · Cited by 294
Decoherence-Free Subspaces and Subsystems
Lidar, D. A., & Birgitta Whaley, K. (2003) · Lecture Notes in Physics · doi:10.1007/3-540-44874-8_5 · Cited by 290
Solving strongly correlated electron models on a quantum computer
Wecker, D., Hastings, M. B., Wiebe, N., Clark, B. K., Nayak, C., & Troyer, M. (2015) · Physical Review A · doi:10.1103/physreva.92.062318 · Cited by 285
Herman, D., Googin, C., Liu, X., Sun, Y., Galda, A., Safro, I., Pistoia, M., & Alexeev, Y. (2023) · Nature Reviews Physics · doi:10.1038/s42254-023-00603-1 · Cited by 284
Halving the cost of quantum addition
Gidney, C. (2018) · Quantum · doi:10.22331/q-2018-06-18-74 · Cited by 279
Exact Correlation Functions for Dual-Unitary Lattice Models in 1 + 1 Dimensions
Bertini, B., Kos, P., & Prosen, T. (2019) · Physical Review Letters · doi:10.1103/physrevlett.123.210601 · Cited by 278
Quantum Simulation of Time-Dependent Hamiltonians and the Convenient Illusion of Hilbert Space
Poulin, D., Qarry, A., Somma, R., & Verstraete, F. (2011) · Physical Review Letters · doi:10.1103/physrevlett.106.170501 · Cited by 265
Undecidability of the spectral gap
Cubitt, T. S., Perez-Garcia, D., & Wolf, M. M. (2015) · Nature · doi:10.1038/nature16059 · Cited by 262
Schuch, N., & Verstraete, F. (2009) · Nature Physics · doi:10.1038/nphys1370 · Cited by 260
Quantum computation vs. firewalls
Harlow, D., & Hayden, P. (2013) · Journal of High Energy Physics · doi:10.1007/jhep06(2013)085 · Cited by 310
Quantum Computational Complexity of the N -Representability Problem: QMA Complete
Liu, Y.-K., Christandl, M., & Verstraete, F. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.110503 · Cited by 211
Both 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
Perspective on the Current State-of-the-Art of Quantum Computing for Drug Discovery Applications
Blunt, N. S., Camps, J., Crawford, O., Izsák, R., Leontica, S., Mirani, A., Moylett, A. E., Scivier, S. A., Sünderhauf, C., Schopf, P., et al. (2022) · Journal of Chemical Theory and Computation · doi:10.1021/acs.jctc.2c00574 · Cited by 192
Adding control to arbitrary unknown quantum operations
Zhou, X.-Q., Ralph, T. C., Kalasuwan, P., Zhang, M., Peruzzo, A., Lanyon, B. P., & O'Brien, J. L. (2011) · Nature Communications · doi:10.1038/ncomms1392 · Cited by 173
Izmaylov, A. F., Yen, T.-C., Lang, R. A., & Verteletskyi, V. (2020) · Journal of Chemical Theory and Computation · doi:10.1021/acs.jctc.9b00791 · Cited by 171
Dissipative Quantum Church-Turing Theorem
Kliesch, M., Barthel, T., Gogolin, C., Kastoryano, M., & Eisert, J. (2011) · Physical Review Letters · doi:10.1103/physrevlett.107.120501 · Cited by 154
Efficient magic state factories with a catalyzed | C C Z ⟩ to 2 | T ⟩ transformation
Gidney, C., & Fowler, A. G. (2019) · Quantum · doi:10.22331/q-2019-04-30-135 · Cited by 152
Faster quantum chemistry simulation on fault-tolerant quantum computers
Cody Jones, N., Whitfield, J. D., McMahon, P. L., Yung, M.-H., Meter, R. V., Aspuru-Guzik, A., & Yamamoto, Y. (2012) · New Journal of Physics · doi:10.1088/1367-2630/14/11/115023 · Cited by 145
Quantum Hamiltonian Complexity
Gharibian, S., Huang, Y., Landau, Z., & Shin, S. W. (2015) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000066 · Cited by 144
Alicki, R., Lidar, D. A., & Zanardi, P. (2006) · Physical Review A · doi:10.1103/physreva.73.052311 · Cited by 132
Kliuchnikov, V., Maslov, D., & Mosca, M. (2013) · Physical Review Letters · doi:10.1103/physrevlett.110.190502 · Cited by 128
Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
Ambainis, A., Childs, A. M., Reichardt, B. W., Špalek, R., & Zhang, S. (2010) · SIAM Journal on Computing · doi:10.1137/080712167 · Cited by 122
Quantum Algorithm for Spectral Measurement with a Lower Gate Count
Poulin, D., Kitaev, A., Steiger, D. S., Hastings, M. B., & Troyer, M. (2018) · Physical Review Letters · doi:10.1103/physrevlett.121.010501 · Cited by 108
Self-citationUniversal variational quantum computation
Biamonte, J. (2021) · Physical Review A · doi:10.1103/physreva.103.l030401 · Cited by 102
Brown, K. R., Clark, R. J., & Chuang, I. L. (2006) · Physical Review Letters · doi:10.1103/physrevlett.97.050504 · Cited by 98
Efficient algorithm for a quantum analogue of 2-SAT
Bravyi, S. (2011) · Contemporary Mathematics · doi:10.1090/conm/536/10552 · Cited by 98
On the Universality of the Quantum Approximate Optimization Algorithm
Morales, M. E. S., Biamonte, J., & Zimborás, Z. (2019) · arXiv · doi:10.48550/arxiv.1909.03123 · Cited by 95
Biology and medicine in the landscape of quantum advantages
Cordier, B. A., Sawaya, N. P. D., Guerreschi, G. G., & McWeeney, S. K. (2022) · Journal of The Royal Society Interface · doi:10.1098/rsif.2022.0541 · Cited by 87
Quantum-circuit design for efficient simulations of many-body quantum dynamics
Raeisi, S., Wiebe, N., & Sanders, B. C. (2012) · New Journal of Physics · doi:10.1088/1367-2630/14/10/103017 · Cited by 72
On the Hardness of Distinguishing Mixed-State Quantum Computations
Rosgen, B., & Watrous, J. (2005) · 20th Annual IEEE Conference on Computational Complexity (CCC'05) · doi:10.1109/ccc.2005.21 · Cited by 70
Measurement-based quantum computation with the toric code states
Bravyi, S., & Raussendorf, R. (2007) · Physical Review A · doi:10.1103/physreva.76.022304 · Cited by 69
Computational complexity in electronic structure
Whitfield, J. D., Love, P. J., & Aspuru-Guzik, A. (2013) · Phys. Chem. Chem. Phys. · doi:10.1039/c2cp42695a · Cited by 71
Scaling of variational quantum circuit depth for condensed matter systems
Bravo-Prieto, C., Lumbreras-Zarapico, J., Tagliacozzo, L., & Latorre, J. I. (2020) · Quantum · doi:10.22331/q-2020-05-28-272 · Cited by 66
Solving Quantum Ground-State Problems with Nuclear Magnetic Resonance
Li, Z., Yung, M.-H., Chen, H., Lu, D., Whitfield, J. D., Peng, X., Aspuru-Guzik, A., & Du, J. (2011) · Scientific Reports · doi:10.1038/srep00088 · Cited by 63
Quantum singular value decomposer
Bravo-Prieto, C., García-Martín, D., & Latorre, J. I. (2020) · Physical Review A · doi:10.1103/physreva.101.062310 · Cited by 64
The ghost in the radiation: robust encodings of the black hole interior
Kim, I., Tang, E., & Preskill, J. (2020) · Journal of High Energy Physics · doi:10.1007/jhep06(2020)031 · Cited by 63
Coherence in logical quantum channels
Iverson, J. K., & Preskill, J. (2020) · New Journal of Physics · doi:10.1088/1367-2630/ab8e5c · Cited by 61
Computational Difficulty of Finding Matrix Product Ground States
Schuch, N., Cirac, I., & Verstraete, F. (2008) · Physical Review Letters · doi:10.1103/physrevlett.100.250501 · Cited by 60
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
Self-testing of Quantum Circuits
Magniez, F., Mayers, D., Mosca, M., & Ollivier, H. (2006) · Lecture Notes in Computer Science · doi:10.1007/11786986_8 · Cited by 58
Clark, C. R., Metodi, T. S., Gasster, S. D., & Brown, K. R. (2009) · Physical Review A · doi:10.1103/physreva.79.062314 · Cited by 51
Abrupt transitions in variational quantum circuit training
Campos, E., Nasrallah, A., & Biamonte, J. (2021) · Physical Review A · doi:10.1103/physreva.103.032607 · Cited by 46
Fast quantum computation at arbitrarily low energy
Jordan, S. P. (2017) · Physical Review A · doi:10.1103/physreva.95.032305 · Cited by 40
Fast quantum modular exponentiation architecture for Shor's factoring alogrithm
Pavlidis, A., & Gizopoulos, D. (2014) · Quantum Information and Computation · doi:10.26421/qic14.7-8-8 · Cited by 38
Hamiltonian gadgets with reduced resource requirements
Cao, Y., Babbush, R., Biamonte, J., & Kais, S. (2015) · Physical Review A · doi:10.1103/physreva.91.012315 · Cited by 35
The baby universe is fine and the CFT knows it: on holography for closed universes
Antonini, S., Rath, P., Sasieta, M., Swingle, B., & Vilar López, A. (2025) · Journal of High Energy Physics · doi:10.1007/jhep12(2025)159 · Cited by 35
Computational Difficulty of Computing the Density of States
Brown, B., Flammia, S. T., & Schuch, N. (2011) · Physical Review Letters · doi:10.1103/physrevlett.107.040501 · Cited by 31
Metric Structure of the Space of Two-Qubit Gates, Perfect Entanglers and Quantum Control
Watts, P., O'Connor, M., & Vala, J. (2013) · Entropy · doi:10.3390/e15061963 · Cited by 31
Bookatz, A. D. (2014) · Quantum Information and Computation · doi:10.26421/qic14.5-6-1 · Cited by 26
Computational complexity of time-dependent density functional theory
Whitfield, J. D., Yung, M.-H., Tempel, D. G., Boixo, S., & Aspuru-Guzik, A. (2014) · New Journal of Physics · doi:10.1088/1367-2630/16/8/083035 · Cited by 15
How to factor 2048 bit RSA integers with less than a million noisy qubits
Gidney, C. (2025) · arXiv · Cited by 7
Salehi, R., Malik, A. W., Novotny, M. A., & Khan, S. U. (2026) · Scientific Reports · doi:10.1038/s41598-026-51033-9 · Cited by 1
Quantum error correction and fault tolerance: A comprehensive tutorial
Spencer, D. J., Jain, S. P., Tanggara, A., Sun, Z., Haug, T., Khu, D., & Bharti, K. (2026) · arXiv
Metadata
- Authors
- Kitaev, A., Shen, A., & Vyalyi, M.
- Affiliations
- California Institute of Technology (US)
- Independent University of Moscow (RU)
- Venue
- Graduate Studies in Mathematics
- Publisher
- American Mathematical Society
- Published
- 2002-05-31
- ISSN
- 1065-7339 (ISSN-L)
- OpenAlex
- W2084019889
- Cited by
- 1,387
- References
- 0
- Citations by year
- 2026: 40 · 2025: 85 · 2024: 85 · 2023: 85 · 2022: 68 · 2021: 93 · 2020: 74 · 2019: 72 · 2018: 58 · 2017: 46 · 2016: 49 · 2015: 62 · 2014: 51 · 2013: 59 · 2012: 58
- FWCI
- 6.61
- Type
- book
- Language
- en
- Open access
- closed
- Locations
- Graduate studies in mathematics (publishedVersion)
- CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
- 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 › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Keywords
- classical computing, quantum computing, elementary number theory, quantum algorithms, computational complexity
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.