[107778] in Cypherpunks
Quantum Computers and Muliple Universes
daemon@ATHENA.MIT.EDU (Tim May)
Sat Jan 23 03:00:22 1999
In-Reply-To: <000d01be4697$fb289760$5c8195cf@blanc>
Date: Fri, 22 Jan 1999 23:46:42 -0800
To: cypherpunks@cyberpass.net
From: Tim May <tcmay@got.net>
Reply-To: Tim May <tcmay@got.net>
At 10:10 PM -0800 1/22/99, Blanc wrote:
>
>What are you going to do with those quantum computations?
>
Beats me.
I'm reading a new book on quantum computers, "Explorations in Quantum
Computing," Colin Williams and Scott Clearwater. Interestingly, the
examples are all worked out in Mathematica, on a CD-ROM, and Mathematica
happens to be my current favorite language for playing around with things
like this.
I'm skeptical, as always, that quantum computers will be practical. But the
demonstration that one can be built will have some mighty interesting
philosophical ramifications. I'm one who agrees with David Deutsch, that
the Many Worlds Interpretation stops being just an _interpretation_ of QM
and becomes, almost provably, the actual reality.
For example, if a 250-digit number is factored with a quantum computer, the
roughly 10^500 computations which a classical, ordinary computer would be
doing would be accomplished in a few thousand steps of the machine, maybe
less.
So, where did the computations get done? Saying the quantum computer
operates on "mixed states" is misleading, in my view. As Deutsch puts it:
"To those who still cling to a single-universe world-view, I issue this
challenge: explain how Shor's algorithm works. I do not merely mean predict
that it will work, which is merely a matter of solving a few
uncontroversial equations. I mean provide an explanation. When Shor's
algorithm has factorized a number, using 10^500 or so times the
computational resources that can be seen to be present, where was the
number factorized?" (in his excellent book, "The Fabric of Reality.")
In the most straightforward interpretation, the Shor algorithm for
factoring (or the Grover algorithm for searching, etc.) means that when a
computation is begun, the computation is spawned into millions, billions,
trillions,... of "other worlds" which are all working on parts of the
computation. Then the universes "interfere" and the correct answer pops out.
A readable introduction to these ideas, besides the Deutsch book, is the
science fiction novel "Paths to Otherwhere," by by James Hogan.
Not all who work in the developing field of quantum computing subscribe to
Deutsch's world-view. And there are issues of coherence and maintaining the
"entanglements" for the computation.
In other words, there are practical considerations.
And there may even be theoretical reasons (as yet unidentified by anyone)
which preclude such computers being built.
I'm much less interested in the practical consequences. For example,
whether this means RSA is not safe for the kinds of time periods we expect
it be so. Rather, I'm more interested in satisfying my own curiousity about
whether such a machine is even possible--and about whether there are
alternative explanations to the one Deutsch proposes so strongly.
By the way, many of our familiar cryptologists are working in aspects of
this field. Besides Bob and Alice, we see names like Brassard, Yao, etc.
And there are links to the theory of computation, the physical basis of
computation, entropy, randomness, reversibility, and other topics of
longstanding interest.
This should answer your question about what I'm going to do with those
quantum computations.
--Tim May
Y2K -- Where were you when the lights went out?
---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May | Crypto Anarchy: encryption, digital money,
ComSec 3DES: 831-728-0152 | anonymous networks, digital pseudonyms, zero
W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets,
Licensed Ontologist | black markets, collapse of governments.
