  In theory, quantum computers can efficiently simulate quantum physics, factor
large numbers and estimate integrals, thus solving otherwise intractable
computational problems. In practice, quantum computers must operate with noisy
devices called ``gates'' that tend to destroy the fragile quantum states needed
for computation. The goal of fault-tolerant quantum computing is to compute
accurately even when gates have a high probability of error each time they are
used. Here we give evidence that accurate quantum computing is possible with
error probabilities above 3% per gate, which is significantly higher than what
was previously thought possible. However, the resources required for computing
at such high error probabilities are excessive. Fortunately, they decrease
rapidly with decreasing error probabilities. If we had quantum resources
comparable to the considerable resources available in today's digital
computers, we could implement non-trivial quantum computations at error
probabilities as high as 1% per gate.
