## 2 Quantum Turing Machines
### Pre Quantum Turing Machines  
In order to formally define QTMs, we first define a notion of pre Quantum Turing Machine, or pQTM. As we shall see later (Definition 7), a QTM is a pQTM whose evolution operator is unitary. Because the behaviour on target states and on source states whose counter is greater than \(0\) is fixed, in order to completely describe a pQTM, it suffices to give a transition function \(\delta_{0}:((Q\setminus\mathcal{Q}_{t})\times\Sigma)\to\ell_{1}^{2}((Q \setminus\mathcal{Q}_{s})\times\Sigma\times\mathbb{D})\), which, for every configuration \(C\) with current state \(q\) and current symbol \(u\), gives the weight \(\delta_{0}(q,u)(p,v,d)\) of \(|C_{p,v,d}\rangle\) in the superposed configuration reached from \(|C\rangle\), where \(C_{p,v,d}\) is obtained by replacing \(v\) for \(u\), by moving the tape in the \(d\) direction, and by changing the current state to \(p\). **Definition 1** (Pre Quantum Turing Machine). : _Given a finite set of states \(\mathcal{Q}\) and an alphabet \(\Sigma\), a pre Quantum Turing Machine (pQTM) is a tuple_  
\[M=\langle\Sigma,\mathcal{Q},\mathcal{Q}_{s},\mathcal{Q}_{t},\delta_{0},q_{i},q _{f}\rangle\]  
_where_  
* \(\mathcal{Q}_{s}\subseteq\mathcal{Q}\) _is the set of source states of_ \(M\)_, and_ \(q_{i}\in\mathcal{Q}_{s}\) _is a distinguished source state named the initial state of_ \(M\)_;_
* \(\mathcal{Q}_{t}\subseteq\mathcal{Q}\) _is the set of target states of_ \(M\)_, and_ \(q_{f}\in\mathcal{Q}_{t}\) _is a distinguished target state named the final state of_ \(M\)_;_
* \(\mathcal{Q}_{s}\) _and_ \(\mathcal{Q}_{t}\) _have the same cardinality and_ \(\mathcal{Q}_{s}\cap\mathcal{Q}_{t}=\mathcal{Q}\)_;_
* \(\delta_{0}:((\mathcal{Q}\setminus\mathcal{Q}_{t})\times\Sigma)\to\ell_{1}^{2} ((\mathcal{Q}\setminus\mathcal{Q}_{s})\times\Sigma\times\mathbb{D})\) _is the quantum transition function of_ \(M\)_, where_ \(\mathbb{D}=\{L,R\}\)_._  
**Remark 1** (Source and target states). : _Source and target states must be introduced to complete a QTM when the transitions implementing its expected behaviour fail to assure the local conditions of Theorem 1, required to get a unitary time evolution operator. In particular, the first condition states that the norm of the vector \(\delta(q,u)\) corresponding to the transition from a configuration \(C\) with current state \(q\) and current symbol \(u\), to a superposed configuration \(\sum\delta(q,u)(p,v,d)|C_{p,v,d}\rangle\) must be equal to \(1\). Anyhow, in some case, the norm of the vector of the weights implementing the expected behavior of the machine might give a value smaller than \(1\), while, in no case, it cannot exceed the value of \(1\). To achieve the required local condition, we can add some new transitions to some special target state acting as a sink (i.e., from which the machine cannot get out), with a procedure reminding the one used to complete a non-deterministic automata by connecting all of the omitted transitions to a sink state. The main difference is that in the QTM case more than one target state may be necessary to achieve the goal. Moreover, because of the reversibility of QTMs, a similar condition must hold for the transitions entering into a given state. Accordingly, we must also take into account the case in which we need to complete the implementation of the expected behaviour by adding new transitions from some source states. Finally, we remark that the requirement that the sets of source and target states have the same cardinality is used to prove the unitarity of the evolution operator associated to our QTMs via a reduction to the B&V QTMs (see Theorem 1). We do have another, independent, and direct proof of this result (that we omit in this paper), and that also exploits the equinumosity of source and target states. We conjecture then that this is indeed a necessary condition._  
**Remark 2** (On godelization of QTMs). : _For a definition of godelizable QTMs, we must restrict the definition of the transition function to computable complex numbers (see also [12].