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/0703230

Level Reduction and the Quantum Threshold Theorem

Panos Aliferis

Published Mar 25, 2007• 62 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.quant-ph/0703230

Related papers

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

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

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 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

Noise Threshold of Quantum Supremacy

Keisuke Fujii

Demonstrating quantum supremacy, a complexity-guaranteed quantum advantage against over the best classical algorithms by using less universal quantum devices, is an important near-term milestone for quantum information processing. Here we develop a threshold theorem for quantum supremacy with noisy quantum circuits in the pre-threshold region, where quantum error correction does not work directly. We show that, even in such a region, we can virtually simulate quantum error correction by postselection. This allows us to show that the output sampled from the noisy quantum circuits (without postselection) cannot be simulated efficiently by classical computers based on a stable complexity theoretical conjecture, i.e., non-collapse of the polynomial hierarchy. By applying this to fault-tolerant quantum computation with the surface codes, we obtain the threshold value $2.84\%$ for quantum supremacy, which is much higher than the standard threshold $0.75\%$ for universal fault-tolerant quantum computation with the same circuit-level noise model. Moreover, contrast to the standard noise threshold, the origin of quantum supremacy in noisy quantum circuits is quite clear; the threshold is determined purely by the threshold of magic state distillation, which is essential to gain a quantum advantage.

arXiv:1610.03632•Oct 12, 2016•32 citations

QUANTUM ERROR CORRECTION AND FAULT-TOLERANT QUANTUM COMPUTING

Frank Gaitan, Ran Li

We review the theories of quantum error correction, and of fault-tolerant quantum computing, and show how these powerful tools are combined to prove the accuracy threshold theorem for a particular error model. One of the theorem's assumptions is the availability of a universal set of unencoded quantum gates whose error probabilities P e fall below a value known as the accuracy threshold P a . For many, P a ~ 10 -4 has become a rough estimate for the threshold so that quantum gates are anticipated to be approaching the accuracies needed for fault-tolerant quantum computing when P e < 10 -4 . We show how controllable quantum interference effects that arise during a type of non-adiabatic rapid passage can be used to produce a universal set of quantum gates whose error probabilities satisfy P e < 10 -4 . We close with a discussion of the current challenges facing an experimental implementation of this approach to reliable universal quantum computation.

•Nov 1, 2009•44 citations
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.
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.
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.
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 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.
Demonstrating quantum supremacy, a complexity-guaranteed quantum advantage against over the best classical algorithms by using less universal quantum devices, is an important near-term milestone for quantum information processing. Here we develop a threshold theorem for quantum supremacy with noisy quantum circuits in the pre-threshold region, where quantum error correction does not work directly. We show that, even in such a region, we can virtually simulate quantum error correction by postselection. This allows us to show that the output sampled from the noisy quantum circuits (without postselection) cannot be simulated efficiently by classical computers based on a stable complexity theoretical conjecture, i.e., non-collapse of the polynomial hierarchy. By applying this to fault-tolerant quantum computation with the surface codes, we obtain the threshold value 2.84%2.84\%2.84% for quantum supremacy, which is much higher than the standard threshold 0.75%0.75\%0.75% for universal fault-tolerant quantum computation with the same circuit-level noise model. Moreover, contrast to the standard noise threshold, the origin of quantum supremacy in noisy quantum circuits is quite clear; the threshold is determined purely by the threshold of magic state distillation, which is essential to gain a quantum advantage.
We review the theories of quantum error correction, and of fault-tolerant quantum computing, and show how these powerful tools are combined to prove the accuracy threshold theorem for a particular error model. One of the theorem's assumptions is the availability of a universal set of unencoded quantum gates whose error probabilities P e fall below a value known as the accuracy threshold P a . For many, P a ~ 10 -4 has become a rough estimate for the threshold so that quantum gates are anticipated to be approaching the accuracies needed for fault-tolerant quantum computing when P e < 10 -4 . We show how controllable quantum interference effects that arise during a type of non-adiabatic rapid passage can be used to produce a universal set of quantum gates whose error probabilities satisfy P e < 10 -4 . We close with a discussion of the current challenges facing an experimental implementation of this approach to reliable universal quantum computation.