# Unary Quantum Finite State Automata with Control Language
## 3 Qfa Models Simulations by Qfcs
We define the simulating qfc\(B=(\varphi,\ \{U(\sigma)\}_{\sigma\in\Gamma},\ \mathcal{O},\ \mathcal{L})\) with \(q\) basis states, where the control language \(\mathcal{L}\subseteq Q^{*}\) is set to \(\mathcal{L}=Q^{*}F\), and with \(F\subseteq Q\) being the set of accepting basis states (i.e, those states spanning the subspace of \(\mathbb{C}^{q}\) that \(P(a)\)projects onto). Then, by Equations (8) and (9), the probability that \(B\) accepts the input word \(x=x_{1}\cdots x_{n}\in\Sigma^{*}\) is written as  
\[\mathcal{E}_{B}(x) =\sum_{q_{1}\cdots q_{n}q_{1}\in\mathcal{L}}p_{B}(q_{1}\cdots q_{n }q_{\sharp};x_{1}\cdots x_{n}\sharp)\] \[=\sum_{q_{1}\cdots q_{n}q_{1}\in\mathcal{L}}\left\|\varphi\cdot \left(\prod_{i=1}^{n}U(x_{i})\cdot P_{q_{i}}\right)\cdot U(\sharp)\cdot P_{q_{ \sharp}}\right\|^{2}\] \[=\sum_{q_{1}\cdots q_{n}\in\mathcal{Q}^{*}}\left\|\varphi\cdot \left(\prod_{i=1}^{n}U(x_{i})\cdot P_{q_{i}}\right)\cdot U(\sharp)\cdot P(a) \right\|^{2}\] \[=\sum_{q_{1}\in\mathbb{Q}}\cdots\sum_{q_{n}\in\mathbb{Q}}\left\| \varphi\cdot\left(\prod_{j=1}^{n}U(x_{j})\cdot P_{q_{j}}\right)\cdot U(\sharp )\cdot P(a)\right\|^{2}=p_{A}(x),\]  
where the last equality follows from Equation (7). The smallest dfa recognizing the control language \(\mathcal{L}=Q^{*}F\) clearly has two states. **lqfa simulation**: Let \(A=(\varphi,\ \{U(\sigma)\}_{\sigma\in\Gamma},\ \{\mathcal{O}_{\sigma}\}_{ \sigma\in\Gamma})\) be an lqfa with \(q\) basis states. For ease of notation, in the final observable \(\mathcal{O}_{\sharp}\), we rename with \(P_{0}(\sharp)\) (respectively, \(P_{1}(\sharp)\)) the projector \(P(a)\) (respectively, \(P(r)\)) onto the subspace of \(\mathbb{C}^{q}\) spanned by the accepting (respectively, rejecting) basis states. By recalling the form of the observable \(\mathcal{O}_{\sigma}=\sum_{i=0}^{\infty-1}c_{i}(\sigma)\cdot P_{i}(\sigma)\) associated with \(\sigma\in\Gamma\), we set \(\theta=\max\{\sigma_{\sigma}\mid\sigma\in\Gamma\}\); clearly, \(\theta\leq q\) holds true. Then, for each \(\sigma\in\Gamma\), we let the \(\theta\cdot q\times\theta\cdot q\) matrix  
\[H(\sigma)=\left( \begin{array}{ccccc}U(\sigma)\cdot P_{0}(\sigma)&U(\sigma) \cdot P_{1}(\sigma)&\cdots&U(\sigma)\cdot P_{\theta-2}(\sigma)&U(\sigma)\cdot P _{\theta-1}(\sigma)\\ U(\sigma)\cdot P_{1}(\sigma)&U(\sigma)\cdot P_{2}(\sigma)&\cdots&U(\sigma) \cdot P_{\theta-1}(\sigma)&U(\sigma)\cdot P_{0}(\sigma)\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ U(\sigma)\cdot P_{\theta-1}(\sigma)&U(\sigma)\cdot P_{0}(\sigma)&\cdots&U( \sigma)\cdot P_{\theta-3}(\sigma)&U(\sigma)\cdot P_{\theta-2}(\sigma)\end{array}  \right),\]  
where for every \(\sigma_{\sigma}\leq j\leq\theta-1\), we let \(P_{j}(\sigma)=[\mathbf{0}]_{q}\). The reader may easily verify that \(H(\sigma)\) is a unitary matrix. So we define the simulating Qf\(B=(\phi,\ \{Y(\sigma)\}_{\sigma\in\Gamma},\ \Omega,\mathcal{L})\) with \(2\theta\cdot q\) quantum basis states equivalent to the lqfa\(A=(\varphi,\ \{U(\sigma)\}_{\sigma\in\Gamma},\ \{\mathcal{O}_{\sigma}\}_{ \sigma\in\Gamma})\) as:  
* \(\phi=\varphi\oplus\mathfrak{0}_{(2\theta-1)\cdot q}\) is the initial superposition, which can be regarded as a row vector of \(2\theta\) blocks, each of dimension \(q\); we have \(\phi\in\mathbb{C}^{2\theta\cdot q}\) and \(\|\phi\|=\|\varphi\|=1\). * \(Y(\sigma)= \begin{pmatrix}H(\sigma)&[\mathbf{0}]_{\theta\cdot q}\\ [\mathbf{0}]_{\theta\cdot q}&I^{(\theta\cdot q)}\end{pmatrix} \) for any \(\sigma\in\Sigma\), and \(Y(\sharp)= \begin{pmatrix}[\mathbf{0}]_{\theta\cdot q}&H(\sharp)\\ I^{(\theta\cdot q)}&[\mathbf{0}]_{\theta\cdot q}\end{pmatrix} \) are the evolution matrices; we have that \(Y(\sigma),Y(\sharp)\in\mathbb{C}^{2\theta\times 2\theta\cdot q}\) are unitary matrices.