A New Model for the Quantum Turing Machine
A Quantum Turing Machine (QTM) adds to the Classic Turing Machine (TM) the ability to move both to the right AND left at the same time and/or write both a one AND a zero to the tape at the same time. The state of the machine after one step is a superposition of all the possible final states.A QTM probably cannot compute the incomputable--that is, only algorithms can be performed. However, the complexity class of the algorithms can be changed. Simply put, a QTM can be faster than a TM in certain circumstances.
However, the algorithms for QTMs are nasty business. Is there an equivalent mechanism that can compute algorithms in the same time as a QTM that may allow easier algorithm design?
I think so. First, let me say that no classical machine can do it, so whatever that mechanism looks like is going to be pretty weird (just as the QTM is pretty weird). But this weirdness shouldn't dissuade us from exploring a new mechanism. The payoff may be a simpler language for algorithm design.
The Negative Delay Turing Machine (NDTM)
Add a unit to the TM between the output from the table and the input to the tape-writing mechanism whichhas a negative time delay. (I told you this would be weird.) This delay needs to have a magnitude greater than the positive delay of all the other working parts. That is, the output of the machine can be written to the tape before the input is read!This conceptually simple device may have the same complexity power as the QTM. The reason I suspect this is because a time-reversed XOR gate leads to a superposition of states on the input side.
The Time Reversed XOR
Think of a regular XOR gate. We are all familiar with the logic involved:| P | Q | R |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
If we imagine running this gate in reverse, feeding in a 0 at R gives us a superposition of states (P=0,Q=0) and (P=1,Q=1). We can imagine testing either P and finding a1 and then knowing (without testing) thatQ is 1. Sound familiar? Sounds like the wave collapse following the test of a state ofone of two entangled quanta.
And of course, feeding in a 1 gives us two entangled outputs where P = ~Q and again testing either gives us the other.
The XOR on a TM
The complete description of the TM which can perform as an XOR gate is as follows:- 5 definitions here
The reversed XOR on a NDTM
The complete description of the NDTM which can perform as a time-reversed XOR is as follows:- 6 definitions here
The reversed XOR on a QTM
The complete description of the QTM which can perform as a time-reversed XOR is as follows:- 6 definitions here
What does it mean?
If these last two are indeed equivalent, then the NDTM can (at least in some situations) model the QTM. This does not help us build such a device, of course, but it does give us a different conceptual platform for which to design algorithms.Once the equivalency is proven, there is a procedure for converting algorithms designed for the NDTM to algorithms for the QTM. One way is to complete the definitions for NDTM and QTM for enough different gates to cover all logical propositions. Then, simply convert the logical workingsof the NDTM into the appropriate gate diagrams, and the algorithm that worked on the NDTM becomes the same series of gate-steps for the QTM.
More important, as long as this is theoretically possible, algorithms can be written exclusively for the NDTM and an automated compiler can covert for use on a QTM.
by Guy T. Schafer
(First published October 7, 2004)