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

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

Research output: Contribution to journalArticlepeer-review


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 measur√ng some designated qubit in the final state. Our main result is that for 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 = 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.

Original languageEnglish (US)
Pages (from-to)361-376
Number of pages16
JournalQuantum Information and Computation
Issue number5-6
StatePublished - May 1 2010


  • Fault-tolerance threshold
  • Noisy quantum computation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Statistical and Nonlinear Physics
  • Nuclear and High Energy Physics
  • Mathematical Physics
  • General Physics and Astronomy
  • Computational Theory and Mathematics


Dive into the research topics of 'Upper bounds on the noise threshold for fault-tolerant quantum computing'. Together they form a unique fingerprint.

Cite this