Quantum Computers, Factoring, and Decoherence
I. L. Chuang,
R. Laflamme,
P. W. Shor,
W. H. Zurek
It is known that quantum computers can dramatically speed up the
task of finding factors of large numbers, a problem of practical
significance for cryptographic applications. Factors of an
L-digit number can be found in 
L2
time [compared to exp(L1/3) time] by a
quantum computer, which simultaneously follows all paths corresponding
to distinct classical inputs, obtaining the solution from the coherent
quantum interference of the alternatives. Here it is shown how the
decoherence process degrades the interference pattern that emerges from
the quantum factoring algorithm. For a quantum computer performing
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
decoherence rate can be achieved to allow meaningful results to be
extracted from the calculation.
I. L. Chuang, Edward L. Ginzton Laboratory, Stanford University,
Stanford, CA 94305, USA.
R. Laflamme and W. H. Zurek, Theoretical Astrophysics, T-6, MS B288,
Los Alamos National Laboratory, Los Alamos, NM 87545, USA.
P. W. Shor, AT&T Bell Labs, 600 Mountain Avenue, Murray Hill, NJ 07974,
USA.
