The DOI matches its Crossref record; 34 of the 34 references it cites were found in a registry or an index.
Fault-tolerant quantum computation
Open accessAbstract
It has recently been realized that use of the properties of quantum mechanics might speed up certain computations dramatically. Interest in quantum computation has since been growing. One of the main difficulties in realizing quantum computation is that decoherence tends to destroy the information in a superposition of states in a quantum computer making long computations impossible. A further difficulty is that inaccuracies in quantum state transformations throughout the computation accumulate, rendering long computations unreliable. However, these obstacles may not be as formidable as originally believed. For any quantum computation with t gates, we show how to build a polynomial size quantum circuit that tolerates O(1/log/sup c/t) amounts of inaccuracy and decoherence per gate, for some constant c; the previous bound was O(1/t). We do this by showing that operations can be performed on quantum data encoded by quantum error-correcting codes without decoding this data.
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
The Theory of Error-Correcting Codes
(1977) · North-Holland Mathematical Library · doi:10.1016/s0924-6509(08)x7030-8 · Cited by 10,760
Algorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713
Self-citationPolynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
Self-citationMixed-state entanglement and quantum error correction
Bennett, C. H., DiVincenzo, D. P., Smolin, J. A., & Wootters, W. K. (1996) · Physical Review A · doi:10.1103/physreva.54.3824 · Cited by 5,272
Scheme for reducing decoherence in quantum computer memory
Shor, P. W. (1995) · Physical Review A · doi:10.1103/physreva.52.r2493 · Cited by 4,479
Self-citationElementary gates for quantum computation
Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J. A., & Weinfurter, H. (1995) · Physical Review A · doi:10.1103/physreva.52.3457 · Cited by 4,311
Self-citationQuantum Computations with Cold Trapped Ions
Cirac, J. I., & Zoller, P. (1995) · Physical Review Letters · doi:10.1103/physrevlett.74.4091 · Cited by 3,733
Purification of Noisy Entanglement and Faithful Teleportation via Noisy Channels
Bennett, C. H., Brassard, G., Popescu, S., Schumacher, B., Smolin, J. A., & Wootters, W. K. (1996) · Physical Review Letters · doi:10.1103/physrevlett.76.722 · Cited by 2,961
Decoherence and the Transition from Quantum to Classical
Zurek, W. H. (1991) · Physics Today · doi:10.1063/1.881293 · Cited by 2,626
Quantum Theory: Concepts and Methods
Peres, A., & Ballentine, L. E. (1995) · American Journal of Physics · doi:10.1119/1.17946 · Cited by 2,561
Cited by
Fault-tolerant quantum computation by anyons
Kitaev, A. Y. (2003) · Annals of Physics · doi:10.1016/s0003-4916(02)00018-0 · Cited by 7,238
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
Self-citationQuantum State Transfer and Entanglement Distribution among Distant Nodes in a Quantum Network
Cirac, J. I., Zoller, P., Kimble, H. J., & Mabuchi, H. (1997) · Physical Review Letters · doi:10.1103/physrevlett.78.3221 · Cited by 2,215
Gottesman, D., & Chuang, I. L. (1999) · Nature · doi:10.1038/46503 · Cited by 1,860
Quantum error correction via codes over GF(4)
Calderbank, A. R., Rains, E. M., Shor, P. M., & Sloane, N. J. A. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.681315 · Cited by 1,742
Self-citationMeasurement-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
Quantum computations: algorithms and error correction
Kitaev, A. Y. (1997) · Russian Mathematical Surveys · doi:10.1070/rm1997v052n06abeh002155 · Cited by 1,424
Quantum error correction for quantum memories
Terhal, B. M. (2015) · Reviews of Modern Physics · doi:10.1103/revmodphys.87.307 · Cited by 1,354
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
Quantum computing with realistically noisy devices
Knill, E. (2005) · Nature · doi:10.1038/nature03350 · Cited by 1,184
Measurement-based quantum computation
Briegel, H. J., Browne, D. E., Dür, W., Raussendorf, R., & Van den Nest, M. (2009) · Nature Physics · doi:10.1038/nphys1157 · Cited by 1,090
Preskill, J. (1998) · Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.1998.0167 · Cited by 994
Universal quantum computation with the exchange interaction
DiVincenzo, D. P., Bacon, D., Kempe, J., Burkard, G., & Whaley, K. B. (2000) · Nature · doi:10.1038/35042541 · Cited by 924
Theory of Quantum Error Correction for General Noise
Knill, E., Laflamme, R., & Viola, L. (2000) · Physical Review Letters · doi:10.1103/physrevlett.84.2525 · Cited by 866
Quantum error correction for beginners
Devitt, S. J., Munro, W. J., & Nemoto, K. (2013) · Reports on Progress in Physics · doi:10.1088/0034-4885/76/7/076001 · Cited by 759
Fault-tolerant quantum computation with constant error
Aharonov, D., & Ben-Or, M. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258579 · Cited by 631
Roads towards fault-tolerant universal quantum computation
Campbell, E. T., Terhal, B. M., & Vuillot, C. (2017) · Nature · doi:10.1038/nature23460 · Cited by 596
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
The Heisenberg Representation of Quantum Computers
Gottesman, D. (1998) · arXiv · doi:10.48550/arxiv.quant-ph/9807006 · Cited by 489
Can quantum probability provide a new direction for cognitive modeling?
Pothos, E. M., & Busemeyer, J. R. (2013) · Behavioral and Brain Sciences · doi:10.1017/s0140525x12001525 · Cited by 440
Quantum circuits with mixed states
Aharonov, D., Kitaev, A., & Nisan, N. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276708 · Cited by 428
Quantum automata and quantum grammars
Moore, C., & Crutchfield, J. P. (2000) · Theoretical Computer Science · doi:10.1016/s0304-3975(98)00191-1 · Cited by 406
Quantum accuracy threshold for concatenated distance-3 code
Aliferis, P., Gottesman, D., & Preskill, J. (2006) · Quantum Information and Computation · doi:10.26421/qic6.2-1 · Cited by 412
Quantum computations on a topologically encoded qubit
Nigg, D., Müller, M., Martinez, E. A., Schindler, P., Hennrich, M., Monz, T., Martin-Delgado, M. A., & Blatt, R. (2014) · Science · doi:10.1126/science.1253742 · Cited by 400
Fault-tolerant control of an error-corrected qubit
Egan, L., Debroy, D. M., Noel, C., Risinger, A., Zhu, D., Biswas, D., Newman, M., Li, M., Brown, K. R., Cetina, M., et al. (2021) · Nature · doi:10.1038/s41586-021-03928-y · Cited by 348
Resilient 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
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
A Survey on Quantum Channel Capacities
Gyongyosi, L., Imre, S., & Nguyen, H. V. (2018) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2017.2786748 · Cited by 337
The ion trap quantum information processor
Steane, A. (1997) · Applied Physics B: Lasers and Optics · doi:10.1007/s003400050225 · Cited by 321
Demonstration of fault-tolerant universal quantum gate operations
Postler, L., Heuβen, S., Pogorelov, I., Rispler, M., Feldker, T., Meth, M., Marciniak, C. D., Stricker, R., Ringbauer, M., Blatt, R., et al. (2022) · Nature · doi:10.1038/s41586-022-04721-1 · Cited by 287
Quantum Error Correction with Imperfect Gates
Kitaev, A. Y. (1997) · Quantum Communication, Computing, and Measurement · doi:10.1007/978-1-4615-5923-8_19 · Cited by 214
Challenges and Opportunities of Near-Term Quantum Computing Systems
Corcoles, A. D., Kandala, A., Javadi-Abhari, A., McClure, D. T., Cross, A. W., Temme, K., Nation, P. D., Steffen, M., & Gambetta, J. M. (2020) · Proceedings of the IEEE · doi:10.1109/jproc.2019.2954005 · Cited by 203
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
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
Flag fault-tolerant error correction with arbitrary distance codes
Chamberland, C., & Beverland, M. E. (2018) · Quantum · doi:10.22331/q-2018-02-08-53 · Cited by 159
Fault-Tolerant quantum computation with constant overhead
Gottesman, D. (2014) · Quantum Information and Computation · doi:10.26421/qic14.15-16-5 · Cited by 172
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
Computational advantage of quantum random sampling
Hangleiter, D., & Eisert, J. (2023) · Reviews of Modern Physics · doi:10.1103/revmodphys.95.035001 · Cited by 145
Alicki, R., Lidar, D. A., & Zanardi, P. (2006) · Physical Review A · doi:10.1103/physreva.73.052311 · Cited by 132
Constant overhead quantum fault tolerance with quantum expander codes
Fawzi, O., Grospellier, A., & Leverrier, A. (2021) · Communications of the ACM · doi:10.1145/3434163 · Cited by 111
Encoding a magic state with beyond break-even fidelity
Gupta, R. S., Sundaresan, N., Alexander, T., Wood, C. J., Merkel, S. T., Healy, M. B., Hillenbrand, M., Jochym-O’Connor, T., Wootton, J. R., Yoder, T. J., et al. (2024) · Nature · doi:10.1038/s41586-023-06846-3 · Cited by 115
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
State readout of a trapped ion qubit using a trap-integrated superconducting photon detector
Todaro, S. L., Verma, V. B., McCormick, K. C., Allcock, D. T. C., Mirin, R. P., Wineland, D. J., Nam, S. W., Wilson, A. C., Leibfried, D., & Slichter, D. H. (2021) · Physical Review Letters · doi:10.1103/physrevlett.126.010501 · Cited by 98
How quantum brain biology can rescue conscious free will
Hameroff, S. (2012) · Frontiers in Integrative Neuroscience · doi:10.3389/fnint.2012.00093 · Cited by 95
Classical signature of quantum annealing
Smolin, J. A., & Smith, G. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00052 · Cited by 79
Fault-tolerant quantum computing with color codes
Landahl, A. J., Anderson, J. T., & Rice, P. R. (2011) · arXiv · doi:10.48550/arxiv.1108.5738 · Cited by 79
Computation by measurements: A unifying picture
Aliferis, P., & Leung, D. W. (2004) · Physical Review A · doi:10.1103/physreva.70.062314 · Cited by 75
Fast versions of Shor's quantum factoring algorithm
Zalka, C. (1998) · arXiv · doi:10.48550/arxiv.quant-ph/9806084 · Cited by 73
Fault-Tolerant Operation of a Quantum Error-Correction Code
Egan, L., Debroy, D. M., Noel, C., Risinger, A., Zhu, D., Biswas, D., Newman, M., Li, M., Brown, K. R., Cetina, M., et al. (2020) · arXiv · doi:10.48550/arxiv.2009.11482 · Cited by 65
Minimizing resource overheads for fault-tolerant preparation of encoded states of the Steane code
Goto, H. (2016) · Scientific Reports · doi:10.1038/srep19578 · Cited by 61
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
Polynomial simulations of decohered quantum computers
Aharonov, D., & Ben-Or, M. (2002) · Proceedings of 37th Conference on Foundations of Computer Science · doi:10.1109/sfcs.1996.548463 · Cited by 41
Decoder for the Triangular Color Code by Matching on a Möbius Strip
Sahay, K., & Brown, B. J. (2022) · PRX Quantum · doi:10.1103/prxquantum.3.010310 · Cited by 38
Fault-Tolerant One-Bit Addition with the Smallest Interesting Colour Code
Wang, Y., Simsek, S., Gatterman, T. M., Gerber, J. A., Gilmore, K., Gresh, D., Hewitt, N., Horst, C. V., Matheny, M., Mengle, T., et al. (2023) · arXiv · doi:10.48550/arxiv.2309.09893 · Cited by 32
Combinatorial Optimization on Gate Model Quantum Computers: A Survey
Zahedinejad, E., & Zaribafiyan, A. (2017) · arXiv · doi:10.48550/arxiv.1708.05294 · Cited by 29
Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study
Gemeinhardt, F., Garmendia, A., Wimmer, M., Weder, B., & Leymann, F. (2024) · ACM Computing Surveys · doi:10.1145/3620668 · Cited by 22
Schmidt, F., & van Loock, P. (2022) · Physical Review A · doi:10.1103/physreva.105.042427 · Cited by 20
Decoding quantum color codes with MaxSAT
Berent, L., Burgholzer, L., Derks, P.-J. H. S., Eisert, J., & Wille, R. (2024) · Quantum · doi:10.22331/q-2024-10-23-1506 · Cited by 13
Practical Quantum Error Correction with the XZZX Code and Kerr-Cat Qubits
Darmawan, A. S., Brown, B. J., Grimsmo, A. L., Tuckett, D. K., & Puri, S. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.030345 · Cited by 2
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
- Shor, P. W.
- Venue
- Proceedings of 37th Conference on Foundations of Computer Science
- Publisher
- IEEE Comput. Soc. Press
- Published
- 2002-12-23
- Pages
- 56-65
- OpenAlex
- W2167927798
- Cited by
- 892
- References
- 34
- FWCI
- 26.37
- Type
- conference paper
- 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.