From: rjc@gnu.ai.mit.edu (Ray)
Date: Thu, 21 Jul 94 21:44:13 PDT
To: cypherpunks@toad.com
Subject: Re: GUT and P=NP
Message-ID: <9407220444.AA20360@geech.gnu.ai.mit.edu>
MIME-Version: 1.0
Content-Type: text/plain


James A. Donald writes:
> I was referring to the proposed quantum computers.
> >  > Since such machines do not operate algorithmically
> > 
> > This statement is exactly wrong.  Such machines *define* a class of
> > algorithms.

> I recommend that you read the following paper.

> E. Bernstein and U. Vazirani, {\it Quantum Complexity
> Theory}, Proc. 25th ACM Symp. on Theory of Computation, pp.  11--20
> (1993).

   James, without reading the paper, can you tell me why the following
argument is incorrect?

1) By definition, if something can be computed by a turing machine,
then it is an algorithm (Lewis and Papadimitriou)
2) a quantum computer can be simulated by a TM with exponential 
slowdown. (claimed by you on the Extropians list, but also
claimed by Feynmann I believe, not about qm computers, but qm systems
in general)

then by (1) and (2), it follows that
3) quantum computers are algorithmic (if not, it would contradict
2) and possibly 1)

   It doesn't matter how slow the turing machine runs the simulation
because we allow an arbitrary time along with the infinite tape
to complete the computation. 
-Ray