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

New Limits on Fault-Tolerant Quantum Computation

Harry Buhrman, Richard Cleve, Monique Laurent, Noah Linden, Alexander Schrijver, Falk Unger

Published Jan 1, 2006• 59 citations
arXivHTMLPDF

Abstract

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

DOI
10.1109/focs.2006.50

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

Quantum Information and Computation•May 1, 2010•6 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

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

Tight Noise Thresholds for Quantum Computation with Perfect Stabilizer Operations

Wim van Dam, Mark Howard

We study how much noise can be tolerated by a universal gate set before it loses its quantum-computational power. Specifically we look at circuits with perfect stabilizer operations in addition to imperfect nonstabilizer gates. We prove that for all unitary single-qubit gates there exists a tight depolarizing noise threshold that determines whether the gate enables universal quantum computation or if the gate can be simulated by a mixture of Clifford gates. This exact threshold is determined by the Clifford polytope spanned by the 24 single-qubit Clifford gates. The result is in contrast to the situation wherein nonstabilizer qubit states are used; the thresholds in that case are not currently known to be tight.

arXiv:0907.3189•Physical Review Letters•Oct 23, 2009•25 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

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
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 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.
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 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.
We study how much noise can be tolerated by a universal gate set before it loses its quantum-computational power. Specifically we look at circuits with perfect stabilizer operations in addition to imperfect nonstabilizer gates. We prove that for all unitary single-qubit gates there exists a tight depolarizing noise threshold that determines whether the gate enables universal quantum computation or if the gate can be simulated by a mixture of Clifford gates. This exact threshold is determined by the Clifford polytope spanned by the 24 single-qubit Clifford gates. The result is in contrast to the situation wherein nonstabilizer qubit states are used; the thresholds in that case are not currently known to be tight.
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.