## 2 Quantum Turing Machines
### Plain Configurations  
The basic elements to describe the configuration of a QTM are the finite sequences of symbols on the tape (as usual, we assume that only a finite portion of the tape contains non-blank symbols), the current internal state of the machine, and the current position of the head reading a symbol in a cell of the tape. We assume that each cell of the tape has a fixed address (an integer number), corresponding to its position on the tape. That is, we assume the tape to be a function \(T:\mathbb{Z}\to\Sigma\), such that, at any moment of the execution, only a finite, contiguous part of the tape is not empty, i.e., at any step of the execution, there are two constants \(h\leq k\) s.t., \(T(i)=\Box\) for \(i<h\) and \(i\geq k\) (thus, when \(h=k\) the tape is empty).  
A canonical plain configuration of a given QTM \(M\) is a quadruple \(\langle\alpha,\beta,i\rangle\in\Sigma^{*}\times Q\times\Sigma^{*}\times \mathbb{Z}\), s.t.:  
1. \(q\in Q\) is the current state, where \(Q\) is the finite set of the internal states of \(M\).
2. \(\beta\in\Sigma^{*}\) is the right content of the tape (w.r.t. the head position), where \(\Sigma\) is the tape alphabet of the machine \(M\). If \(\beta=u\beta^{\prime}\
eq\lambda\), the symbol \(u\in\Sigma\) is the current symbol, which is the content of the current cell, while \(\beta^{\prime}\in\Sigma^{*}\) is the longest string on the tape ending with a symbol different from \(\Box\) and whose first symbol (if any) is written in the cell immediately to the right of the current cell. When \(\beta=\lambda\) instead, the right content of the tape, including the current cell, is empty, and the current symbol is \(\Box\).  
\(\alpha\) is the left content of the tape (w.r.t. the head position). That is, it is either the empty string \(\lambda\), or it is the longest string on the tape starting with a symbol different from \(\Box\), and whose last symbol is written in the cell immediately to the left of the current cell.
4. \(i\) is the address of the current cell.  
Given \(\alpha\), \(\beta\in\Sigma^{*}\), let \(\alpha=a_{0}a_{1}\ldots a_{u-1}\) and \(\beta=b_{0}b_{1}\ldots b_{v-1}\), with \(u,v\geq 0\). The plain configuration \(\langle\alpha,q,\beta,i\rangle\) corresponds to the tape  
\[T(j)=\begin{cases}a_{j-i+u}&\text{for $i-u\leq j<i$}\\ b_{j-i}&\text{for $i\leq j<i+v$}\\ \Box&\text{otherwise}\end{cases}\]  
where \(T(j)\
eq\Box\), implies that \(i-u\leq j<i+v\).  
In a canonical plain configuration \(\langle\alpha,q,\beta,i\rangle\) the string \(\alpha\) does not start with a \(\Box\), and \(\beta\) does not end with a \(\Box\). This ensures that each tape corresponds to a unique canonical plain configuration, and vice versa. However, because it will be useful to manipulate configurations that are extended with blank cells to the right (of the right content) or to the left (of the left content), we shall also consider plain configurations \(\langle\alpha,q,\beta,i\rangle\) in which there is no restriction on \(\alpha\) and \(\beta\) and we equate them up to the three equivalence relations that are induced by the following equations  
\[\alpha\simeq_{l}\Box\alpha \beta\simeq_{r}\beta\Box\] \[\langle\alpha,q,\beta,i\rangle\simeq\langle\alpha^{r},q,\beta^{ \prime},i\rangle \text{when $\alpha\simeq_{l}\alpha^{\prime}$ and $\beta\simeq_{r}\beta^{\prime}$}\]  
It is readily seen that any plain configuration is equivalent to a unique canonical plain configuration, and that two configurations are equivalent if and only if they are in the same state, the address of the head is the same, and they correspond to the same tape.