Short answer: The threshold theorem says quantum computation can be made fault-tolerant against errors when the error rate is below a constant threshold. Aharonov and Ben-Or proved a version of it in a paper that improved on an earlier result by Shor, which needed the error rate to shrink as the computation grew. Their own estimate of the threshold was about 1 in a million in the best case. This is a theoretical result from the late 1990s, and later work has studied other codes and thresholds.
What the theorem says
The abstract of the paper "Fault-Tolerant Quantum Computation with Constant Error Rate", by Dorit Aharonov and Michael Ben-Or, says it proves the threshold result: quantum computation can be made robust against errors and inaccuracies when the error rate, called eta, is smaller than a constant threshold. The version published in the SIAM Journal on Computing describes eta as the probability for an error in a qubit or a gate.
What it improved
The paper says it improves on Shor's result, which shows how to perform fault-tolerant quantum computation when the error rate decays polylogarithmically with the size of the computation. The authors call that assumption physically unreasonable. Their construction handles a constant error rate instead, and they say the cost of making the circuit fault-tolerant is polylogarithmic in time and space.
What kinds of noise it covers
The journal abstract says the result holds for a very general local noise model that includes probabilistic errors, decoherence, amplitude damping, depolarization and systematic inaccuracies in the gates. It also allows exponentially decaying correlations between errors, both in space and in time. The arXiv abstract says the result holds for a general noise model that is not necessarily probabilistic, and for quantum particles with any number of states.
The paper also says fault-tolerant computation can be performed with any universal set of gates, and that the result generalizes to one-dimensional quantum computers with only nearest-neighbour interactions. It states that no measurements or classical operations are required during the quantum computation.
The threshold estimate
The authors estimate the threshold of their construction to be about 10 to the power minus 6, in the best case. An earlier version of the paper, from 1996, uses concatenated quantum error-correcting codes and says the threshold is about 10 to the power minus 6 with its codes. It adds the hope that the paper motivates a search for proper quantum codes with higher thresholds, at which point quantum computation becomes practical. In other words, the figure belongs to the specific construction in that paper and is not a fundamental limit.
What this does not tell you
This article summarises the abstracts of three versions of one paper. It does not say what error rates any current device reaches, and it does not describe any later threshold estimates, which depend on the code and the noise model used.
FAQ
What is the threshold theorem?
A result that quantum computation can be made robust against errors when the error rate is below a constant threshold, proved by Aharonov and Ben-Or according to the paper's abstract.
What did it improve?
Shor's earlier result, which required the error rate to decay polylogarithmically with the size of the computation. The authors call that assumption physically unreasonable.
Does it need measurements during the computation?
The abstract says no measurements or classical operations are required during the quantum computation.
What threshold did the authors estimate?
About 10 to the power minus 6, in the best case, for their construction. They hoped codes with higher thresholds would be found.
Does it cover correlated noise?
The journal abstract says it allows exponentially decaying correlations between errors in space and in time.
All field notes