In a Quantum Turing Machine, how is the decision to move along the memory tape made?

Question

Let, for a Quantum Turing machine (QTM), the state set be $Q$, and the alphabet of symbols be $\sum=\{0,1\}$, which appear at the tape head. Then, as per my understanding, at any given time while the QTM is calculating, the qubit that appears at its head will hold an arbitrary vector $V_\sum = a|1\rangle+b|0\rangle$. Also, if $|q_0\rangle , |q_1\rangle, ... \in Q$, then the state vector at that instance will also be an arbitrary vector $V_q=b_0|q_0\rangle + b_1 |q_1\rangle+ ...$.

Now, after the instruction cycle is complete, the vectors $V_\sum$ and $V_q$ will decide whether the QTM will move left or right along the Qubit tape. My question is- since Hilbert space formed by $Q \otimes \sum$ is an uncountable infinite set and $\{\text{Left,Right}\}$ is a discrete set, the mapping between them will be difficult to create.

So how is the decision to move left or right made? Does the QTM move both left and right at the same time, meaning that the set $\{\text{Left,Right}\}$ also forms a different Hilbert space, and hence the motion of the QTM becomes something like $a|\text{Left}\rangle+b|\text{Right}\rangle$.

Or, just like a Classical Turing machine, the QTM moves either left or right, but not both at the same time?

Answer 1

If we have a QTM with state set $Q$ and a tape alphabet $\Sigma = \{0,1\}$, we cannot say that the qubit being scanned by the tape head "holds" a vector $a|0\rangle + b|1\rangle$ or that the (internal) state is a vector with basis states corresponding to $Q$. The qubits on the tape can be correlated with one another and with the internal state, as well as with the tape head position.

As an analogy, we would not describe a probabilistic Turing machine's global state by independently specifying a distribution for the internal state and for each of the tape squares. Rather, we have to describe everything together so as to properly represent correlations among the different parts of the machine. For example, the bits stored in two distant tape squares might be perfectly correlated, both 0 with probability 1/2 and both 1 with probability 1/2.

So, in the quantum case, and assuming we're talking about pure states of quantum Turing machines with unitary evolutions (as opposed to a more general model based on mixed states), the global state is represented by a vector whose entries are indexed by configurations (i.e., classical descriptions of the internal state, the location of the tape head, and the contents of every tape square) of the Turing machine. It should be noted that we generally assume that there is a special blank symbol in the tape alphabet (which could be 0 if we want our tape squares to store qubits) and that we start computations with at most finitely many squares being non-blank, so that the set of all reachable configurations is countable. This means that the state will be represented by a unit vector in a separable Hilbert space.

Finally, and perhaps this is the actual answer to the question interpreted literally, the movement of the tape head is determined by the transition function, which will assign an "amplitude" to each possible action (new state, new symbol, and tape head movement) for every classical pair $(q,\sigma)$ representing the current state and currently scanned symbol. Nothing forces the tape head to move deterministically -- a nonzero amplitude could be assigned to two or more actions that include tape head movements to both the left and right -- so it is possible for a QTM tape head to move both left and right in superposition.

For example, you can imagine a QTM with $Q = \{0,1\}$ and $\Sigma = \{0,1\}$ (and we'll take 0 to be the blank symbol). We start in state 0 scanning a square that stores 1, and all other squares store 0. I won't explicitly write down the transition function, but will just describe the behavior in words. On each move, the contents of the scanned tape square is interpreted as a control bit for a Hadamard operation on the internal state. After the controlled-Hadamard is performed, the head moves left if the (new) state is 0 and moves right if the (new) state is 1. (In this example we never actually change the contents of the tape.) After one step, the QTM will be in an equally weighted superposition between being in state 0 with the tape head scanning square -1, and being in state 1 with the tape head scanning square +1. On all subsequent moves the controlled-Hadamard does nothing because every square aside from square 0 contains the 0 symbol. The tape head will therefore continue to move simultaneously both left and right, like a particle travelling to the left and to the right in superposition.

If you wanted to, you could of course define a variant of the quantum Turing machine model for which the tape head location and movement is deterministic, and this would not ruin the computational universality of the model, but the "classic" definition of quantum Turing machines does not impose this restriction.

Answer 2

The quantum Turing machine can move into a superposition of moving left and right. This is different from the classical Turing machine which can only move either left or right.