  A quantum computer -- i.e., a computer capable of manipulating data in
quantum superposition -- would find applications including factoring, quantum
simulation and tests of basic quantum theory. Since quantum superpositions are
fragile, the major hurdle in building such a computer is overcoming noise.
  Developed over the last couple of years, new schemes for achieving fault
tolerance based on error detection, rather than error correction, appear to
tolerate as much as 3-6% noise per gate -- an order of magnitude better than
previous procedures. But proof techniques could not show that these promising
fault-tolerance schemes tolerated any noise at all.
  With an analysis based on decomposing complicated probability distributions
into mixtures of simpler ones, we rigorously prove the existence of constant
tolerable noise rates ("noise thresholds") for error-detection-based schemes.
Numerical calculations indicate that the actual noise threshold this method
yields is lower-bounded by 0.1% noise per gate.
