Re: Quantum computer : dream or a reality?

From: Bill Unruh (unruh_at_string.physics.ubc.ca)
Date: 06/23/04 

Date: Tue, 22 Jun 2004 23:46:27 +0000 (UTC)

codemutant@programmer.net (Codemutant) writes:

]Well... r u saying that even if the QC is build... with the current
]private key methods it doesnt pose a problem... but the other public
]keys like RSA/DES are vulnerable???

A qualified Yes.

There is an algorithm, called the Grover Search algorithm which allows a
search of 2^L item database in 2^L/2 Quantum operations. Thus this would in
principle reduce a 128 bit key to an effective length of 64 bits. But 2^64
bits is still a huge number of operations, and the probability of keeping
the QC coherent even with error correction through that many operations is
negligible.

For RSA a 1000 bit key which would take 2^1000 operations by brute force,
would only take about 10^6 operations by a QC.
Ie, and exponential reduction.