. Our proof also applies to concatenation of higher-distance codes, and to noise models that allow faults to be correlated in space and in time. The proof uses new criteria for assessing the accuracy of fault-tolerant circuits, which are particularly conducive to the inductive analysis of recursive simulations. Our lower bound on the threshold,

\varepsilon_0 \ge 2.73\times 10^{-5}

for an adversarial independent stochastic noise model, is derived from a computer-assisted combinatorial analysis; it is the best lower bound that has been rigorously proven so far.

DOI: 10.26421/qic6.2-1

Related papers

Quantum accuracy threshold for concatenated distance-3 codes

Panos Aliferis, Daniel Gottesman, John P. Preskill

We prove a new version of the quantum threshold theorem that applies to concatenation of a quantum code that corrects only one error, and we use this theorem to derive a rigorous lower bound on the quantum accuracy threshold epsilon_0. Our proof also applies to concatenation of higher-distance codes, and to noise models that allow faults to be correlated in space and in time. The proof uses new criteria for assessing the accuracy of fault-tolerant circuits, which are particularly conducive to the inductive analysis of recursive simulations. Our lower bound on the threshold, epsilon_0 > 2.73 \times 10^{-5} for an adversarial independent stochastic noise model, is derived from a computer-assisted combinatorial analysis; it is the best lower bound that has been rigorously proven so far.We prove a new version of the quantum threshold theorem that applies to concatenation of a quantum code that corrects only one error, and we use this theorem to derive a rigorous lower bound on the quantum accuracy threshold epsilon_0. Our proof also applies to concatenation of higher-distance codes, and to noise models that allow faults to be correlated in space and in time. The proof uses new criteria for assessing the accuracy of fault-tolerant circuits, which are particularly conducive to the inductive analysis of recursive simulations. Our lower bound on the threshold, epsilon_0 > 2.73 \times 10^{-5} for an adversarial independent stochastic noise model, is derived from a computer-assisted combinatorial analysis; it is the best lower bound that has been rigorously proven so far.

arXiv:quant-ph/0504218Apr 28, 200584 citations

Accuracy threshold for postselected quantum computation

Panos Aliferis, Daniel Gottesman, John P. Preskill

We prove an accuracy threshold theorem for fault-tolerant quantum computation based on error detection and postselection. Our proof provides a rigorous foundation for the scheme suggested by Knill, in which preparation circuits for ancilla states are protected by a concatenated error-detecting code and the preparation is aborted if an error is detected. The proof applies to independent stochastic noise but (in contrast to proofs of the quantum accuracy threshold theorem based on concatenated error-correcting codes) not to strongly-correlated adversarial noise. Our rigorously established lower bound on the accuracy threshold, $1.04\times 10^{-3}$ , is well below Knill's numerical estimates.We prove an accuracy threshold theorem for fault-tolerant quantum computation based on error detection and postselection. Our proof provides a rigorous foundation for the scheme suggested by Knill, in which preparation circuits for ancilla states are protected by a concatenated error-detecting code and the preparation is aborted if an error is detected. The proof applies to independent stochastic noise but (in contrast to proofs of the quantum accuracy threshold theorem based on concatenated error-correcting codes) not to strongly-correlated adversarial noise. Our rigorously established lower bound on the accuracy threshold, $1.04\times 10^{-3}$, is well below Knill's numerical estimates.

arXiv:quant-ph/0703264Quantum Information and ComputationMar 1, 200895 citations

Quantum accuracy threshold for concatenated distance-3 codes

AliferisPanos, GottesmanDaniel, PreskillJohn

Quantum Information and ComputationMar 1, 200619 citations

Quantum accuracy threshold for distance-5 codes

Omar. Khalid

A quantum computer can only solve classically intractable problems like factoring large integers if it can perform quantum computations scalably. The minimum accuracy required among the components of a quantum computer to perform scalable computation is called the quantum accuracy threshold, epsilon 0. We explore the accuracy threshold for Calderbank-Shor-Steane codes of distance 5. Our accuracy thresholds are based on the threshold theorem proven by Aliferis et al. [3]. Their threshold theorem is applicable to concatenated codes and can be used to derive a rigorous lower bound on the threshold. In this thesis we consider degenerate codes with parameters [[17,1,5]] and [[19,1,5]], and a non-degenerate [[21,1,5]] code. For each code we design a set of logical operations sufficient to perform universal computation. We estimate the thresholds using simulation tools for an independent stochastic error model. Our simulations incorporate randomized sampling techniques to estimate the number of ways our largest logical operation can fail. A lower bound of epsilon0 ≥ 3.624 x 10-5 is derived for the [[17,1,5]] code.A quantum computer can only solve classically intractable problems like factoring large integers if it can perform quantum computations scalably. The minimum accuracy required among the components of a quantum computer to perform scalable computation is called the quantum accuracy threshold, epsilon 0. We explore the accuracy threshold for Calderbank-Shor-Steane codes of distance 5. Our accuracy thresholds are based on the threshold theorem proven by Aliferis et al. [3]. Their threshold theorem is applicable to concatenated codes and can be used to derive a rigorous lower bound on the threshold. In this thesis we consider degenerate codes with parameters [[17,1,5]] and [[19,1,5]], and a non-degenerate [[21,1,5]] code. For each code we design a set of logical operations sufficient to perform universal computation. We estimate the thresholds using simulation tools for an independent stochastic error model. Our simulations incorporate randomized sampling techniques to estimate the number of ways our largest logical operation can fail. A lower bound of epsilon0 ≥ 3.624 x 10-5 is derived for the [[17,1,5]] code.

Jan 1, 20060 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.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 eBooksFeb 7, 20080 citations

Fault-tolerance threshold for a distance-three quantum code

Ben W. Reichardt

The quantum error threshold is the highest (model-dependent) noise rate which we can tolerate and still quantum-compute to arbitrary accuracy. Although noise thresholds are frequently estimated for the Steane seven-qubit, distance-three quantum code, there has been no proof that a constant threshold even exists for distance-three codes. We prove the existence of a constant threshold. The proven threshold is well below estimates, based on simulations and analytic models, of the true threshold, but at least it is now known to be positive.The quantum error threshold is the highest (model-dependent) noise rate which we can tolerate and still quantum-compute to arbitrary accuracy. Although noise thresholds are frequently estimated for the Steane seven-qubit, distance-three quantum code, there has been no proof that a constant threshold even exists for distance-three codes. We prove the existence of a constant threshold. The proven threshold is well below estimates, based on simulations and analytic models, of the true threshold, but at least it is now known to be positive.

arXiv:quant-ph/0509203Sep 28, 20058 citations

\varepsilon_0

\varepsilon_0 \ge 2.73\times 10^{-5}

for an adversarial independent stochastic noise model, is derived from a computer-assisted combinatorial analysis; it is the best lower bound that has been rigorously proven so far.

1.04\times 10^{-3}

, is well below Knill's numerical estimates.