## 2 Quantum Turing Machines
### A Comparison with [PERSON]'s QTMs: Part 1  
We refer to B&V [12] for the precise definitions of the QTMs used in that paper. For the sake of readability, we informally recall the notion of what they call well formed, stationary, normal form QTMs (B&V-QTMs in the following).  
A B&V-QTM \(M=\langle\Sigma,\mathcal{Q},\delta,q_{0},q_{f}\rangle\) is defined as our QTM (with one source state and one target state only) with the following differences:the set of configurations coincides with all possible classical configurations, namely all the set \(\Sigma^{*}\times\Omega\times\Sigma^{*}\times\mathbb{Z}\);
2. no superposition is allowed in the initial q-configuration (it must be a classical configuration \(\langle\alpha,q,\beta,i\rangle\) with amplitude 1);
3. given an initial configuration \(|C\rangle\), the q-configuration \(\phi_{k}=U_{M}^{k}|C\rangle\) is the _final \(q\)-configuration_ for the computation starting in \(|C\rangle\), when: (i) all of the configurations in \(\phi_{k}\) are final; (ii) for all \(i<k\), the q-configuration \(\phi_{i}=U_{M}^{i}|C\rangle\) does not contain any final configuration. When this is the case, we also say that the QTM halts in \(k\) steps in \(\phi_{k}\);
4. if a QTM halts, then the tape head is on the start cell of the initial configuration; and,
5. there is no counter and for every symbol \(a\) there is loop from the only final state \(q_{f}\) into the only initial state \(q_{0}\), which is, \(\delta(q_{f},a)(q_{0},a,R)=1\) for every \(a\in\Sigma\). Therefore, because of the local unitary conditions (that must hold in the final state too), these are the only outgoing transitions from \(q_{f}\), and the only incoming ones into \(q_{0}\). Accordingly, \(\delta(q_{f},a)(q^{\prime},a^{\prime},d)=0\) if \((q^{\prime},a^{\prime},d)\
eq(q_{0},a,R)\) and \(\delta(q^{\prime},a^{\prime})(q_{0},a,d)=0\) if \((q^{\prime},a^{\prime},d)\
eq(q_{f},a,R)\).  
For any B&V-QTM \(M\) there is a QTM \(M^{\prime}\) s.t. for each initial configuration \(|C\rangle\), if \(M\) with input \(|C\rangle\) halts in \(k\) steps in a final configuration \(|\phi\rangle=U_{M}^{k}|C\rangle\), then \(U_{M^{\prime}}^{k}|C\rangle=|\phi\rangle\).  
Proof.: The QTM \(M^{\prime}\) has the same states of \(M\), the initial state \(q_{0}\) is its only source state, and the final state \(q_{f}\) is its only target state. Therefore, if \(M=\langle\Sigma,\Omega,\delta,q_{0},q_{f}\rangle\), we take \(M^{\prime}=\langle\Sigma,\Omega,\{q_{0}\},\{q_{f}\},\delta_{0},q_{0},q_{f}\rangle\), where \(\delta_{0}\) is the restriction of \(\delta\) to \(((\Omega\setminus\Omega_{t})\times\Sigma)\to\ell^{2}\big{(}(\Omega\setminus \Omega_{s})\times\Sigma\times\mathbb{D}\big{)}\), which is, for each \(q\
eq q_{f}\) and \(a\in\Sigma\), we have \(\delta_{0}(q,a)(p,b,d)=\delta(q,a)(p,b,d)\), for every \((p,b,d)\in(\Omega\setminus\Omega_{s})\times\Sigma\times\mathbb{D}\). Because the local unitary conditions hold for \(\delta\) and, in a B&V-QTM, \(\delta(q,a)(q_{0},b,d)=0\), when \(q\
eq q_{f}\), the unitary local conditions hold for \(\delta_{0}\) too.  
By construction, if \(U_{M}^{i}|C\rangle\) is not final for \(0\leq i<k\), then \(|\phi_{k}\rangle=U_{M}^{k}|C\rangle=U_{M^{\prime}}^{k}|C\rangle\). In particular, this holds when \(|\phi_{k}\rangle\) is the final configuration of the B&V-QTM \(M\).  
We remark that the inverse cannot hold true: A B&V-QTM for a given input cannot exhibit both a non terminated computation and a terminated one (see Section 5.3 for a machine that cannot be simulated by a B&V-QTM).