# Unary Quantum Finite State Automata with Control Language
## 5 QFCs for Unary Regular Languages
### The First Construction  
We provide a first implementation out of the construction scheme outlined in Section 5.1, featuring a first type of _quantum component_ for our isolated cut point QFC \(A\) recognizing the unary language \(L=L_{T}\cup L_{P}\). Such a component takes care of the ultimately periodic language \(L_{P}\) by recognizing with an isolated cut point the \(P\)-periodic language  
\[L_{P^{\odot}}=\{\sigma^{(T+i)\bmod P}\mid 0\leq i<P,\;h\geq 0,\text{ and }\sigma^{T+i}\in L_{P}\}.\]  
It is not hard to see that \(L_{P^{\odot}}\) coincides with \(L_{P}\) when restricted to strings with lengths exceeding \(T-1\): namely, \(L_{P}=L_{P^{\odot}}\cap\sigma^{\geq T}\). This quantum component is equipped with an observable to be measured at every step and with three possible outcomes: \(g\) (go), \(a\) (accept), and \(r\) (reject). Upon processing the input symbol \(\sigma\), the observable outcome will always be \(g\), while on \(\sharp\), the outcome will be either \(a\) or \(r\) depending, respectively, on whether or not the input string belongs to \(L_{P^{\odot}}\). Given that \(L_{P}=L_{P^{\odot}}\cap\sigma^{\geq T}\), the control language \(\mathcal{L}\) of \(A\) is designed so that acceptance by this quantum component takes place only on the strings with lengths exceeding \(T-1\); on the other hand, for strings with lengths less than or equal to \(T-1\), the acceptance is completely up to the classical component. Precisely, \(\mathcal{L}\subseteq\{a,r,g\}^{*}\) is designed so that:  
* Only for input strings with lengths greater than or equal to \(T\), the outcomes \(a\) and \(r\) are considered for accepting/rejecting; correspondingly, the outcome \(g\) is ignored after \(T\) steps. * Instead, for input strings with lengths less than \(T\), the outcomes \(a\) and \(r\) are ignored, and the classical component counts the number of \(g\) to establish membership in \(L_{T}\). Summing up, the classical component of the QFC \(A\) is the Dfa \(D\), whose state diagram is depicted in Figure 6, which recognizes the control language language \(\mathcal{L}\subseteq\{a,r,g\}^{*}\) defined to be the set \(\mathcal{L}=\{y\in g^{*}\{a,r\}\mid\sigma^{|y|_{g}}\in L_{T}\text{ or }y\in g^{\geq T}a\}\). Let us quickly discuss the architecture and behavior of the Dfa \(D\) in Figure 6. In the initial path \(\{q_{0},\dots,q_{T-1}\}\), the accepting states are set according to \(L_{T}\). Namely, for every \(0\leq i<T\), we designate the state \(q_{i}\) as accepting if and only if \(\sigma^{i}\in L_{T}\). This ensures the correct acceptance of input strings (with lengths not exceeding \(T-1\) and) belonging to \(L_{T}\). If the state \(q_{T}\) is reached, then an input string with a length of at least \(T\) is under processing, and so membership in \(L_{P}\) has to be checked. To this aim, once reaching \(q_{T}\), the Dfa \(D\) stays in \(q_{T}\) as long as the input symbol \(\sigma\) is read (i.e., as long as the outcome \(g\) is processed by \(D\)). Upon reaching the endmarker \(\sharp\), the Dfa \(D\) simply acknowledges the outcome \(a\) or \(r\) of the quantum component to witness, respectively, membership or not in \(L_{P}\). Formally, we define the isolated cut point QFC \(A=(\varphi,\;\{U(\sigma),\;U(\sharp)\},\;\mathcal{O},\;\mathcal{L})\) for the unary regular language \(L=L_{T}\cup L_{P}\) as follows:* \(\varphi=\mathrm{e}_{1}\in\mathbb{C}^{2\cdot P}\) is the initial superposition;
* \(U(\sigma)=Z\oplus I^{(P)}\), where \(Z\in\{0,1\}^{P\times P}\) is the matrix representing the cyclic permutation, i.e., \(Z\) has \(1\) at the \((i,i+1)\)th entries for every \(1\leq i<P\) and at the \((P,1)\)th entry, while all the other entries are \(0\);
* \(U(\sharp)= \begin{pmatrix}\mathbf{0}&I^{(P)}\\ I^{(P)}&\mathbf{0}\end{pmatrix}