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/0608018 · Annual Symposium on Foundations of Computer Science

Postselection threshold against biased noise

Ben W. Reichardt

Published Jan 1, 2006• 2 citations
arXivHTMLPDF

Abstract

The highest current estimates for the amount of noise a quantum computer can tolerate are based on fault-tolerance schemes relying heavily on postselecting on no detected errors. However, there has been no proof that these schemes give even a positive tolerable noise threshold. A technique to prove a positive threshold, for probabilistic noise models, is presented. The main idea is to maintain strong control over the distribution of errors in the quantum state at all times. This distribution has correlations which conceivably could grow out of control with postselection. But in fact, the error distribution can be written as a mixture of nearby distributions each satisfying strong independence properties, so there are no correlations for postselection to amplify

DOI
10.1109/focs.2006.64

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•95 citations

Error-detection-based quantum fault tolerance against discrete Pauli noise

Reichardt, Ben W.

A quantum computer -- i.e., a computer capable of manipulating data in quantum superposition -- would find applications including factoring, quantum simulation and tests of basic quantum theory. Since quantum superpositions are fragile, the major hurdle in building such a computer is overcoming noise. Developed over the last couple of years, new schemes for achieving fault tolerance based on error detection, rather than error correction, appear to tolerate as much as 3-6% noise per gate -- an order of magnitude better than previous procedures. But proof techniques could not show that these promising fault-tolerance schemes tolerated any noise at all. With an analysis based on decomposing complicated probability distributions into mixtures of simpler ones, we rigorously prove the existence of constant tolerable noise rates ("noise thresholds") for error-detection-based schemes. Numerical calculations indicate that the actual noise threshold this method yields is lower-bounded by 0.1% noise per gate.

arXiv:quant-ph/0612004•Nov 30, 2006•29 citations

Accuracy threshold for postselected quantum computation

AliferisPanos, GottesmanDaniel, PreskillJohn

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

Quantum Information and Computation•Mar 1, 2008•1 citation

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.

arXiv:quant-ph/0509203•Sep 28, 2005•8 citations

Fault-Tolerant Postselected Quantum Computation: Threshold Analysis

Emanuel H. Knill

The schemes for fault-tolerant postselected quantum computation given in [Knill, Fault-Tolerant Postselected Quantum Computation: Schemes, http://arxiv.org/abs/quant-ph/0402171] are analyzed to determine their error-tolerance. The analysis is based on computer-assisted heuristics. It indicates that if classical and quantum communication delays are negligible, then scalable qubit-based quantum computation is possible with errors above 1% per elementary quantum gate.

arXiv:quant-ph/0404104•Apr 19, 2004•44 citations

The Role of Correlated Noise in Quantum Computing

Daan Staudt

This paper aims to give an overview of the current state of fault-tolerant quantum computing, by surveying a number of results in the field. We show that thresholds can be obtained for a simple noise model as first proved in [AB97, Kit97, KLZ98], by presenting a proof for statistically independent noise, following the presentation of Aliferis, Gottesman and Preskill [AGP06]. We also present a result by Terhal and Burkard [TB05] and later improved upon by Aliferis, Gottesman and Preskill [AGP06] that shows a threshold can still be obtained for local non-Markovian noise, where we allow the noise to be weakly correlated in space and time. We then turn to negative results, presenting work by Ben-Aroya and Ta-Shma [BT11] who showed conditional errors cannot be perfectly corrected. We end our survey by briefly mentioning some more speculative objections, as put forth by Kalai [Kal08, Kal09, Kal11].

arXiv:1111.1417•Nov 6, 2011•3 citations
The highest current estimates for the amount of noise a quantum computer can tolerate are based on fault-tolerance schemes relying heavily on postselecting on no detected errors. However, there has been no proof that these schemes give even a positive tolerable noise threshold. A technique to prove a positive threshold, for probabilistic noise models, is presented. The main idea is to maintain strong control over the distribution of errors in the quantum state at all times. This distribution has correlations which conceivably could grow out of control with postselection. But in fact, the error distribution can be written as a mixture of nearby distributions each satisfying strong independence properties, so there are no correlations for postselection to amplify
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.
A quantum computer -- i.e., a computer capable of manipulating data in quantum superposition -- would find applications including factoring, quantum simulation and tests of basic quantum theory. Since quantum superpositions are fragile, the major hurdle in building such a computer is overcoming noise. Developed over the last couple of years, new schemes for achieving fault tolerance based on error detection, rather than error correction, appear to tolerate as much as 3-6% noise per gate -- an order of magnitude better than previous procedures. But proof techniques could not show that these promising fault-tolerance schemes tolerated any noise at all. With an analysis based on decomposing complicated probability distributions into mixtures of simpler ones, we rigorously prove the existence of constant tolerable noise rates ("noise thresholds") for error-detection-based schemes. Numerical calculations indicate that the actual noise threshold this method yields is lower-bounded by 0.1% noise per gate.
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.
This paper aims to give an overview of the current state of fault-tolerant quantum computing, by surveying a number of results in the field. We show that thresholds can be obtained for a simple noise model as first proved in [AB97, Kit97, KLZ98], by presenting a proof for statistically independent noise, following the presentation of Aliferis, Gottesman and Preskill [AGP06]. We also present a result by Terhal and Burkard [TB05] and later improved upon by Aliferis, Gottesman and Preskill [AGP06] that shows a threshold can still be obtained for local non-Markovian noise, where we allow the noise to be weakly correlated in space and time. We then turn to negative results, presenting work by Ben-Aroya and Ta-Shma [BT11] who showed conditional errors cannot be perfectly corrected. We end our survey by briefly mentioning some more speculative objections, as put forth by Kalai [Kal08, Kal09, Kal11].