From: gtoal@an-teallach.com (Graham Toal)
Date: Wed, 18 May 94 09:49:03 PDT
To: cypherpunks@toad.com
Subject: Re: quantum Computing
Message-ID: <199405181647.RAA02357@an-teallach.com>
MIME-Version: 1.0
Content-Type: text/plain


	this term keeps poping up recently.  Can anybody give me a pointer
	to where I can find out more info?  Someone said that it is nonsense,
	"quantum computers?, Isn't that something out of a carlos casteneda
	novel?" I'm just trying to find out the real deal.

It's purest bullshit: there are a class of mathematically difficult
problems called "NP-Complete".  These problems are all equivalent to
one another in difficulty, ie if you can solve one you can solve them
all (that's where the complete part comes is - it's NP-complete if
you can prove that equivalence to another NP-complete problem).

The "NP" part is "Non-deterministic, polynomial time".  What that means
is that there is a solution possible in polynomial time (rather than
exponential time) *ONLY* on a *NON-DETERMINISTIC* machine.  And that's
the fun part, because a non-deterministic machine is one that *guesses*
the correct path every time it has a choice to make.  It's like trying
to guess a 3-bit number, and saying "Is the first bit a 1?" Yes!  "Is the
second bit a 0?" Yes!  "Is the third bit a 0?"  Yes!

Clearly, in real life, this doesn't happen.  However, in fairy-tale land
(or quantum physics as it's called) such things *can* happen - because
one interpretation of the Einstein-Podolsky-Rosen thought experiment is
that every time you make a choice based on the outcome of a quantum
event, you fork off a pair of universes!  In one universe you make
one choice; in the other universe you made the other choice.  Consequently
if you loose a computer on such a problem, in *one* of the many many
universes it generates, it'll find the right answer in polynomial time.

The basis of quantum computing as a means to crack NP-complete problems
therefore reduces to finding which of these universes found the answer and
comminicating that answer to all the other universes.  (Of course, you
don't have to do this part, but the 99.9999999999999999999999999999999%
of experimenters in all the universes that didn't find the result are
not going to believe the method words too well...)

Basically, it's a theoretical result with no application in the real
world, and if ever anything happens that makes it mappable to the
real world we'll have been subjected to such a major upheaval in
the way the universe works that no-one will give a damn any more
about such trivial things as encryption because we'll all effectively
have turned into magicians :-)

G