I knew that we usually use circuit instead of Turing machine in Quantum computation.

In a deterministic Turing machine one has transition rules, $$ \delta: Q\times\Gamma\rightarrow Q\times\Gamma\times\{\pm 1, 0\}, $$ where $Q, \Gamma$ are set of states and symbols respectively. In the quantum Turing machine, we instead have, $$ \delta:Q\times\Gamma\rightarrow\mathbb{C}^{Q\times\Gamma\times\{\pm1,0\}}. $$ Suppose all that needed for the induced evolution $U_\delta$ being unitary. However, I feel tremendously obstructed when trying to construct even a toy example. Then I realize one difference between quantum circuit family and Turing machine when manipulating the computation is the following.

When constructing a quantum circuit, one could decide which qubit to act on, this decision is a classical advice that is precomputed before the quantum computating even started. When constructing a quantum Turing machine, we need to make sure that even the arrangement of gates must obeys the unitary property.

For instance, if we would like to apply $2$-local $U$ on a tape. Say, suppose the configuration in computational basis after truncated infinitely long tape is $|n,q\rangle|x_0,x_1\rangle$ where $n,q,x_i$ represents the current pointer location, state, and value of 2 cells on the tape. We would like to maps it to $|n,q\rangle U|x_0,x_1\rangle$, but unfortunately we could only apply our basic gate on $n,q, x_n$. In the circuit paradigm, we might use a trick that swaps information between $q$ and $x_0$ to perform multi-qubit gates. So we might say,

  1. Let $(q,s)\in Q=Q_L\times \Gamma$ composed of "logical state" and a dummy register state. Write computational basis as $|n,q,s,x_0,x_1\rangle$ and we starts at $|0,q,s,x_0,x_1\rangle$
  2. Interchange $s,x_n$, so $|0,q,s,x_0,x_1\rangle\mapsto|n,q,x_0,s,x_1\rangle$.
  3. Logical flip the pointer bit, $|n,q,s,x_0,x_1\rangle\mapsto|\lnot n,q,s,x_0,x_1\rangle$.
  4. Perform $2$-local operator $U$ on $s,x_n$, so $|1,q,s,x_0,x_1\rangle\mapsto|1,q\rangle U|s,x_1\rangle|x_0\rangle.$
  5. Swap back everything as prevously done, $|1,q,s,x_0,x_1\rangle\mapsto|0,q,x_0,s,x_1\rangle$.

But we cannot do this directly on quantum Turing machine, it is because we must also guarantee that the way we arrange these rules mentioned above should induce a unitary evolution. Even to simulate a classical Turing machine is non-trivial because though without superposition, in order to preserve unitary property, you need to permute classical states instead of making straight transition logic. I understand that quantum circuit is usually more used in the context of quantum computation, but at this stage even manipulating really simple rules are quite painful, in the above example, I even have to construct the states to transition cyclicly just to preserve unitary property.

If we would like to instantiate classical arrangements of quantum gates in a quantum Turing machine, is there better ways, perhaps more expressive, to constuct them explicitly?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.