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

*has 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:

Now imagine we have the output

**R** = 0.
What inputs were required on

**P** and

**Q**?
Obviously they were either both 0 or both 1.

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:

## The reversed XOR on a NDTM

The complete description of the NDTM which
can perform as a time-reversed XOR is as
follows:

## The reversed XOR on a QTM

The complete description of the QTM which
can perform as a time-reversed XOR is as
follows:

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