From: jamesd@netcom.com (James A. Donald)
Date: Mon, 25 Jul 94 19:53:11 PDT
To: m5@vail.tivoli.com (Mike McNally)
Subject: Re: GUT and P=NP
In-Reply-To: <9407251237.AA08406@vail.tivoli.com>
Message-ID: <199407251630.JAA29418@netcom8.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


James A. Donald writes:
>  > The new operator is a unitary transformation on a single bit. 

Mike McNally writes
> Ok, great.  So why is it that a description of a process to be
> followed by a quantum copmputer in order to produce some desired
> result not an algorithm just because it involves this operator?

Obviously one could choose to call these algorithms if one wished,
but such a name, if adopted, will obfuscate the fact that 
such things have very different properties, capabilities, and
limitations to conventional algorithms.

In particular the results of conventional complexity theory
obviously are largely irrelevant to quantum complexity theory,
which is why I made my original statement that the development
of quantum computers with capabilities that are impossible
for conventional computers cannot falsify existing complexity
theory and existing complexity theory cannot "disprove"
the alleged capabilities of quantum computers.

Very likely the name will be adopted but with a qualifier
"quantum algorithm".  In the event that quantum computers
become common (which I do not expect to happen for thirty
years or so)  I expect the phrase "quantum algorithm" will
be replaced by something shorter, so that we have one
word for algorithms, and another word for quantum algorithms.

We have wandered seriously off topic, and I will make
future replies in private email.


-- 
 ---------------------------------------------------------------------
We have the right to defend ourselves and our
property, because of the kind of animals that we              James A. Donald
are.  True law derives from this right, not from
the arbitrary power of the omnipotent state.                jamesd@netcom.com