QCF_dec

[John Young <jya@pipeline.com>]

   Science, 8 December 1995


   Quantum Computers, Factoring, and Decoherence

   I. L. Chuang, R. Laflamme, P. W. Shor, W. H. Zurek

   [First paragraph] The uniqueness of the prime
   factorization of a positive integer is the Fundamental
   Theorem of Arithmetic. In practice, the determination of
   the prime factors of a given number can be an exceedingly
   difficult problem, even though verification is trivial.
   This asymmetry is the basis for modern cryptography and
   provides secret codes used not only on your own bank card
   but also to transfer diplomatic messages between embassies.


   [Precis] 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 ~L^2 time [compared to ~exp(L^1/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, Stanford University.

   R. Laflamme and W. H. Zurek, Los Alamos National Laboratory.

   P. W. Shor, AT&T Bell Labs.

   ----------

   QCF_dec (18 kb)

   Sent with compressed qcf1.jpg of 14 equations and 2 
   figures (31 kb)