let's watch the sparks...i mean bits...fly!
joe
------- start of forwarded message (RFC 934 encapsulation) -------
From: Craig Fields <cfields@mit.edu>
To: kiniry@cs.caltech.edu
Subject: Re: see http://pest.w3.org/FoRK-archive/
Date: Sat, 21 Jun 1997 17:21:39 -0400
Poked around a bit. Looks fun. Noticed a question of yours, and an
answer to it that annoyed me. Feel free to forward this to the list if
it seems appropriate.
> Robert Harley (Robert.Harley@inria.fr)
> Tue, 17 Jun 1997 11:57:27 +0200 (MET DST)
>
> A quantum computer is a (non-human) device that flips a coin and
> records the answer in exactly the same way. As long as I don't
> observe the output, there is a superposition of all possible outputs
> including the correct one. The only problem is that the correct one
> is an exponentially weak component of the wave-function.
Not really. See below.
> The only thing quantum-computation guys haven't quite figured out yet
> is how to extract that signal reliably for n more than about 15.
No.
> In other words, quantum computation is currently a crock of shit.
As anything beyond theory, yes. On the other hand, nobody (er, maybe
nobody sane) claims it is anything beyond theory at this point.
However, it points in fascinating and useful directions for research
in both quantum mechanics and theory of computation.
> Joseph R. Kiniry (kiniry@cs.caltech.edu)
> Mon, 16 Jun 1997 23:39:16 -0700 (PDT)
>
> can some physicist explain to me, for instance, what the following can
> mean:
I'm not a physicist, but I wave my hands and pretend to be one in my
spare time.
> how does a machine "process" with bits that are both 0 _and_ 1?
The bits are represented by uncollapsed wave functions. A computation
on one of these is some physical process which transforms, but does
not collapse, the wave function in some way. The wave function may
(theoretically) represent any number of possibilities at varying
probabilities, and a transformation will alter the possibilities and
probabilities in the wave function.
The interesting thing that happens here is that the wave function
effectively represents any number of states simultaneously, and an
operation on that wave function is effectively a parallel
computation. If you can build hardware somehow that can muck with the
wave functions in such a way that they don't collapse, then you
effectively get infinite parallelism for free.
This idea had probably been around for a while, but didn't go far
because nobody had figured out, even theoretically, how to do anything
useful with it. So you can do this parallel computation on a zillion
numbers simultaneously, or whatever. When you finally observe the
answer, what do you get? You get whatever the wave function collapsed
to, which isn't terribly useful... Unless you've designed some clever
algorithm.
Two or three years ago Peter Shor (I believe) published a polynomial
time algorithm which is equivalent to factoring. At the end of the
computation, when you collapse the wave function, you have a 1 in 3
chance of getting the answer you wanted. If not, you rerun the
computation. (Or 2 in 3, or something large like that. Details.)
The field took off (became "hot") from there. Theoretically, this
stuff is very cool. Physically though, there are certainly some open
issues:
What the hell is a wave function anyway, and how complicated
can it really be? Can it really contain an infinite amount
of information, or do you start losing at some point? How do
you lose? I don't think there are any experiments here.
What exactly are the causes of wave function collapses, and
can they actually be avoided for long enough to get some
reasonable work done? This is not well understood either.
Directions for research.
> how does the observer know when to observe (to collapse the wave
> function)?
Don't really remember. I could guess, but I won't. I'm waving my hands
too much already.
> plus, as the article states a few paragraphs later, even
> if the gate speed of such a system were 0.1 milliseconds, the bits
> would have to remain in superposition for at least a year to
> complete a meaningful computation (in this case, factoring a
> 200-digit number). can anyone make a guess where they came up with
> this number?
Probably from the algorithm by Shor, or something similar. I can find
the paper again if you want. There was a "Quantum Computation Home
Page" or something a while back as well.
So my take on this is that the theoretical stuff is really cool, but
if you're looking for something beyond utterly trivial computations
it's anybody's guess as to whether any of this will ever work.
Craig
------- end -------