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

Quantum accuracy threshold for distance-5 codes

Omar. Khalid

Published Jan 1, 2006• 0 citations
Publisher

Abstract

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.

DOI
10.82308/51383

Related papers

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

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•74 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•90 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.

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

Accuracy threshold for concatenated error detection in one dimension

Ashley M. Stephens, Zachary W. E. Evans

Estimates of the quantum accuracy threshold often tacitly assume that it is possible to interact arbitrary pairs of qubits in a quantum computer with a failure rate that is independent of the distance between them. None of the many physical systems that are candidates for quantum computing possess this property. Here we study the performance of a concatenated error-detection code in a system that permits only nearest-neighbor interactions in one dimension. We make use of a message-passing scheme that maximizes the number of errors that can be reliably corrected by the code. Our numerical results indicate that arbitrarily accurate universal quantum computation is possible if the probability of failure of each elementary physical operation is below approximately ${10}^{\ensuremath{-}5}$. This threshold is three orders of magnitude lower than the highest known.

arXiv:0902.2658•Physical Review A•Aug 10, 2009•28 citations

Level-Reduction and the Quantum Threshold Theorem

Panagiotis Aliferis

Computers have led society to the information age revolutionizing central aspects of our lives from production and communication to education and entertainment. There exist, however, important problems which are intractable with the computers available today and, experience teaches us, will remain so even with the more advanced computers we can envision for tomorrow. Quantum computers promise speedups to some of these important but classically intractable problems. Simulating physical systems, a problem of interest in a diverse range of areas from testing physical theories to understanding chemical reactions, and solving number factoring, a problem at the basis of cryptographic protocols that are used widely today on the internet, are examples of applications for which quantum computers, when built, will offer a great advantage over what is possible with classical computer technology. The construction of a quantum computer of sufficient scale to solve interesting problems is, however, especially challenging. The reason for this is that, by its very nature, operating a quantum computer will require the coherent control of the quantum state of a very large number of particles. Fortunately, the theory of quantum error correction and fault-tolerant quantum computation gives us confidence that such quantum states can be created, can be stored in memory and can also be manipulated provided the quantum computer can be isolated to a sufficient degree from sources of noise. One of the central results in the theory of fault-tolerant quantum computation, the quantum threshold theorem shows that a noisy quantum computer can accurately and efficiently simulate any ideal quantum computation provided that noise is weakly correlated and its strength is below a critical value known as the quantum accuracy threshold. This thesis provides a simpler and more transparent non-inductive proof of this theorem based on the concept of level reduction. This concept is also used in proving the quantum threshold theorem for coherent and leakage noise and for quantum computation by measurements. In addition, the proof provides a methodology which allows us to establish improved rigorous lower bounds on the value of the quantum accuracy threshold.

•Mar 28, 2007•8 citations
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.
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 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}.
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.
Estimates of the quantum accuracy threshold often tacitly assume that it is possible to interact arbitrary pairs of qubits in a quantum computer with a failure rate that is independent of the distance between them. None of the many physical systems that are candidates for quantum computing possess this property. Here we study the performance of a concatenated error-detection code in a system that permits only nearest-neighbor interactions in one dimension. We make use of a message-passing scheme that maximizes the number of errors that can be reliably corrected by the code. Our numerical results indicate that arbitrarily accurate universal quantum computation is possible if the probability of failure of each elementary physical operation is below approximately ${10}^{\ensuremath{-}5}$. This threshold is three orders of magnitude lower than the highest known.
Computers have led society to the information age revolutionizing central aspects of our lives from production and communication to education and entertainment. There exist, however, important problems which are intractable with the computers available today and, experience teaches us, will remain so even with the more advanced computers we can envision for tomorrow. Quantum computers promise speedups to some of these important but classically intractable problems. Simulating physical systems, a problem of interest in a diverse range of areas from testing physical theories to understanding chemical reactions, and solving number factoring, a problem at the basis of cryptographic protocols that are used widely today on the internet, are examples of applications for which quantum computers, when built, will offer a great advantage over what is possible with classical computer technology. The construction of a quantum computer of sufficient scale to solve interesting problems is, however, especially challenging. The reason for this is that, by its very nature, operating a quantum computer will require the coherent control of the quantum state of a very large number of particles. Fortunately, the theory of quantum error correction and fault-tolerant quantum computation gives us confidence that such quantum states can be created, can be stored in memory and can also be manipulated provided the quantum computer can be isolated to a sufficient degree from sources of noise. One of the central results in the theory of fault-tolerant quantum computation, the quantum threshold theorem shows that a noisy quantum computer can accurately and efficiently simulate any ideal quantum computation provided that noise is weakly correlated and its strength is below a critical value known as the quantum accuracy threshold. This thesis provides a simpler and more transparent non-inductive proof of this theorem based on the concept of level reduction. This concept is also used in proving the quantum threshold theorem for coherent and leakage noise and for quantum computation by measurements. In addition, the proof provides a methodology which allows us to establish improved rigorous lower bounds on the value of the quantum accuracy threshold.