## 2 Quantum Turing Machines
### Local Conditions for Unitary Evolution  
In analogy to the main approaches in the literature [12,18], it is possible to state a set of local condition for the quantum transition function \(\delta_{0}\) of pQTMs in order to ensure that the time evolution operator is unitary. **Theorem 1**. : _Let \(M\) be a pQTM with quantum transition function \(\delta_{0}\). The time evolution operator \(U_{M}:\ell^{2}(\mathfrak{C}_{M})\to\ell^{2}(\mathfrak{C}_{M})\) of \(M\) is unitary if and only if \(\delta_{0}\) satisfies the local conditions:_  
1. _for any_ \((q,a)\in(\mathcal{Q}\setminus\mathcal{Q}_{t})\times\Sigma\)__ \[\sum_{(p,b,d)\in(\mathcal{Q}\setminus\mathcal{Q}_{s})\times\Sigma\times \mathbb{D}}|\delta_{0}(q,a)(p,b,d)|^{2}=1\]
2. _for any_ \((q,a),(q^{\prime},a^{\prime})\in(\mathcal{Q}\setminus\mathcal{Q}_{t})\times\Sigma\) _with_ \((q,a)\
eq(q^{\prime},a^{\prime})\)__ \[\sum_{(p,b,d)\in(\mathcal{Q}\setminus\mathcal{Q}_{s})\times\Sigma\times \mathbb{D}}\delta_{0}(q^{\prime},a^{\prime})(p,b,d)^{*}\delta_{0}(q,a)(p,b,d)=0\]
3. _for any_ \((q,a,b),(q^{\prime},a^{\prime},b^{\prime})\in(\mathcal{Q}\setminus\mathcal{Q }_{t})\times\Sigma^{2}\)__ \[\sum_{p\in(\mathcal{Q}\setminus\mathcal{Q}_{s})}\delta_{0}(q^{\prime},a^{\prime} )(p,b^{\prime},L)^{*}\delta_{0}(q,a)(p,b,R)=0\]  
_where \(()^{*}\) denote the complex conjugate operator._  
Proof. : We show that, to any QTM \(M\) (as defined above), we can associate a B&V QTM \(N\), which differs on the behaviour on source and target states only. The unitarity of \(M\) follows then from the unitarity of \(N\). Let \(M=\langle\Sigma,\mathcal{Q},\mathcal{Q}_{s},\mathcal{Q}_{t},\delta_{0},q_{i},q _{f}\rangle\). We take the B&V QTM \(N\) with the same states \(\mathcal{Q}\) and the same alphabet \(\Sigma\), and whose transition function \(\rho\) satisfies the following conditions:  
1. \(\rho\) is the same of the transition function \(\delta_{0}\) of \(M\) for any non-terminal state;
2. for any terminal state \(q_{t}\) and every current symbol \(u\), \(\rho\) has a unique non-null transition, with weight \(1\), that leaves the current symbol on the tape unchanged, moves the head to the right, and goes into an initial state \(q_{s}\); and,
3. the non-null out transitions from two distinct terminal states lead to two distinct source states, defining in this way a bijection between the set of the target and source states. In other words, \(\rho\) is defined by:  
\[\rho(q,u)(p,v,d) =\delta_{0}(q,u)(p,v,d) \text{for }q\in\mathcal{Q}\setminus\mathcal{Q}_{t},p\in \mathcal{Q}\setminus\mathcal{Q}_{s},u,v\in\Sigma,\,d\in\mathbb{D}\] \[\rho(q,u)(s,v,d) =0 \text{for }q\in\mathcal{Q}\setminus\mathcal{Q}_{t},s\in \mathcal{Q}_{s},u,v\in\Sigma,\,d\in\mathbb{D}\]  
and, assuming \(\mathcal{Q}_{s}=\{s_{i}\}_{0\leq i\leq k}\) and \(\mathcal{Q}_{t}=\{t_{i}\}_{0\leq i\leq k}\)  
\[\rho(t_{i},u)(s_{i},u,R) =1 \text{for }u\in\Sigma\] \[\rho(t_{i},u)(s_{i},v,L) =0 \text{for }u,v\in\Sigma\] \[\rho(t_{i},u)(q,v,d) =0 \text{for }q\in\mathcal{Q}\setminus\mathcal{Q}_{t},q\
eq s_{i},u,v\in \Sigma,\,d\in\mathbb{D}\]The above definition ensures that \(N\) is a B&V QTM whose configurations are the plain configurations of \(M\), and s.t. its transition function \(\rho\) verifies B&V local conditions. By B&V, the evolution operator \(U_{N}\) of \(N\) is then a unitary operator on the Hilbert space of the plain configurations of \(N\) and, as a consequence, its adjoint \(U_{N}^{*}\) is its inverse.