2
$\begingroup$

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?

$\endgroup$

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.