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