# Unary Quantum Finite State Automata with Control Language
## 3 Qfa Models Simulations by Qfcs
Upon reading the endmarker, the left half of this superposition is swapped with the right half while evolving on \(\sharp\) as in \(A\). After the evolution on \(\sharp\), the final observation on \(B\) for acceptance takes place exactly in the same context as in \(A\). Let us formally show that \(\mathcal{E}_{B}=p_{A}\). Let \(y_{1}\cdots y_{n}y_{\sharp}\in\{a,r\}^{*}\) be a sequence of outcomes of measuring \(\Omega\) along the computation of \(B\) on an input word \(x_{\sharp}^{*}=x_{1}\cdots x_{n}\sharp\in\Sigma^{*}\sharp\). As pointed out above, we can only have \(y_{i}=a\) for every \(1\leq i\leq n\). In addition, this computation is accepting if and only if \(y_{\sharp}=a\) as well. So by Equation (9) and recalling that the control language is defined as \(\mathcal{L}=a^{*}\), we get that the probability for \(B\) to accept \(x\in\Sigma^{*}\) is  
\[\mathcal{E}_{B}(x)=\sum_{y_{1}\cdots y_{n}y_{\sharp}\in\mathcal{L}}p_{B}(y_{1} \cdots y_{n}y_{\sharp};x_{1}\cdots x_{n}\sharp)=p_{B}(a^{n+1};x\sharp).\]  
Indeed, by Equation (8), the probability \(p_{B}(a^{n+1};x\sharp)\) of observing the outcome sequence \(a^{n+1}\) along the computation of \(B\) on the input word \(x\sharp\) is  
\[\mathcal{E}_{B}(x)=p_{B}(a^{n+1};x\sharp) =\left\|\phi\cdot\left(\prod_{i=1}^{n}Y(x_{i})\cdot\Lambda(a) \right)\cdot Y(\sharp)\cdot\Lambda(a)\right\|^{2}\] \[=\left\|\left(\varphi\oplus\mathbf{0}_{q}\right)\cdot\left(\prod_ {i=1}^{n} \begin{pmatrix}U(x_{i})&[\mathbf{0}]_{q}\\ [\mathbf{0}]_{q}&P(a)\end{pmatrix} \right)\cdot \begin{pmatrix}[\mathbf{0}]_{q}&U (\sharp)\\ U(\sharp)&[\mathbf{0}]_{q}\end{pmatrix} \cdot\Lambda(a)\right\|^{2}\] \[=\left\|\left(\mathbf{0}_{q}\oplus\left(\varphi\cdot\left(\prod_ {i=1}^{n}U(x_{i})\right)\cdot U(\sharp)\right)\right)\cdot\Lambda(a)\right\|^ {2}\] \[=\left\|\varphi\cdot\left(\prod_{i=1}^{n}U(x_{i})\right)\cdot U( \sharp)\cdot P(a)\right\|^{2}=p_{A}(x),\]  
where the last equality follows from Equation (4). The smallest dfa recognizing the control language \(\mathcal{L}=a^{*}\subseteq\{a,r\}^{*}\) clearly has two states. **mm-qfa simulation**: Let \(A=(\varphi,\ \{U(\sigma)\}_{\sigma\in\Gamma},\ \mathcal{O})\) be an mm-qfa with \(q\) basis states and observable \(\mathcal{O}=a\cdot P(a)+r\cdot P(r)+g\cdot P(g)\). We define the simulating qfc\(B=(\varphi,\ \{U(\sigma)\}_{\sigma\in\Gamma},\ \mathcal{O},\ \mathcal{L})\) with \(q\) basis states and where the control language \(\mathcal{L}\subseteq\{a,r,g\}^{*}\) is set to \(\mathcal{L}=g^{*}a\{a,r,g\}^{*}\). According to Equations (8) and (9), the stochastic event induced by \(B\) on \(x\in\Sigma^{*}\) is obtained as follows (we let \(x_{n+1}=\sharp\) and \(y_{n+1}=a\) and let \(I^{(q)}\) be the result of the matrix products below whenever the lower limit exceeds the upper limit):  
\[\mathcal{E}_{B}(x) =\sum_{y_{1}\cdots y_{n}y_{\sharp}\in\mathcal{L}}\left\|\varphi \cdot\left(\prod_{i=1}^{n}U(x_{i})\cdot P(y_{i})\right)\cdot U(\sharp)\cdot P (y_{\sharp})\right\|^{2}\] \[=\sum_{k=1}^{n+1}\sum_{y_{k+1}\cdots y_{n}y_{\sharp}\in\mathbb{C} ^{n-k+1}}\left\|\varphi\cdot\left(\prod_{i=1}^{k-1}U(x_{i})\cdot P(g)\right) \cdot U(x_{k})\cdot P(a)\cdot\left(\prod_{i=k+1}^{n+1}U(x_{j})\cdot P(y_{j} )\right)\right\|^{2}\] \[=\sum_{k=1}^{n+1}\left\|\varphi\cdot\left(\prod_{i=1}^{k-1}U(x_{i })\cdot P(g)\right)\cdot U(x_{k})\cdot P(a)\right\|^{2}=p_{A}(x),\]  
where the last two equalities follow, respectively, from Lemma 1 and Equation (5). The smallest dfa recognizing the control language \(\mathcal{L}=g^{*}a\{a,r,g\}^{*}\) clearly has three states. **qra simulation**: Let \(A=(\varphi,\ \{U(\sigma)\}_{\sigma\in\Gamma},\ \{\mathcal{O},\mathcal{E}_{\sharp}\})\) be a qra with \(Q\) being the set of basis states satisfying \(|Q|=q\), \(\mathcal{O}=\sum_{q\in Q}q\cdot P_{q}\) being the canonical observable to be used all along processing symbols in \(\Sigma\), and with \(\mathcal{O}_{\sharp}=a\cdot P(a)+r\cdot P(r)\) being the usual final accept/reject observable.