## 3 Quantum Computable Functions
### PPD Sequence of a Computation  
The computed output of a QTM will be defined (Definition 14) as the limit of the sequence of PPDs obtained along its computations. **Definition 12** (probability and q-configurations): _Given a configuration \(C=\langle\alpha,q,\beta,i,n\rangle\), let \(\mathbf{val}[C]\) be the number of \(1\)s in \(\alpha\beta\). For any \(|\phi\rangle\in\ell^{2}(\mathfrak{C})\), let us define \(\mathbf{P}_{|\phi\rangle}:\mathbb{N}\to\mathbb{R}_{\geq 0}\) s.t._  
\[\mathbf{P}_{|\phi\rangle}(n)=\sum_{C\in\ell^{2n},\mathbf{val}[C]=n}|e_{C}|^{2}\]_when \(|\phi\rangle=\sum_{C\in\mathfrak{C}}e_{C}|C\rangle\)._  
**Proposition 2**. : _If \(|\phi\rangle\) is a \(q\)-configuration, \(\mathbf{P}_{|\phi\rangle}\) is a PPD. Moreover, it is a PD if and only if \(|\phi\rangle\) is final._  
Proof. : Let \(|\phi\rangle=|\phi_{0}\rangle+|\phi_{f}\rangle\) with \(|\phi_{0}\rangle\in\ell^{2}(\mathfrak{C}_{M}\setminus\mathfrak{C}_{M}^{fin})\), and \(|\phi_{f}\rangle\in\ell^{2}(\mathfrak{C}_{M}^{fin})\). By the definition of \(\mathbf{P}_{|\phi\rangle}\), it is readily seen that \(\mathbf{P}_{|\phi\rangle}=\mathbf{P}_{|\phi_{f}\rangle}\) and that \(\sum_{n\in\mathbb{N}}\mathbf{P}_{|\phi\rangle}(n)=\sum_{n\in\mathbb{N}}\mathbf{ P}_{|\phi_{f}\rangle}(n)=\||\phi_{f}\rangle\|\leq 1\). Therefore, \(\mathbf{P}_{|\phi\rangle}\) is a PPD. Moreover, since \(\||\phi_{f}\rangle\|=1\) if and only if \(\||\phi_{0}\rangle\|=0\). We see that \(\mathbf{P}_{|\phi\rangle}\) is a PD if and only if \(|\phi_{0}\rangle=0\), that is, if and only if \(|\phi\rangle=|\phi_{f}\rangle\). **Definition 13**. : _For any \(q\)-configuration \(|\phi\rangle\), we shall say that \(\mathbf{P}_{|\phi\rangle}\) is the PPD associated to \(|\phi\rangle\), and we shall denote by \(\mathbf{P}_{K_{|\phi\rangle}^{M}}\) the sequence of PPDs \(\{\mathbf{P}_{|\phi_{i}\rangle}\}_{i\in\mathbb{N}}\) associated to the computation \(K_{|\phi\rangle}^{M}=\{|\phi_{i}\rangle\}_{i\in\mathbb{N}}\)._  
The PPD sequence of any QTM computation is monotone. In the simple proof of this key property (Theorem 3) we see at work all of the constraints on the time evolution of a QTM \(M\). 1. That when in a final (target) configuration, the machine can only increment the counter; as a consequence, the **val** of final (target) configurations does not change. 2. That when entering for the first time into a final (target) state, the value of the counter is initialised to 0. 3. That when in a final (target) configuration \(|\phi,n\rangle\), the counter gives the number of steps \(n\) since \(M\) is looping into the plain configuration \(\phi\). We stress that the last two properties defuse quantum interference between final configurations reached in a different number of steps. **Theorem 3** (monotonicity of computations). : _For any computation \(K_{|\phi\rangle}^{M}\) of a QTM \(M\), the sequence of PPDs \(\mathbf{P}_{K_{|\phi\rangle}^{M}}\) is monotone._  
Proof. : Let us prove that \(\mathbf{P}_{|\phi\rangle}\leq\mathbf{P}_{U|\phi\rangle}\), for every \(|\phi\rangle\in\ell^{2}(\mathfrak{C}_{M})\). Let \(|\phi\rangle=|\phi_{0}\rangle+\sum_{k\in\mathbb{N}}|\phi_{f,k}\rangle\), with \(|\phi_{0}\rangle\in\ell^{2}(\mathfrak{C}_{M}\setminus\mathfrak{C}_{M}^{fin})\), and \(|\phi_{f,k}\rangle\in\ell^{2}(\mathfrak{C}_{M}^{fin}\cap\mathfrak{C}_{M}^{k})\), where \(\mathfrak{C}_{M}^{k}\) is the set of the configurations of \(M\) whose counter is equal to \(k\in\mathbb{N}\). For every \(n\in\mathbb{N}\), we see that \(\mathbf{P}_{|\phi\rangle}(n)=\sum_{k\in\mathbb{N}}\mathbf{P}_{|\phi_{f,k} \rangle}(n)\). Let \(|\psi\rangle=|\psi_{0}\rangle+\sum_{k\in\mathbb{N}}|\psi_{f,k}\rangle=U|\phi\rangle\). By the definition of \(U\), we see that \(U|\phi_{0}\rangle=|\psi_{0}\rangle+|\psi_{f,0}\rangle\) and \(U|\phi_{f,k}\rangle=|\psi_{f,k+1}\rangle\).