## 2 Quantum Turing Machines
### Time Evolution Operator and QTM  
In order to define the evolution operator of a pQTM \(M\), it suffices to give its behaviour on the computational basis \(\mathsf{CB}(\mathfrak{E}_{M})\). In particular, we have to distinguish three cases:  
1. \(C\in\mathfrak{C}^{0}_{M}\setminus\mathfrak{E}^{t}_{M}\). Let \(C_{p,p,d}\in\mathfrak{E}^{0}_{M}\setminus\mathfrak{E}^{s}_{M}\) be the configuration obtained by leaving the counter to \(0\), by replacing the symbol \(u\) in the current cell with the symbol \(v\), by moving the head on the \(d\) direction, and by setting the machine into the new state \(p\). In detail, if \(C\simeq\langle\alpha w,q,u\beta,i,0\rangle\) we have \[C_{p,p,d}\simeq\begin{cases}\langle\alpha wv,p,\beta,i+1,0\rangle&\text{when $d=R$}\\ \langle\alpha,p,wv\beta,i-1,0\rangle&\text{when $d=L$.}\end{cases}\] and we define \[W_{0,M}(|C\rangle)=\sum_{(p,p,d)\in(\langle\lambda\setminus\mathfrak{E}_{s} \rangle\times\Sigma\times\mathbb{D}}\delta_{0}(q,u)(p,v,d)\,|C_{p,p,d}\rangle\] where \(\delta_{0}\) is the quantum transition function of \(M\), and, as already introduced at the end of Section 2.3, \(C_{p,v,d}\) is the new configuration obtained from \(C\) by changing the current state from \(q\) to \(p\), by replacing the current symbol \(u\) with \(v\), and by moving the tape head in the direction \(d\).
2. \(C\in\mathfrak{E}^{s}_{M}\setminus\mathfrak{E}^{0}_{M}\). Let \(C_{-1}\in\mathfrak{E}^{s}_{M}\) be the source configuration obtained by decreasing by \(1\) the counter of \(C\), we define \[W_{s,M}(|C\rangle)=|C_{-1}\rangle\]
3. \(C\in\mathfrak{E}^{t}_{M}\). Let \(C_{+1}\in\mathfrak{E}^{t}_{M}\setminus\mathfrak{E}^{0}_{M}\) be the target configuration obtained by increasing by \(1\) the counter of \(C\), we define \[W_{t,M}(|C\rangle)=|C_{+1}\rangle\] We have then three linear operators \[W_{0,M}:\mathsf{span}(\mathsf{CB}(\mathfrak{E}^{0}_{M}\setminus \mathfrak{E}^{t}_{M}))\rightarrow\mathsf{span}(\mathsf{CB}(\mathfrak{E}^{0}_ {M}\setminus\mathfrak{E}^{s}_{M}))\] \[W_{s,M}:\mathsf{span}(\mathsf{CB}(\mathfrak{E}^{t}_{M})\setminus \mathfrak{E}^{0}_{M}))\rightarrow\mathsf{span}(\mathsf{CB}(\mathfrak{E}^{t}_ {M}\setminus\mathfrak{E}^{0}_{M}))\] defined on three disjoint subspaces. Moreover, because even the images of these three operators are disjoint, their sum \[W_{M}=W_{0,M}+W_{s,M}+W_{t,M}\]defines an automorphism on the linear space of q-configurations  
\[W_{M}:\mathsf{span}(\mathsf{CB}(\mathfrak{C}))\to\mathsf{span}(\mathsf{CB}( \mathfrak{C})).\]  
Indeed, since \(W_{M}\) is bounded, it extends in a unique way to a continuous operator on the Hilbert space of q-configurations.  
**Definition 6** (time evolution operator).: _The time evolution operator of \(M\) is the unique continuous extension_  
\[U_{M}:\ell^{2}(\mathfrak{C}_{M})\to\ell^{2}(\mathfrak{C}_{M})\]  
_of the bounded linear operator \(W_{M}:\mathsf{span}(\mathsf{CB}(\mathfrak{C}))\to\mathsf{span}(\mathsf{CB}( \mathfrak{C})).\)_  
As it is the case for the operator \(W_{M}\), also the time evolution operator \(U_{M}\) can be decomposed into three operators  
\[U_{0,M} :\ell^{2}(\mathfrak{C}_{M}^{0}\setminus\mathfrak{C}_{M}^{t})\to \ell^{2}(\mathfrak{C}_{M}^{0}\setminus\mathfrak{C}_{M}^{s})\] \[U_{s,M} :\ell^{2}(\mathfrak{C}_{M}^{s}\setminus\mathfrak{C}_{M}^{0})\to \ell^{2}(\mathfrak{C}_{M}^{s})\] \[U_{t,M} :\ell^{2}(\mathfrak{C}_{M}^{t})\to\ell^{2}(\mathfrak{C}_{M}^{t} \setminus\mathfrak{C}_{M}^{0})\]  
s.t.  
\[U_{M}=U_{0,M}+U_{s,M}+U_{t,M}.\]  
**Definition 7** (Qtm).: _A pQTM is a Quantum Turing Machine (QTM) when its time evolution operator \(U_{M}\) is unitary._  
As usual, \(U_{M}^{i}\) (the \(i\)-th iterate of \(U_{M}\)) is defined as \(U_{M}^{0}=id\), and \(U_{M}^{i+1}=U_{M}\circ U_{M}^{i}\).