Re: Quantum Computation

From: Nick Maclaren (nmm1_at_cus.cam.ac.uk)
Date: 03/29/05 

Date: Tue, 29 Mar 2005 17:16:31 +0000 (UTC)

In article <2c4326c5.0503271729.6bcdb2f@posting.google.com>,
charles@connectfusion.com (Charles) writes:
|> I am a newbie to quantum computation and hope some experts can advise
|> me on the following question.
|>
|> Can a quantum computer of say, 128 qubits, speed up the computation of
|> *any* existing (classical) computer algorithm (and if so by what
|> order), or does it speed up only certain types of algorithms like
|> those introduced by Shor, Deutsch..etc ?

The latter. To a very good approximation, there is only one
practical problem that a quantum computer is known to solve
significantly faster than a deterministic one: integer
factorisation a.k.a. the discrete logarithm (Shor). Whether
there are any other problems that can be is an open question.

And, as I understand it, 128 qubits isn't interesting because
you need to store a whole modulus at once and practical ones
are 512 bits and up. Quantum computers become important only
when they can be built to factorise the moduli that are used
in software at the time.

Or that was my understanding the last time I looked. I should
appreciate any informed updates or corrections.

Regards,
Nick Maclaren.