1994-07-22 - Re: GUT and P=NP

Header Data

From: rjc@gnu.ai.mit.edu (Ray)
To: cypherpunks@toad.com
Message Hash: e2f9583e7ee5b4a219e28f80c6098c2ace82c4b97fbe737d7274fe057f438b0a
Message ID: <9407220444.AA20360@geech.gnu.ai.mit.edu>
Reply To: N/A
UTC Datetime: 1994-07-22 04:44:13 UTC
Raw Date: Thu, 21 Jul 94 21:44:13 PDT

Raw message

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







Thread