QUANTUM COMPUTERS, FACTORING, AND DECOHERENCE

It is known that quantum computers can dramatically speed up the task of finding factors of large numbers, a problem of practical significan ce for cryptographic applications. Factors of an L-digit number can be found in similar to L(2) time [compared to similar to exp(L(1/3)) tim e] by a quantum computer, which simultaneously follows all paths corre sponding to distinct classical inputs, obtaining the solution from the coherent quantum interference of the alternatives. Here it is shown h ow the decoherence process degrades the interference pattern that emer ges from the quantum factoring algorithm. For a quantum computer perfo rming logical operations, an exponential decay of quantum coherence is inevitable. However, even in the presence of exponential decoherence, quantum computation can be useful as long as a sufficiently low decoh erence rate can be achieved to allow meaningful results to be extracte d from the calculation.