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:0705.4360 · Physical Review A

Bounding fault-tolerant thresholds for purification and quantum computation

Alastair Kay

Published May 19, 2008• 5 citations
arXivHTMLPDF

Abstract

In this paper, we place bounds on when it is impossible to purify a noisy two-qubit state if all the gates used in the purification protocol are subject to adversarial, local, independent noise. It is found that the gate operations must be subject to less than 5.3% error. An existing proof that purification is equivalent to error correction is used to show that this bound can also be applied to concatenated error correcting codes in the presence of noisy gates, and hence gives a limit to the tolerable error rate for a fault-tolerant quantum computer formed by concatenation. This is shown to apply also to the case where error detection and postselection, as proposed by Knill, is used to enhance the threshold. We demonstrate the trade-off between gate and environmentally induced faulty rotations and qubit loss errors.

DOI
10.1103/physreva.77.052319

Related papers

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.

arXiv:quant-ph/0703264•Quantum Information and Computation•Mar 1, 2008•125 citations

Thresholds for Universal Concatenated Quantum Codes

Christopher Chamberland, Tomas Jochym-O’Connor, Raymond Laflamme

Quantum error correction and fault tolerance make it possible to perform quantum computations in the presence of imprecision and imperfections of realistic devices. An important question is to find the noise rate at which errors can be arbitrarily suppressed. By concatenating the 7-qubit Steane and 15-qubit Reed-Muller codes, the 105-qubit code enables a universal set of fault-tolerant gates despite not all of them being transversal. Importantly, the cnot gate remains transversal in both codes, and as such has increased error protection relative to the other single qubit logical gates. We show that while the level-1 pseudothreshold for the concatenated scheme is limited by the logical Hadamard gate, the error suppression of the logical cnot gates allows for the asymptotic threshold to increase by orders of magnitude at higher levels. We establish a lower bound of 1.28×10^{-3} for the asymptotic threshold of this code, which is competitive with known concatenated models and does not rely on ancillary magic state preparation for universal computation.

arXiv:1603.02704•Physical Review Letters•Jun 28, 2016•53 citations

Noise threshold for a fault-tolerant two-dimensional lattice architecture

Krysta M. Svore, David Peter Divincenzo, Barbara M. Terhal

We consider a model of quantum computation in which the set of operations is limited to nearest-neighbor interactions on a 2D lattice. We model movement of qubits with noisy \SWAP\ operations. For this architecture we design a fault-tolerant coding scheme using the concatenated $[[7,1,3]]$ Steane code. Our scheme is potentially applicable to ion-trap and solid-state quantum technologies. We calculate a lower bound on the noise threshold for our local model using a detailed failure probability analysis. We obtain a threshold of $1.85 \times 10^{-5}$ for the local setting, where memory error rates are one-tenth of the failure rates of gates, measurement, and preparation steps. For the analogous nonlocal setting, we obtain a noise threshold of $3.61 \times 10^{-5}$. Our results thus show that the additional \SWAP\ operations required to move qubits in the local model affect the noise threshold only moderately.

arXiv:quant-ph/0604090•Quantum Information and Computation•May 1, 2007•96 citations

Fault-tolerant quantum computation with local gates

Daniel Gottesman

The performance of fault-tolerant quantum computation with concatenated codes using local gates in small numbers of spatial dimensions is discussed. It is shown that a threshold result still exists in three, two, or one spatial dimensions when next-to-nearest-neighbour gates are available, and explicit constructions are presented. In two or three dimensions, it is also shown how nearest-neighbour gates can give a threshold result. In all cases, it is simply demonstrated that a threshold exists, and no attempt to optimize the error correction circuit or to determine the exact value of the threshold is made. The additional overhead due to the fault-tolerance in both space and time is polylogarithmic in the error rate per logical gate.

arXiv:quant-ph/9903099•Journal of Modern Optics•Feb 1, 2000•136 citations

Quantum accuracy threshold for concatenated distance-3 code

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 $\varepsilon_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, $\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.

arXiv:quant-ph/0504218•Quantum Information and Computation•Mar 1, 2006•559 citations

Fibonacci scheme for fault-tolerant quantum computation

Panos Aliferis, John P. Preskill

We rigorously analyze Knill's Fibonacci scheme for fault-tolerant quantum computation, which is based on the recursive preparation of Bell states protected by a concatenated error-detecting code. We prove lower bounds on the threshold fault rate of $0.67\ifmmode\times\else\texttimes\fi{}{10}^{\ensuremath{-}3}$ for adversarial local stochastic noise, and $1.25\ifmmode\times\else\texttimes\fi{}{10}^{\ensuremath{-}3}$ for independent depolarizing noise. In contrast to other schemes with comparable proved accuracy thresholds, the Fibonacci scheme has a significantly reduced overhead cost because it uses postselection far more sparingly.

arXiv:0809.5063•Physical Review A•Jan 30, 2009•49 citations
In this paper, we place bounds on when it is impossible to purify a noisy two-qubit state if all the gates used in the purification protocol are subject to adversarial, local, independent noise. It is found that the gate operations must be subject to less than 5.3% error. An existing proof that purification is equivalent to error correction is used to show that this bound can also be applied to concatenated error correcting codes in the presence of noisy gates, and hence gives a limit to the tolerable error rate for a fault-tolerant quantum computer formed by concatenation. This is shown to apply also to the case where error detection and postselection, as proposed by Knill, is used to enhance the threshold. We demonstrate the trade-off between gate and environmentally induced faulty rotations and qubit loss errors.
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×10−31.04\times 10^{-3}1.04×10−3, is well below Knill's numerical estimates.
Quantum error correction and fault tolerance make it possible to perform quantum computations in the presence of imprecision and imperfections of realistic devices. An important question is to find the noise rate at which errors can be arbitrarily suppressed. By concatenating the 7-qubit Steane and 15-qubit Reed-Muller codes, the 105-qubit code enables a universal set of fault-tolerant gates despite not all of them being transversal. Importantly, the cnot gate remains transversal in both codes, and as such has increased error protection relative to the other single qubit logical gates. We show that while the level-1 pseudothreshold for the concatenated scheme is limited by the logical Hadamard gate, the error suppression of the logical cnot gates allows for the asymptotic threshold to increase by orders of magnitude at higher levels. We establish a lower bound of 1.28×10^{-3} for the asymptotic threshold of this code, which is competitive with known concatenated models and does not rely on ancillary magic state preparation for universal computation.
We consider a model of quantum computation in which the set of operations is limited to nearest-neighbor interactions on a 2D lattice. We model movement of qubits with noisy \SWAP\ operations. For this architecture we design a fault-tolerant coding scheme using the concatenated [[7,1,3]][[7,1,3]][[7,1,3]] Steane code. Our scheme is potentially applicable to ion-trap and solid-state quantum technologies. We calculate a lower bound on the noise threshold for our local model using a detailed failure probability analysis. We obtain a threshold of 1.85×10−51.85 \times 10^{-5}1.85×10−5 for the local setting, where memory error rates are one-tenth of the failure rates of gates, measurement, and preparation steps. For the analogous nonlocal setting, we obtain a noise threshold of 3.61×10−53.61 \times 10^{-5}3.61×10−5. Our results thus show that the additional \SWAP\ operations required to move qubits in the local model affect the noise threshold only moderately.
The performance of fault-tolerant quantum computation with concatenated codes using local gates in small numbers of spatial dimensions is discussed. It is shown that a threshold result still exists in three, two, or one spatial dimensions when next-to-nearest-neighbour gates are available, and explicit constructions are presented. In two or three dimensions, it is also shown how nearest-neighbour gates can give a threshold result. In all cases, it is simply demonstrated that a threshold exists, and no attempt to optimize the error correction circuit or to determine the exact value of the threshold is made. The additional overhead due to the fault-tolerance in both space and time is polylogarithmic in the error rate per logical gate.
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 ε0\varepsilon_0ε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, ε0≥2.73×10−5\varepsilon_0 \ge 2.73\times 10^{-5}ε0​≥2.73×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 rigorously analyze Knill's Fibonacci scheme for fault-tolerant quantum computation, which is based on the recursive preparation of Bell states protected by a concatenated error-detecting code. We prove lower bounds on the threshold fault rate of $0.67\ifmmode\times\else\texttimes\fi{}{10}^{\ensuremath{-}3}$ for adversarial local stochastic noise, and $1.25\ifmmode\times\else\texttimes\fi{}{10}^{\ensuremath{-}3}$ for independent depolarizing noise. In contrast to other schemes with comparable proved accuracy thresholds, the Fibonacci scheme has a significantly reduced overhead cost because it uses postselection far more sparingly.