Abstract
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.
Keywords
Quantum computerQuantum error correctionQuantum algorithmQuantum circuitQuantum operationComputer scienceQuantum decoherenceQuantum informationComputationQuantum networkQuantum capacityTheoretical computer scienceQuantumQuantum mechanicsAlgorithmOpen quantum systemPhysics
Affiliated Institutions
Related Publications
Scheme for reducing decoherence in quantum computer memory
Recently, it was realized that use of the properties of quantum mechanics might speed up certain computations dramatically. Interest has since been growing in the area of quantu...
Noisy intermediate-scale quantum algorithms
A universal fault-tolerant quantum computer that can efficiently solve problems such as integer factorization and unstructured database search requires millions of qubits with l...
Quantum Mechanics Helps in Searching for a Needle in a Haystack
Quantum mechanics can speed up a range of search applications over unsorted data. For example imagine a phone directory containing N names arranged in completely random order. T...
Accuracy threshold for quantum computation
We have previously [11] shown that for quantum memories and quantum communication, a state can be transmitted over arbitrary distances with error ffl provided each gate has erro...
Threshold Accuracy for Quantum Computation
We have previously (quant-ph/9608012) shown that for quantum memories and quantum communication, a state can be transmitted over arbitrary distances with error $ε$ provided each...
Publication Info
- Year
- 2002
- Type
- article
- Pages
- 56-65
- Citations
- 861
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
861
OpenAlex
62
Influential
298
CrossRef
Cite This
Peter W. Shor
(2002).
Fault-tolerant quantum computation.
Proceedings of 37th Conference on Foundations of Computer Science
, 56-65.
https://doi.org/10.1109/sfcs.1996.548464
Identifiers
- DOI
- 10.1109/sfcs.1996.548464
- arXiv
- quant-ph/9605011