From: jamesd@netcom.com (James A. Donald)
Date: Mon, 25 Jul 94 20:09:06 PDT
To: m5@vail.tivoli.com (Mike McNally)
Subject: Re: GUT and P=NP
In-Reply-To: <9407242215.AA06910@vail.tivoli.com>
Message-ID: <199407242334.QAA28120@netcom13.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


> James A. Donald writes:
> > One can reduce all classical operations to "and", "or", and "not"
> > operations on bits.   Quantum computers include an additional 
> > operation that cannot be so reduced.
> 
Mike McNally writes
> Could you break the suspense and let us know what this special new
> operator is?

The new operator is a unitary transformation on a single bit.

Note that I am using the word "unitary" in the sense of
quantum physics, not in the sense of C language syntax
(That is unitary, not unary)

Actually this a three dimensional continuous class of
transformations.  Because it is continuous, quantum
computers tend to rapidly lose precision.

Just as any classical physical system can be simulated in
polynomial time by a Turing machine using only the operations
of boolian arithmetic, in the same way any quantum physical
system can be simulated in polynomial time using only the
operations of boolian arithmetic plus unitary transformations
on individual bits.

Of course actually building a quantum computer using only these
operations would be rather silly.  In practice one would need
to use unitary three bit operations for reasons of efficiency.

-- 
 ---------------------------------------------------------------------
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