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 Information and Computation

Upper bounds on the noise threshold for fault-tolerant quantum computing

Julia Kempe, Oded Regev, Falk Unger, Ronald de Wolf

Published May 1, 2010• 6 citations
Publisher

Abstract

We prove new upper bounds on the tolerable level of noise in a quantum circuit. We consider circuits consisting of unitary $k$-qubit gates each of whose input wires is subject to depolarizing noise of strength $p$, as well as arbitrary one-qubit gates that are essentially noise-free. We assume that the output of the circuit is the result of measuring some designated qubit in the final state. Our main result is that for $p>1-\Theta(1/\sqrt{k})$, the output of any such circuit of large enough depth is essentially independent of its input, thereby making the circuit useless. For the important special case of $k=2$, our bound is $p>35.7\%$. Moreover, if the only allowed gate on more than one qubit is the two-qubit CNOT gate, then our bound becomes $29.3\%$. These bounds on $p$ are numerically better than previous bounds, yet are incomparable because of the somewhat different circuit model that we are using. Our main technique is the use of a Pauli basis decomposition, in which the effects of depolarizing noise are very easy to describe.

DOI
10.26421/qic10.5-6-1

Related papers

Upper Bounds on the Noise Threshold for Fault-tolerant Quantum Computing

Julia Kempe, Oded Regev, Falk Unger +1 more

We prove new upper bounds on the tolerable level of noise in a quantum circuit. We consider circuits consisting of unitary k-qubit gates each of whose input wires is subject to depolarizing noise of strength p, as well as arbitrary one-qubit gates that are essentially noise-free. We assume that the output of the circuit is the result of measuring some designated qubit in the final state. Our main result is that for p>1-Θ(1/\sqrt{k}), the output of any such circuit of large enough depth is essentially independent of its input, thereby making the circuit useless. For the important special case of k=2, our bound is p>35.7%. Moreover, if the only allowed gate on more than one qubit is the two-qubit CNOT gate, then our bound becomes 29.3%. These bounds on p are notably better than previous bounds, yet are incomparable because of the somewhat different circuit model that we are using. Our main technique is the use of a Pauli basis decomposition, which we believe should lead to further progress in deriving such bounds.

arXiv:0802.1464•Feb 11, 2008•0 citations

Noise Limits on Fault-Tolerant Fermionic Quantum Computing

Owen Allison, Luke Coffman

Determining the highest amount of noise that quantum circuits can handle is an interesting and crucial task in the development of fault-tolerant quantum computation. Previous work has constrained this upper limit for local depolarizing noise to $\approx 45~\%$ for circuits constructed using the universal Clifford with T gate set by finding the noise threshold where the gate set loses universality. In this work, we use a similar method with the matchgate with non-Gaussian resource universal gate set to find a limit of $p=(8 - 2 \sqrt{6})/5$ or $\approx 62~\%$ for fermionic quantum computing that is independent of circuit depth. To do this, we use Uhlmann-Wootters concurrences for a 4-mode fermionic Choi state representing a resourceful gate combined with local depolarizing noise to determine when the combined channel is convex Gaussian. These bounds are not directly comparable due to differences in noise model making the bound of $\approx 62~\%$ the best known for fermions.

quant-pharXiv:2609.09467•Sep 10, 2026•0 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•59 citations

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

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.

•Mar 9, 2010•15 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•4 citations
We prove new upper bounds on the tolerable level of noise in a quantum circuit. We consider circuits consisting of unitary kkk-qubit gates each of whose input wires is subject to depolarizing noise of strength ppp, as well as arbitrary one-qubit gates that are essentially noise-free. We assume that the output of the circuit is the result of measuring some designated qubit in the final state. Our main result is that for p>1−Θ(1/k)p>1-\Theta(1/\sqrt{k})p>1−Θ(1/k​), the output of any such circuit of large enough depth is essentially independent of its input, thereby making the circuit useless. For the important special case of k=2k=2k=2, our bound is p>35.7%p>35.7\%p>35.7%. Moreover, if the only allowed gate on more than one qubit is the two-qubit CNOT gate, then our bound becomes 29.3%29.3\%29.3%. These bounds on ppp are numerically better than previous bounds, yet are incomparable because of the somewhat different circuit model that we are using. Our main technique is the use of a Pauli basis decomposition, in which the effects of depolarizing noise are very easy to describe.
We prove new upper bounds on the tolerable level of noise in a quantum circuit. We consider circuits consisting of unitary k-qubit gates each of whose input wires is subject to depolarizing noise of strength p, as well as arbitrary one-qubit gates that are essentially noise-free. We assume that the output of the circuit is the result of measuring some designated qubit in the final state. Our main result is that for p>1-Θ(1/\sqrt{k}), the output of any such circuit of large enough depth is essentially independent of its input, thereby making the circuit useless. For the important special case of k=2, our bound is p>35.7%. Moreover, if the only allowed gate on more than one qubit is the two-qubit CNOT gate, then our bound becomes 29.3%. These bounds on p are notably better than previous bounds, yet are incomparable because of the somewhat different circuit model that we are using. Our main technique is the use of a Pauli basis decomposition, which we believe should lead to further progress in deriving such bounds.
Determining the highest amount of noise that quantum circuits can handle is an interesting and crucial task in the development of fault-tolerant quantum computation. Previous work has constrained this upper limit for local depolarizing noise to ≈45 %\approx 45~\%≈45 % for circuits constructed using the universal Clifford with T gate set by finding the noise threshold where the gate set loses universality. In this work, we use a similar method with the matchgate with non-Gaussian resource universal gate set to find a limit of p=(8−26)/5p=(8 - 2 \sqrt{6})/5p=(8−26​)/5 or ≈62 %\approx 62~\%≈62 % for fermionic quantum computing that is independent of circuit depth. To do this, we use Uhlmann-Wootters concurrences for a 4-mode fermionic Choi state representing a resourceful gate combined with local depolarizing noise to determine when the combined channel is convex Gaussian. These bounds are not directly comparable due to differences in noise model making the bound of ≈62 %\approx 62~\%≈62 % the best known for fermions.
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
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 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.
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).