Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/9610011

Threshold Accuracy for Quantum Computation

Emanuel H. Knill, Raymond Laflamme, Wojciech Hubert Zurek

Published Oct 8, 1996• 99 citations
arXivHTMLPDF

Abstract

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 gate has error at most $cε$. We discuss a similar concatenation technique which can be used with fault tolerant networks to achieve any desired accuracy when computing with classical initial states, provided a minimum gate accuracy can be achieved. The technique works under realistic assumptions on operational errors. These assumptions are more general than the stochastic error heuristic used in other work. Methods are proposed to account for leakage errors, a problem not previously recognized.

DOI
10.48550/arxiv.quant-ph/9610011

Related papers

Accuracy threshold for quantum computation

Emanuel H. Knill, Wojciech Hubert Zurek, Raymond Laflamme

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 error at most cffl. We discuss a similar concatenation technique which can be used with fault tolerant networks to achieve any desired accuracy when computing with classical initial states, provided a minimum gate accuracy can be achieved. The technique works under realistic assumptions on operational errors. These assumptions are more general than the stochastic error heuristic used in other work. Methods are proposed to account for leakage errors, a problem not previously recognized. 1 Introduction Three recent events are promising to make extensive quantum computations as practical as classical computations. The first is the discovery by Shor [13], Steane [15] and Calderbank et al. [4, 3] of quantum error-correcting codes email: knill@lanl.gov y laflamme@lanl.gov z whz@lanl.gov which can be used to main...

•Jan 1, 1996•72 citations

Threshold Estimate for Fault Tolerant Quantum Computation

Christof Zalka

I make a rough estimate of the accuracy threshold for fault tolerant quantum computing with concatenated codes. First I consider only gate errors and use the depolarizing channel error model. I will follow P.Shor (quant-ph/9505011) for fault tolerant error correction (FTEC) and the fault tolerant implementation of elementary operations on states encoded by the 7-qubit code. A simple computer simulation suggests a threshold for gate errors of the order ε\approx 10^{-3} or better. I also give a simple argument that the threshold for memory errors is about 10 times smaller, thus ε\approx 10^{-4}.

arXiv:quant-ph/9612028•Dec 8, 1996•37 citations

Resilient quantum computation: error models and thresholds

Emanuel Knill, Raymond Laflamme, Wojciech H. Zurek

Recent research has demonstrated that quantum computers can solve certain types of problems substantially faster than the known classical algorithms. These problems include factoring integers and certain physics simulations. Practical quantum computation requires overcoming the problems of environmental noise and operational errors, problems which appear to be much more severe than in classical computation due to the inherent fragility of quantum superpositions involving many degrees of freedom. Here we show that arbitrarily accurate quantum computations are possible provided that the error per operation is below a threshold value. The result is obtained by combining quantum error–correction, fault–tolerant state recovery, fault–tolerant encoding of operations and concatenation. It holds under physically realistic assumptions on the errors.

arXiv:quant-ph/9702058•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Jan 8, 1998•344 citations

Resilient Quantum Computation: Error Models and Thresholds

Knill, E H, Laflamme, R, Zurek, W H

Recent research has demonstrated that quantum computers can solve certain types of problems substantially faster than the known classical algorithms. These problems include factoring integers and certain physics simulations. Practical quantum computation requires overcoming the problems of environmental noise and operational errors, problems which appear to be much more severe than in classical computation due to the inherent fragility of quantum superpositions involving many degrees of freedom. Here we show that arbitrarily accurate quantum computations are possible provided that the error per operation is below a threshold value. The result is obtained by combining quantum error-correction, fault tolerant state recovery, fault tolerant encoding of operations and concatenation. It holds under physically realistic assumptions on the errors.

•Jan 1, 1997•287 citations

Quantum Mechanics

Frank Gaitan

In Chapters 2-5 we gave a detailed presentation of the theory of quantum error correction and fault-tolerant quantum computing. The stage is finally set for a proof of the accuracy threshold theorem [2-9]. As pointed out in Chapter 1, this theorem spells out the conditions under which quantum computing can be done reliably using imperfect quantum gates and in the presence of noise. The proof presented in this chapter follows Ref. [6]. Section 6.1 addresses a number of preliminary topics. It explains why a concatenated quantum error correcting code (QECC) should be used to protect the computational data when fault-tolerance is an issue; it states the principal assumptions underlying the threshold calculations presented in Section 6.2; and finally, it closes with a statement of the accuracy threshold theorem. The proof of this theorem is taken up in Section 6.2. For the error model introduced in Section 6.1, the accuracy threshold is calculated for gates in the Clifford group N(Qn), storage registers, and the Toffoli gate. The calculations make explicit use of the recursive structure of a concatenated QECC and the fault-tolerant procedures introduced in Chapter 5. The theorem is proved by showing that all three cases yield non-zero threshold values.

CRC Press eBooks•Feb 7, 2008•0 citations

Fault-Tolerant Coding for Quantum Communication

Matthias Christandl, Alexander Müller‐Hermes

Designing encoding and decoding circuits to reliably send messages over many uses of a noisy channel is a central problem in communication theory. When studying the optimal transmission rates achievable with asymptotically vanishing error it is usually assumed that these circuits can be implemented using noise-free gates. While this assumption is satisfied for classical machines in many scenarios, it is not expected to be satisfied in the near term future for quantum machines where decoherence leads to faults in the quantum gates. As a result, fundamental questions regarding the practical relevance of quantum channel coding remain open. By combining techniques from fault-tolerant quantum computation with techniques from quantum communication, we initiate the study of these questions. We introduce fault-tolerant versions of quantum capacities quantifying the optimal communication rates achievable with asymptotically vanishing total error when the encoding and decoding circuits are affected by gate errors with small probability. Our main results are threshold theorems for the classical and quantum capacity: For every quantum channel$T$and every$\epsilon >0$there exists a threshold$p(\epsilon,T)$for the gate error probability below which rates larger than$C-\epsilon $are fault-tolerantly achievable with vanishing overall communication error, where$C$denotes the usual capacity. Our results are not only relevant in communication over large distances, but also on-chip, where distant parts of a quantum computer might need to communicate under higher levels of noise than affecting the local gates.

arXiv:2009.07161•IEEE Transactions on Information Theory•Apr 21, 2022•15 citations
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 gate has error at most cεcεcε. We discuss a similar concatenation technique which can be used with fault tolerant networks to achieve any desired accuracy when computing with classical initial states, provided a minimum gate accuracy can be achieved. The technique works under realistic assumptions on operational errors. These assumptions are more general than the stochastic error heuristic used in other work. Methods are proposed to account for leakage errors, a problem not previously recognized.
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 error at most cffl. We discuss a similar concatenation technique which can be used with fault tolerant networks to achieve any desired accuracy when computing with classical initial states, provided a minimum gate accuracy can be achieved. The technique works under realistic assumptions on operational errors. These assumptions are more general than the stochastic error heuristic used in other work. Methods are proposed to account for leakage errors, a problem not previously recognized. 1 Introduction Three recent events are promising to make extensive quantum computations as practical as classical computations. The first is the discovery by Shor [13], Steane [15] and Calderbank et al. [4, 3] of quantum error-correcting codes email: knill@lanl.gov y laflamme@lanl.gov z whz@lanl.gov which can be used to main...
I make a rough estimate of the accuracy threshold for fault tolerant quantum computing with concatenated codes. First I consider only gate errors and use the depolarizing channel error model. I will follow P.Shor (quant-ph/9505011) for fault tolerant error correction (FTEC) and the fault tolerant implementation of elementary operations on states encoded by the 7-qubit code. A simple computer simulation suggests a threshold for gate errors of the order ε\approx 10^{-3} or better. I also give a simple argument that the threshold for memory errors is about 10 times smaller, thus ε\approx 10^{-4}.
Recent research has demonstrated that quantum computers can solve certain types of problems substantially faster than the known classical algorithms. These problems include factoring integers and certain physics simulations. Practical quantum computation requires overcoming the problems of environmental noise and operational errors, problems which appear to be much more severe than in classical computation due to the inherent fragility of quantum superpositions involving many degrees of freedom. Here we show that arbitrarily accurate quantum computations are possible provided that the error per operation is below a threshold value. The result is obtained by combining quantum error–correction, fault–tolerant state recovery, fault–tolerant encoding of operations and concatenation. It holds under physically realistic assumptions on the errors.
Recent research has demonstrated that quantum computers can solve certain types of problems substantially faster than the known classical algorithms. These problems include factoring integers and certain physics simulations. Practical quantum computation requires overcoming the problems of environmental noise and operational errors, problems which appear to be much more severe than in classical computation due to the inherent fragility of quantum superpositions involving many degrees of freedom. Here we show that arbitrarily accurate quantum computations are possible provided that the error per operation is below a threshold value. The result is obtained by combining quantum error-correction, fault tolerant state recovery, fault tolerant encoding of operations and concatenation. It holds under physically realistic assumptions on the errors.
In Chapters 2-5 we gave a detailed presentation of the theory of quantum error correction and fault-tolerant quantum computing. The stage is finally set for a proof of the accuracy threshold theorem [2-9]. As pointed out in Chapter 1, this theorem spells out the conditions under which quantum computing can be done reliably using imperfect quantum gates and in the presence of noise. The proof presented in this chapter follows Ref. [6]. Section 6.1 addresses a number of preliminary topics. It explains why a concatenated quantum error correcting code (QECC) should be used to protect the computational data when fault-tolerance is an issue; it states the principal assumptions underlying the threshold calculations presented in Section 6.2; and finally, it closes with a statement of the accuracy threshold theorem. The proof of this theorem is taken up in Section 6.2. For the error model introduced in Section 6.1, the accuracy threshold is calculated for gates in the Clifford group N(Qn), storage registers, and the Toffoli gate. The calculations make explicit use of the recursive structure of a concatenated QECC and the fault-tolerant procedures introduced in Chapter 5. The theorem is proved by showing that all three cases yield non-zero threshold values.
Designing encoding and decoding circuits to reliably send messages over many uses of a noisy channel is a central problem in communication theory. When studying the optimal transmission rates achievable with asymptotically vanishing error it is usually assumed that these circuits can be implemented using noise-free gates. While this assumption is satisfied for classical machines in many scenarios, it is not expected to be satisfied in the near term future for quantum machines where decoherence leads to faults in the quantum gates. As a result, fundamental questions regarding the practical relevance of quantum channel coding remain open. By combining techniques from fault-tolerant quantum computation with techniques from quantum communication, we initiate the study of these questions. We introduce fault-tolerant versions of quantum capacities quantifying the optimal communication rates achievable with asymptotically vanishing total error when the encoding and decoding circuits are affected by gate errors with small probability. Our main results are threshold theorems for the classical and quantum capacity: For every quantum channelTTTand everyϵ>0\epsilon >0ϵ>0there exists a thresholdp(ϵ,T)p(\epsilon,T)p(ϵ,T)for the gate error probability below which rates larger than$C-\epsilon arefault−tolerantlyachievablewithvanishingoverallcommunicationerror,whereare fault-tolerantly achievable with vanishing overall communication error, wherearefault−tolerantlyachievablewithvanishingoverallcommunicationerror,whereC$denotes the usual capacity. Our results are not only relevant in communication over large distances, but also on-chip, where distant parts of a quantum computer might need to communicate under higher levels of noise than affecting the local gates.