Efficient fault-tolerant quantum computing

Quantum computing(1)-the processing of information according to the fundamental laws of physics-offers a means to solve efficiently a small but significant set of classically intractable problems. Quantum computers are based on the controlled manipulation of entangled quantum states, which are extremely sensitive to noise and imprecision; active correction of errors must therefore be implemented without causing loss of coherence. Quantum error-correction theory(2-9) has made great progress in this regard, by predicting error-correcting 'codeword' quantum states. But the coding is inefficient and requires many quantum bits(10-12), which results in physically unwieldy fault-tolerant quantum circuits(10-18). Here I report a general technique for circumventing the trade-off between the achieved noise tolerance and the scale-up in computer size that is required to realize the error correction. I adapt the recovery operation (the process by which noise is suppressed through error detection and correction) to simultaneously correct errors and perform a useful measurement that drives the computation. The result is that a quantum computer need be only an order of magnitude larger than the logic device contained within it. For example, the physical scale-up factor(10,11) required to factorize a thousand-digit number is reduced from 1,500 to 22, while preserving the original tolerated gate error rate (10(-5)) and memory noise per bit (10(-7)). The difficulty of realizing a useful quantum computer is therefore significantly reduced.