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:0907.3189 · Physical Review Letters

Tight Noise Thresholds for Quantum Computation with Perfect Stabilizer Operations

Wim van Dam, Mark Howard

Published Oct 23, 2009• 25 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physrevlett.103.170504

Related papers

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

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

Noise thresholds for higher-dimensional systems using the discrete Wigner function

Wim van Dam, Mark Howard

For a quantum computer acting on $d$-dimensional systems, we analyze the computational power of circuits wherein stabilizer operations are perfect, and we allow access to imperfect nonstabilizer states or operations. If the noise rate affecting the nonstabilizer resource is sufficiently high, then these states and operations can become simulable in the sense of the Gottesman-Knill theorem, reducing the overall power of the circuit to no better than classical. In this paper we find the depolarizing noise rate at which this happens and consequently the most robust nonstabilizer states and non-Clifford gates. In doing so, we make use of the discrete Wigner function and derive facets of the so-called qudit Clifford polytope, i.e., the inequalities defining the convex hull of all qudit Clifford gates. Our results for robust states are provably optimal. For robust gates we find a critical noise rate that, as dimension increases, rapidly approaches the the theoretical optimum of 100%. Some connections with the question of qudit magic state distillation are discussed.

arXiv:1011.2497•Physical Review A•Mar 17, 2011•39 citations

Classical simulability, entanglement breaking, and quantum computation thresholds

S. Virmani, Susana F. Huelga, Martin Bodo Plenio

We investigate the amount of noise required to turn a universal quantum gate set into one that can be efficiently modeled classically. This question is useful for providing upper bounds on fault-tolerant thresholds, and for understanding the nature of the quantum-classical computational transition. We refine some previously known upper bounds using two different strategies. The first one involves the introduction of bientangling operations, a class of classically simulable machines that can generate at most bipartite entanglement. Using this class we show that it is possible to sharpen previously obtained upper bounds in certain cases. As an example, we show that under depolarizing noise on the controlled-NOT gate, the previously known upper bound of 74% can be sharpened to around 67%. Another interesting consequence is that measurement-based schemes cannot work using only two-qubit nondegenerate projections. In the second strand of the work we utilize the Gottesman-Knill theorem on the classically efficient simulation of Clifford group operations. The bounds attained using this approach for the $\ensuremath{\pi}∕8$ gate can be as low as 15% for general single-gate noise, and 30% for dephasing noise.

arXiv:quant-ph/0408076•Physical Review A•Apr 19, 2005•51 citations

The robustness of magic state distillation against errors in Clifford gates

Tomas Jochym-O’Connor, Ya-Fei Yu, Bassam Helou +1 more

Quantum error correction and fault-tolerance have provided the possibility for large scale quantum computations without a detrimental loss of quantum information. A very natural class of gates for fault-tolerant quantum computation is the Clifford gate set and as such their usefulness for universal quantum computation is of great interest. Clifford group gates augmented by magic state preparation give the possibility of simulating universal quantum computation. However, experimentally one cannot expect to perfectly prepare magic states. Nonetheless, it has been shown that by repeatedly applying operations from the Clifford group and measurements in the Pauli basis, the fidelity of noisy prepared magic states can be increased arbitrarily close to a pure magic state~\cite{Bravyi}. We investigate the robustness of magic state distillation to perturbations of the initial states to arbitrary locations in the Bloch sphere due to noise. Additionally, we consider a depolarizing noise model on the quantum gates in the decoding section of the distillation protocol and demonstrate its effect on the convergence rate and threshold value. Finally, we establish that faulty magic state distillation is more efficient than fault-tolerance-assisted magic state distillation at low error rates due to the large overhead in the number of quantum gates and qubits required in a fault-tolerance architecture. The ability to perform magic state distillation with noisy gates leads us to conclude that this could be a realistic scheme for future small-scale quantum computing devices as fault-tolerance need only be used in the final steps of the protocol.

Quantum Information and Computation•May 1, 2013•17 citations

Universal quantum computation with ideal Clifford gates and noisy ancillas

Sergey B. Bravyi, Alexei Kitaev

We consider a model of quantum computation in which the set of elementary operations is limited to Clifford unitaries, the creation of the state $\ensuremath{\mid}0⟩$, and qubit measurement in the computational basis. In addition, we allow the creation of a one-qubit ancilla in a mixed state $\ensuremath{\rho}$, which should be regarded as a parameter of the model. Our goal is to determine for which $\ensuremath{\rho}$ universal quantum computation (UQC) can be efficiently simulated. To answer this question, we construct purification protocols that consume several copies of $\ensuremath{\rho}$ and produce a single output qubit with higher polarization. The protocols allow one to increase the polarization only along certain ``magic'' directions. If the polarization of $\ensuremath{\rho}$ along a magic direction exceeds a threshold value (about 65%), the purification asymptotically yields a pure state, which we call a magic state. We show that the Clifford group operations combined with magic states preparation are sufficient for UQC. The connection of our results with the Gottesman-Knill theorem is discussed.

arXiv:quant-ph/0403025•Physical Review A•Feb 22, 2005•1,524 citations
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 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
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.
For a quantum computer acting on ddd-dimensional systems, we analyze the computational power of circuits wherein stabilizer operations are perfect, and we allow access to imperfect nonstabilizer states or operations. If the noise rate affecting the nonstabilizer resource is sufficiently high, then these states and operations can become simulable in the sense of the Gottesman-Knill theorem, reducing the overall power of the circuit to no better than classical. In this paper we find the depolarizing noise rate at which this happens and consequently the most robust nonstabilizer states and non-Clifford gates. In doing so, we make use of the discrete Wigner function and derive facets of the so-called qudit Clifford polytope, i.e., the inequalities defining the convex hull of all qudit Clifford gates. Our results for robust states are provably optimal. For robust gates we find a critical noise rate that, as dimension increases, rapidly approaches the the theoretical optimum of 100%. Some connections with the question of qudit magic state distillation are discussed.
We investigate the amount of noise required to turn a universal quantum gate set into one that can be efficiently modeled classically. This question is useful for providing upper bounds on fault-tolerant thresholds, and for understanding the nature of the quantum-classical computational transition. We refine some previously known upper bounds using two different strategies. The first one involves the introduction of bientangling operations, a class of classically simulable machines that can generate at most bipartite entanglement. Using this class we show that it is possible to sharpen previously obtained upper bounds in certain cases. As an example, we show that under depolarizing noise on the controlled-NOT gate, the previously known upper bound of 74% can be sharpened to around 67%. Another interesting consequence is that measurement-based schemes cannot work using only two-qubit nondegenerate projections. In the second strand of the work we utilize the Gottesman-Knill theorem on the classically efficient simulation of Clifford group operations. The bounds attained using this approach for the $\ensuremath{\pi}∕8$ gate can be as low as 15% for general single-gate noise, and 30% for dephasing noise.
Quantum error correction and fault-tolerance have provided the possibility for large scale quantum computations without a detrimental loss of quantum information. A very natural class of gates for fault-tolerant quantum computation is the Clifford gate set and as such their usefulness for universal quantum computation is of great interest. Clifford group gates augmented by magic state preparation give the possibility of simulating universal quantum computation. However, experimentally one cannot expect to perfectly prepare magic states. Nonetheless, it has been shown that by repeatedly applying operations from the Clifford group and measurements in the Pauli basis, the fidelity of noisy prepared magic states can be increased arbitrarily close to a pure magic state~\cite{Bravyi}. We investigate the robustness of magic state distillation to perturbations of the initial states to arbitrary locations in the Bloch sphere due to noise. Additionally, we consider a depolarizing noise model on the quantum gates in the decoding section of the distillation protocol and demonstrate its effect on the convergence rate and threshold value. Finally, we establish that faulty magic state distillation is more efficient than fault-tolerance-assisted magic state distillation at low error rates due to the large overhead in the number of quantum gates and qubits required in a fault-tolerance architecture. The ability to perform magic state distillation with noisy gates leads us to conclude that this could be a realistic scheme for future small-scale quantum computing devices as fault-tolerance need only be used in the final steps of the protocol.
We consider a model of quantum computation in which the set of elementary operations is limited to Clifford unitaries, the creation of the state $\ensuremath{\mid}0⟩$, and qubit measurement in the computational basis. In addition, we allow the creation of a one-qubit ancilla in a mixed state $\ensuremath{\rho}$, which should be regarded as a parameter of the model. Our goal is to determine for which $\ensuremath{\rho}$ universal quantum computation (UQC) can be efficiently simulated. To answer this question, we construct purification protocols that consume several copies of $\ensuremath{\rho}$ and produce a single output qubit with higher polarization. The protocols allow one to increase the polarization only along certain ``magic'' directions. If the polarization of $\ensuremath{\rho}$ along a magic direction exceeds a threshold value (about 65%), the purification asymptotically yields a pure state, which we call a magic state. We show that the Clifford group operations combined with magic states preparation are sufficient for UQC. The connection of our results with the Gottesman-Knill theorem is discussed.