# Unary Quantum Finite State Automata with Control Language
## 5 QFCs for Unary Regular Languages
### The First Construction
\);
* \(\mathcal{O}=g\cdot P(g)+a\cdot P(a)+r\cdot P(r)\) is the \(2\cdot P\times 2\cdot P\) observable for which the projectors are defined as \(P(g)=I^{(P)}\oplus\mathbf{0}\), \(P(a)=\mathbf{0}\oplus\mathrm{diag}(\chi_{L_{P^{\circlearrowright}}})\), and \(P(r)=\mathbf{0}\oplus(I^{(P)}-P(a))\), where the vector \(\chi_{L_{P^{\circlearrowright}}}\in\{0,1\}^{P}\) satisfies \((\chi_{L_{P^{\circlearrowright}}})_{i}=1\) if and only if \(\sigma^{i-1}\in\ L_{P^{\circlearrowright}}\) for every \(1\leq i\leq P\) (we notice that \(\chi_{L_{P^{\circlearrowright}}}\) is sometimes referred to as the characteristic vector of the \(P\)-periodic language \(L_{P^{\circlearrowright}}\));
* \(\mathcal{L}=\{y\in g^{*}\{a,r\}\mid\sigma^{iy\mid s}\in L_{\mathrm{T}}\text{ or }y\in g^{\geq T}a\}\subseteq\{a,r,g\}^{*}\) is the control language recognized by the dfa \(D\) in Figure 6.  
Each superposition of the qfc \(A\) can be regarded as being divided into two halves. Along its computation and _before_ reaching the endmarker, \(A\) implements in the left half the dynamic of the quantum component taking care of \(L_{P^{\circlearrowright}}\) by repeatedly applying \(U(\sigma)\). In this phase, any measuring of \(\mathcal{O}\) yields the outcome \(g\) with certainty. Upon reading the endmarker, the left half of the superposition is swapped with the right half by applying \(U(\sharp)\). At this point, the final measuring of \(\mathcal{O}\) takes place, yielding \(a\) or \(r\) according to membership or not, respectively, in \(L_{P^{\circlearrowright}}\). Figure 7 quickly exemplifies the dynamic of \(A\). Let \(g^{k}y_{\sharp}\), with \(y_{\sharp}\in\{a,r\}\), be the sequence of outcomes from measuring \(\mathcal{O}\) along the computation of \(A\) on the input string \(\sigma^{k_{\sharp}}\). * Suppose that \(k<T\): It is not hard to see from the definition of the control language \(\mathcal{L}=\{y\in g^{*}\{a,r\}\mid\sigma^{iy\mid s}\in L_{\mathrm{T}}\text{ or }y\in g^{\geq T}a\}\) that \(A\) exhibits with certainty an accepting computation on \(\sigma^{k_{\sharp}}\sharp\) if and only if \(\sigma^{\mid k^{\sharp}y_{\sharp}\mid s}\in L_{\mathrm{T}}\Leftrightarrow \sigma^{k}\in L_{\mathrm{T}}\). Also, it is easy to verify that an accepting computation occurs with probability \(0\) whenever \(\sigma^{k}\
ot\in L_{\mathrm{T}}\). * Suppose that \(k\geq T\): Again, from the definition of \(\mathcal{L}\), it is not hard to see that \(A\) exhibits with certainty an accepting computation on \(\sigma^{k}\sharp\) if and only if \(g^{k}y_{\sharp}=g^{k}a\), and this happens if and only if \(\sigma^{k}\in L_{P^{\circlearrowright}}\cap\sigma^{\geq T}=L_{P}\). On the other hand, no accepting computation can occur whenever \(\sigma^{k}\
ot\in L_{P}\). In conclusion, the resulting qfc \(A\) deterministically recognizes the unary regular language \(L\) (i.e., \(A\) accepts with certainty (respectively, with probability \(0\)) the strings in (respectively, not in) \(L\)). Concerning the _size_ of \(A\), we have \(2\cdot P\) quantum basis states and \(T+3\) classical states, which is slightly worse than the size (i.e., \(T+P\) states) of the dfa for \(L\). However, in the next section, we are going to improve the size of \(A\) by hardwiring a smaller quantum component.