Fault-tolerant quantum computation with constant error

Abstract

In the past year many developments have taken place in the area of quantum error corrections. Recently Shor showed how to perform fault tolerant quantum computation when, ~, the probability for a fault in one time step per qubit or per gate, is polylogarithmically small. This paper closes the gap and shows how to perform fault tolerant quantum computation when the error probability, q, is smaller than some constant threshold, q.. The cost is polylogarithmic in time and space, and no measurements are used during the quantum computation. The same result is shown also for quantum circuits which operate on nearest neighbors only. To achieve this noise resistance, we use concatenated quantum error correcting codes. The scheme presented is general, and works with any quantum code, that satisfies certain restm”ctions, namely that it is a “proper quantum code”. The constant threshold r10 is a function of the parameters of the specifc proper code used. We present two explicit classes of proper quantum codes. The first class generalizes classical secret sharing with polynomials. The codes are defined over a field with p elements, which means that the elementary quantum particle is not a qubit but a “qupit”. The second class uses a known class of quantum codes and converts it to a proper code. We estimate the threshold qO to be = 10-6. Hopefully, this paper motivates a search for proper quantum codes with higher thresholds, at which point quantum computation becomes practical.