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

An upper bound on quantum fault tolerant thresholds

Jesse Fern

Published Jan 17, 2008• 5 citations
arXivHTMLPDF

Abstract

In this paper we calculate upper bounds on fault tolerance, without restrictions on the overhead involved. Optimally adaptive recovery operators are used, and the Shannon entropy is used to estimate the thresholds. By allowing for unrealistically high levels of overhead, we find a quantum fault tolerant threshold of 6.88% for the depolarizing noise used by Knill, which compares well to "above 3%" evidenced by Knill. We conjecture that the optimal threshold is 6.90%, based upon the hashing rate. We also perform threshold calculations for types of noise other than that discussed by Knill.

DOI
10.48550/arxiv.0801.2608

Related papers

Upper bounds on fault tolerance thresholds of noisy Clifford-based quantum computers

Martin Bodo Plenio, S Virmani

We consider the possibility of adding noise to a quantum circuit to make it efficiently simulatable classically. In previous works, this approach has been used to derive upper bounds to fault tolerance thresholds—usually by identifying a privileged resource, such as an entangling gate or a non-Clifford operation, and then deriving the noise levels required to make it 'unprivileged'. In this work, we consider extensions of this approach where noise is added to Clifford gates too and then 'commuted' around until it concentrates on attacking the non-Clifford resource. While commuting noise around is not always straightforward, we find that easy instances can be identified in popular fault tolerance proposals, thereby enabling sharper upper bounds to be derived in these cases. For instance we find that if we take Knill's (2005 Nature 434 39) fault tolerance proposal together with the ability to prepare any possible state in the XY plane of the Bloch sphere, then not more than 3.69% error-per-gate noise is sufficient to make it classical, and 13.71% of Knill's γ noise model is sufficient. These bounds have been derived without noise being added to the decoding parts of the circuits. Introducing such noise in a toy example suggests that the present approach can be optimized further to yield tighter bounds.

arXiv:0810.4340•New Journal of Physics•Mar 9, 2010•17 citations

A comparative code study for quantum fault tolerance

Andrew W. Cross, David Peter Divincenzo, Barbara M. Terhal

We study a comprehensive list of quantum codes as candidates for codes used at the physical level in a fault-tolerant code architecture. Using the Aliferis-Gottesman-Preskill (AGP) ex-Rec method we calculate the pseudo-threshold for these codes against depolarizing noise at various levels of overhead. We estimate the logical noise rate as a function of overhead at a physical error rate of $p_0=1 \times 10^{-4}$. The Bacon-Shor codes and the Golay code are the best performers in our study.

arXiv:0711.1556•Quantum Information and Computation•Jul 1, 2009•122 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

New Limits on Fault-Tolerant Quantum Computation

Harry Buhrman, Richard Cleve, Monique Laurent +3 more

We show that quantum circuits cannot be made fault-tolerant against a depolarizing noise level of thetas = (6 - 2radic2)/7 ap 45%, thereby improving on a previous bound of 50% (due to Razborov, 2004). More precisely, the circuit model for which we prove this bound contains perfect gates from the Clifford group (CNOT, Hadamard, S, X, Y, Z) and arbitrary additional one-qubit gates that are subject to depolarizing noise thetas. We prove that this set of gates cannot be universal for arbitrary (even classical) computation, from which the upper bound on the noise threshold for fault-tolerant quantum computation follows

arXiv:quant-ph/0604141•Annual Symposium on Foundations of Computer Science•Jan 1, 2006•67 citations

A Lower Bound on the Space Overhead of Fault-Tolerant Quantum Computation

Omar Fawzi, Alexander Müller‐Hermes, Ala Shayeghi

The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation stating that arbitrarily long quantum computations can be performed with a polylogarithmic overhead provided the noise level is below a constant level. A recent work by Fawzi, Grospellier and Leverrier (FOCS 2018) building on a result by Gottesman (QIC 2013) has shown that the space overhead can be asymptotically reduced to a constant independent of the circuit provided we only consider circuits with a length bounded by a polynomial in the width. In this work, using a minimal model for quantum fault tolerance, we establish a general lower bound on the space overhead required to achieve fault tolerance. For any non-unitary qubit channel $\mathcal{N}$ and any quantum fault tolerance schemes against $\mathrm{i.i.d.}$ noise modeled by $\mathcal{N}$, we prove a lower bound of $\max\left\{\mathrm{Q}(\mathcal{N})^{-1}n,α_\mathcal{N} \log T\right\}$ on the number of physical qubits, for circuits of length $T$ and width $n$. Here, $\mathrm{Q}(\mathcal{N})$ denotes the quantum capacity of $\mathcal{N}$ and $α_\mathcal{N}>0$ is a constant only depending on the channel $\mathcal{N}$. In our model, we allow for qubits to be replaced by fresh ones during the execution of the circuit and we allow classical computation to be free and perfect. This improves upon results that assumed classical computations to be also affected by noise, and that sometimes did not allow for fresh qubits to be added. Along the way, we prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude damping noise resolving a conjecture by Ben-Or, Gottesman, and Hassidim (2013).

arXiv:2202.00119•Leibniz international proceedings in informatics•Jan 1, 2022•11 citations

Fault-tolerant quantum computation cannot be achieved with constant spacetime overhead

Kishor Bharti, Tobias Haug, Andrew Tanggara

The threshold theorem states that quantum computations can be made reliable below a physical error threshold, at the cost of additional physical qubits and circuit depth. Recent work has reduced these space and time overheads to polylogarithmic or nearly logarithmic scalings, but whether the cumulative spacetime overhead can be constant has remained unclear. Here, we show that even for the simplest task of preserving quantum information in a quantum memory, under an optimistic noise model and allowing general adaptive protocols, there is an unavoidable logarithmic contribution to the cumulative spacetime overhead. This additional cost can nevertheless be shared among many logical qubits, so sufficiently wide computations, including standard implementations of Shor's algorithm, may still achieve constant relative overhead. We further give a positive-rate CSS code construction that attains the memory bound, identify sufficient conditions under which the same scaling extends from quantum memory to fault-tolerant circuit implementations, and derive circuit-size bounds for subsystem spacetime codes. Our work establishes fundamental limits on the resources required for quantum fault tolerance.

quant-pharXiv:2608.26272•Aug 28, 2026•2 citations
In this paper we calculate upper bounds on fault tolerance, without restrictions on the overhead involved. Optimally adaptive recovery operators are used, and the Shannon entropy is used to estimate the thresholds. By allowing for unrealistically high levels of overhead, we find a quantum fault tolerant threshold of 6.88% for the depolarizing noise used by Knill, which compares well to "above 3%" evidenced by Knill. We conjecture that the optimal threshold is 6.90%, based upon the hashing rate. We also perform threshold calculations for types of noise other than that discussed by Knill.
We consider the possibility of adding noise to a quantum circuit to make it efficiently simulatable classically. In previous works, this approach has been used to derive upper bounds to fault tolerance thresholds—usually by identifying a privileged resource, such as an entangling gate or a non-Clifford operation, and then deriving the noise levels required to make it 'unprivileged'. In this work, we consider extensions of this approach where noise is added to Clifford gates too and then 'commuted' around until it concentrates on attacking the non-Clifford resource. While commuting noise around is not always straightforward, we find that easy instances can be identified in popular fault tolerance proposals, thereby enabling sharper upper bounds to be derived in these cases. For instance we find that if we take Knill's (2005 Nature 434 39) fault tolerance proposal together with the ability to prepare any possible state in the XY plane of the Bloch sphere, then not more than 3.69% error-per-gate noise is sufficient to make it classical, and 13.71% of Knill's γ noise model is sufficient. These bounds have been derived without noise being added to the decoding parts of the circuits. Introducing such noise in a toy example suggests that the present approach can be optimized further to yield tighter bounds.
We study a comprehensive list of quantum codes as candidates for codes used at the physical level in a fault-tolerant code architecture. Using the Aliferis-Gottesman-Preskill (AGP) ex-Rec method we calculate the pseudo-threshold for these codes against depolarizing noise at various levels of overhead. We estimate the logical noise rate as a function of overhead at a physical error rate of p0=1×10−4p_0=1 \times 10^{-4}p0​=1×10−4. The Bacon-Shor codes and the Golay code are the best performers in our study.
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.
We show that quantum circuits cannot be made fault-tolerant against a depolarizing noise level of thetas = (6 - 2radic2)/7 ap 45%, thereby improving on a previous bound of 50% (due to Razborov, 2004). More precisely, the circuit model for which we prove this bound contains perfect gates from the Clifford group (CNOT, Hadamard, S, X, Y, Z) and arbitrary additional one-qubit gates that are subject to depolarizing noise thetas. We prove that this set of gates cannot be universal for arbitrary (even classical) computation, from which the upper bound on the noise threshold for fault-tolerant quantum computation follows
The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation stating that arbitrarily long quantum computations can be performed with a polylogarithmic overhead provided the noise level is below a constant level. A recent work by Fawzi, Grospellier and Leverrier (FOCS 2018) building on a result by Gottesman (QIC 2013) has shown that the space overhead can be asymptotically reduced to a constant independent of the circuit provided we only consider circuits with a length bounded by a polynomial in the width. In this work, using a minimal model for quantum fault tolerance, we establish a general lower bound on the space overhead required to achieve fault tolerance. For any non-unitary qubit channel N\mathcal{N}N and any quantum fault tolerance schemes against i.i.d.\mathrm{i.i.d.}i.i.d. noise modeled by N\mathcal{N}N, we prove a lower bound of max⁡{Q(N)−1n,αNlog⁡T}\max\left\{\mathrm{Q}(\mathcal{N})^{-1}n,α_\mathcal{N} \log T\right\}max{Q(N)−1n,αN​logT} on the number of physical qubits, for circuits of length TTT and width nnn. Here, Q(N)\mathrm{Q}(\mathcal{N})Q(N) denotes the quantum capacity of N\mathcal{N}N and αN>0α_\mathcal{N}>0αN​>0 is a constant only depending on the channel N\mathcal{N}N. In our model, we allow for qubits to be replaced by fresh ones during the execution of the circuit and we allow classical computation to be free and perfect. This improves upon results that assumed classical computations to be also affected by noise, and that sometimes did not allow for fresh qubits to be added. Along the way, we prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude damping noise resolving a conjecture by Ben-Or, Gottesman, and Hassidim (2013).
The threshold theorem states that quantum computations can be made reliable below a physical error threshold, at the cost of additional physical qubits and circuit depth. Recent work has reduced these space and time overheads to polylogarithmic or nearly logarithmic scalings, but whether the cumulative spacetime overhead can be constant has remained unclear. Here, we show that even for the simplest task of preserving quantum information in a quantum memory, under an optimistic noise model and allowing general adaptive protocols, there is an unavoidable logarithmic contribution to the cumulative spacetime overhead. This additional cost can nevertheless be shared among many logical qubits, so sufficiently wide computations, including standard implementations of Shor's algorithm, may still achieve constant relative overhead. We further give a positive-rate CSS code construction that attains the memory bound, identify sufficient conditions under which the same scaling extends from quantum memory to fault-tolerant circuit implementations, and derive circuit-size bounds for subsystem spacetime codes. Our work establishes fundamental limits on the resources required for quantum fault tolerance.