From: Rick Osborne <osborne@gateway.grumman.com>
Date: Wed, 18 Sep 1996 19:48:30 +0800
To: cypherpunks@toad.com
Subject: Re: Quantum Computers
Message-ID: <3.0b16.32.19960918050947.00539aa0@gateway.grumman.com>
MIME-Version: 1.0
Content-Type: text/plain


I rather enjoyed this article, especially the part about:

>It gets even wilder, because the quantum mechanical state of the
>matter in the machine's memory determines the output, Seth Lloyd 
>of MIT thinks you could run the machine in  reverse and the result 
>would be a quantum mechanical micromanipulator.

This was great!  So where do we plug in the nice hot cup of tea? ;^)

I'm sorry if I seem to be making light of a very serious topic, but, last
time I checked, computers don't have a reverse.  Spam me, flame me,
whatever, but as far as I know, the universe only goes in one direction.
It's just a rehash of the old sci-fi dramas about building a computer that
goes on and builds a smarter computer, ad infinitum.  That's one of the
problems of non-sentient things: they can't grasp anything beyond their
scope.  But, for argument's sake, let's assume:

1. This quantum computer, which looks startlingly like my HP48, has a
slider labeled:
  FORWARD -- STOP -- REVERSE
   And the slider actually works.
2. We are working with a finite-state quantum computer (say 32 qbits worth).
3. There is NO error introduced into the system from any source, including
itself.

Okay, so I turn my little QC48 on, just to set a state, and then slam the
slider into REVERSE.  AT this point, it fizzles and dies.  Why?  Because of
the same reason you can't just put the DES algorithm 'in reverse': the
quantum equivalent of s/p-boxes.

What am I talking about?  I'm talking about a QUANTUM COMPUTER here.
Remember it's greatest asset?  It does every calculation at once.  This is
exactly why you can't go backwards.  You have nowhere to go, because you
have EVERYWHERE to go.  Because at each 'quantum tick' of the 'quantum
clock' EVERY possible operation is going on, each state has the possibility
of leading to every other state.

Now, let's throw out assumption #3, and deal with a slightly more realistic
version of my QC48, the QC48SX.

Because we're dealing with a computer that produces error in it's own
system, the error is going to be relatively hard to keep track of.  Notice
that the error-correction schemes listed don't eliminate error, they just
help thin it out.  So you've got your result to the operation you just
performed:
  OP1 + OP2 + OPERR = RESULT
The error-correction protocol makes OPERR small, but it doesn't eliminate
it.  So this is when I throw it into reverse.  (Sure, I could have kept
track of all my operations up to that point and trace back along them with
no problem, but I can only do that until the point at which I turned on my
QC48SX, so let's just assume I didn't keep track.)  I've got RESULT now,
and with a reasonable degree of accuracy, I can statistically figure out
what two states led up to that point, with a margin of error STATERR.  This
is made even tougher by the fact that there was an error (OPERR) in the
system to begin with.  Remember now, every state can lead to every other
state, but let's assume we've got NSA-level statisticians here, and STATERR
is relatively small.  You now have STATERR*OPERR working against you.  This
is where working in a finite-state machine is good, as it keeps these
values relatively small.  But they are still there.  These errors, in
combination with the quantum-s/p-box factor, precludes you from going
backwards with any degree of reliability.

Like I said, I'm not trying to tear down anyone hopes and ideas, I just
want to introduce a little *reality* into our system.


____________________________________________________________
Rick Osborne                     osborne@gateway.grumman.com
"Yes, evil comes in many forms, whether it be a man-eating
 cow or Joseph Stalin, but you can't let the package hide
 the pudding!  Evil is just plain bad!  You don't cotton to
 it.  You gotta smack it in the nose with the rolled-up
 newspaper of goodness!  Bad dog!  Bad dog!" - The Tick