Abstract
Quantum computing1—the processing of information according to the fundamental laws of physics—offers a means to solve efficiently a small but significant set of classically intractable problems. Quantum computers are based on the controlled manipulation of entangled quantum states, which are extremely sensitive to noise and imprecision; active correction of errors must therefore be implemented without causing loss of coherence. Quantum error-correction theory2,3,4,5,6,7,8,9 has made great progress in this regard, by predicting error-correcting ‘codeword’ quantum states. But the coding is inefficient and requires many quantum bits10,11,12, which results in physically unwieldy fault-tolerant quantum circuits10,11,12,13,14,15,16,17,18. Here I report a general technique for circumventing the trade-off between the achieved noise tolerance and the scale-up in computer size that is required to realize the error correction. I adapt the recovery operation (the process by which noise is suppressed through error detection and correction) to simultaneously correct errors and perform a useful measurement that drives the computation. The result is that a quantum computer need be only an order of magnitude larger than the logic device contained within it. For example, the physical scale-up factor10,11 required to factorize a thousand-digit number is reduced from 1,500 to 22, while preserving the original tolerated gate error rate (10−5) and memory noise per bit (10−7). The difficulty of realizing a useful quantum computer is therefore significantly reduced.
This is a preview of subscription content, access via your institution
Access options
Subscribe to this journal
Receive 51 print issues and online access
£199.00 per year
only £3.90 per issue
Buy this article
- Purchase on SpringerLink
- Instant access to full article PDF
Prices may be subject to local taxes which are calculated during checkout
Similar content being viewed by others
References
Steane, A. M. Quantum computing. Rep. Prog. Phys. 61, 117–173 (1998).
Steane, A. M. Introduction to quantum error correction. Phil. Trans. R. Soc. Lond. A 356, 1739–1758 ( 1998).
Shor, P. W. Scheme for reducing decoherence in quantum computer memory. Phys. Rev. A 52, R2493–R2496 ( 1995).
Steane, A. M. Error correcting codes in quantum theory. Phys. Rev. Lett. 77, 793–797 (1996).
Calderbank, A. R. & Shor, P. W. Good quantum error-correcting codes exist. Phys. Rev. A 54, 1098– 1105 (1996).
Steane, A. M. Multiple particle interference and quantum error correction. Proc. R. Soc. Lond. A 452, 2551–2577 (1996).
Knill, E. & Laflamme, R. Atheory of quantum error correcting codes. Phys. Rev. A 55, 900– 911 (1997).
Bennett, C. H., DiVencenzo, D. P., Smolin, J. A. & Wootters, W. K. Mixed state entanglement and quantum error correction. Phys. Rev. A 54, 3822–3851 ( 1996).
Knill, E. & Laflamme, R. Concatenated quantum codes.Preprint quant-ph/9608012 at 〈http://xxx.lanl.gov〉 ( 1996).
Steane, A. M. Space, time, parallelism and noise requirements for reliable quantum computing. Fortschr. Phys. 46, 443– 457 (1998).
Preskill, J. Reliable quantum computers. Proc. R. Soc. Lond. A 454 , 385–410 (1998).
Knill, E., Laflamme, R. & Zurek, W. H. Resilient quantum computation: error models and thresholds. Proc. R. Soc. Lond. A 454, 365– 384 (1998).
Shor, P. W. in Proc. 37th Symp. on Foundations of Computer Science 15– 65 (IEEE Computer Soc. Press, Los Alamitos, CA, (1996 ).
Kitaev, A. Yu. Quantum computations: algorithms and error correction. Russ. Math. Surveys 52, 1191–1249 ( 1997).
DiVencenzo, D. P. & Shor, P. W. Fault-tolerant error correction with efficient quantum codes. Phys. Rev. Lett. 77, 3260–3263 ( 1996).
Steane, A. M. Active stabilisation, quantum computation and quantum state synthesis. Phys. Rev. Lett. 78, 2252–2255 (1997).
Knill, E. Group representations, error bases and quantum codes.Preprint quant-ph/9608049 at 〈http://xxx.lanl.gov〉 (1996).
Gottesman, D. Atheory of fault-tolerant quantum computation. Phys. Rev. A 57, 127–137 (1998).
Gottesman, D. Class of quantum error correcting codes saturating the quantum Hamming bound. Phys. Rev. A 54, 1862– 1868 (1996).
Calderbank, A. R., Rains, E. M., Shor, P. W. & Sloane, N. J. A. Quantum error correction and orthogonal geometry. Phys. Rev. Lett. 78, 405–409 ( 1997).
Steane, A. M. Enlargement of Calderbank Shor Steane quantum codes. IEEE Trans. Inf. Theory (in the press); preprint quant-ph/9802061 at 〈 http://xxx.lanl.gov〉 (1998).
Gottesman, D. Fault-tolerant quantum computation with higher-dimensional systems.Preprint quant-ph/9802007 at 〈http://xxx.lanl.gov〉 ( 1998).
Knill, E. Personal communication.
Beckman, D., Chari, A. N., Devabhaktuni, S. & Preskill, J. Efficient networks for quantum factoring. Phys. Rev. A 54, 1034–1063 (1996).
Vedral, V., Barenco, A. & Ekert, A. Quantum networks for elementary arithmetic operations. Phys. Rev. A 54, 147–153 (1996).
Steane, A. M. Efficient fault-tolerant quantum computing.Preprint quant-ph/9809054 at 〈http://xxx.lanl.gov〉 (1998).
MacWilliams, F. J. & Sloane, N. J. A. The Theory of Error-correcting Codes(North-Holland, Amsterdam, ( 1996).
Grassl, M., Beth, Th. & Pellizzari, T. Codes for the quantum erasure channel. Phys. Rev. A 56, 33–38 ( 1997).
Zalka, C. Threshold estimate for fault tolerant quantum computing.Preprint quant-ph/9612028 at 〈http://xxx.lanl.gov〉 (1996).
Acknowledgements
The author is supported by The Royal Society and St Edmund Hall, Oxford.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Steane, A. Efficient fault-tolerant quantum computing. Nature 399, 124–126 (1999). https://doi.org/10.1038/20127
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1038/20127