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