# Unary Quantum Finite State Automata with Control Language
## 3 Qfa Models Simulations by Qfcs  
One of the main capabilities of Qfcs is to provide a unifying framework within which to represent several Qfa models. Here, we show how to simulate mo-Qfas, mm-Qfas, qras, and lqfas by qfcs, emphasizing the cost in terms of quantum and classical states of such simulations. The simulation of lqfas is devised in [36], while the other simulations are quickly addressed in [24]. For the sake of completeness, we display all these simulations in full detail. To this regard, to study simulation correctness, we will make use of the following technical lemma on the dynamics of Qfcs, the proof of which can be given by induction on the length of the input strings:  
**Lemma 1**. : _Let \(A=(\varphi,\ \{U(\sigma)\}_{\sigma\in\Gamma},\ \mathcal{O}=\sum_{c\in\mathbb{C}}c \cdot P(c),\ \mathcal{L})\) be a qfc with \(q\) quantum basis states. Then for any vector \(\zeta\in\mathbb{C}^{q}\) and any string \(x_{1}\cdots x_{n}\in\Gamma^{*}\), we have_  
\[\sum_{y_{1}\cdots y_{n}\in\mathbb{C}^{n}}\left\|\zeta\cdot\left(\prod_{i=1}^{ n}U(x_{i})\cdot P(y_{i})\right)\right\|^{2}=\|\zeta\|^{2}.\]  
We are now ready to show the main result of this section:  
**Theorem 2**. : _Let \(A\) be a mo-Qfa, mm-Qfa, Qfa, or lqfas with \(q\) basis states (Table 1). Then, there exists a qfc \(B\) satisfying \(\mathcal{E}_{B}=p_{A}\) with the following number of quantum basis states and classical states:_  
Proof. : Throughout the following simulations, for a given \(t\in\mathbb{N}\), we let \(\mathbf{0}_{t}\) denote the \(t\)-dimensional row zero-vector and \([\mathbf{0}]_{t}\) denote the \(t\times t\) zero-matrix. **Mo-Qfa simulation**: Let \(A=(\varphi,\ \{U(\sigma)\}_{\sigma\in\Gamma},\ \mathcal{O})\) be an mo-Qfa with \(q\) basis states and observable \(\mathcal{O}=a\cdot P(a)+r\cdot P(r)\). We define the simulating qfc \(B=(\varphi,\ \{Y(\sigma)\}_{\sigma\in\Gamma},\ \mathcal{O},\ \mathcal{L})\) with \(2\cdot q\) quantum basis states, where:  
* \(\phi=\varphi\oplus\mathbf{0}_{q}\) is the initial superposition; we have \(\phi\in\mathbb{C}^{2\cdot q}\) and \(\|\phi\|=\|\varphi\|=1\). * \(Y(\sigma)=U(\sigma)\oplus I^{(q)}\) for any \(\sigma\in\Sigma\), and \(Y(\tilde{\varepsilon})= \begin{pmatrix}[\mathbf{0}]_{q}&U(\tilde{\varepsilon})\\ U(\tilde{\varepsilon})&[\mathbf{0}]_{q}\end{pmatrix} \) are the evolution matrices; we have that \(Y(\sigma),Y(r)\in\mathbb{C}^{2\cdot q\times 2\cdot q}\) are unitary matrices. * \(\Omega=a\cdot\Lambda(a)+r\cdot\Lambda(r)\), with projectors \(\Lambda(a)=I^{(q)}\oplus P(a)\) and \(\Lambda(r)=[\mathbf{0}]_{q}\oplus P(r)\), is a \(2\cdot q\times 2\cdot q\) Hermitian matrix representing an observable with the two outcomes \(a\) (accept) and \(r\) (reject). * \(\mathcal{L}=a^{*}\subseteq\{a,r\}^{*}\) is the regular control language. To have an idea of the behavior of \(B\), we can think of each possible superposition of \(B\) as being divided into two halves. Along its computation, _before_ processing the input endmarker, \(B\) replicates the dynamic of the simulated mo-Qfa \(A\) into the left half and leaves the right half untouched. As the reader may easily verify, during this phase any observation by \(\Omega\) yields the outcome \(a\) with certainty. Thus, by setting the control language to \(\mathcal{L}=a^{*}\), we are basically letting \(B\) reach with certainty a superposition featuring in \begin{table}
\begin{tabular}{c c c} \hline \hline
**Simulated qfa Model \(A\) with \(q\) Basis States** & **Quantum Basis States for** & **Classical States for** \\
**Simulating qfc \(B\)** & **Simulating qfc \(B\)** & **Simulating qfc \(B\)** \\ \hline mo-Qfa & \(2\cdot q\) & \(2\) \\ \hline mm-Qfa & \(q\) & \(3\) \\ \hline qra & \(q\) & \(2\) \\ \hline lqfa & \(2\cdot q^{2}\) & \(q\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The costs in terms of quantum and classical states of simulating models of qfas by qfcs. the left half the superposition assumed by \(A\) when the endmarker is about to be read.