# Unary Quantum Finite State Automata with Control Language
## 2 Preliminaries
### Models of Quantum Finite State Automata and Quantum Automata with Control Language
Then, we see either the outcome \(a\) or the outcome \(r\), with the probability equal to the square norm of the projection of \(\xi\) onto the subspace spanned by, respectively, the accepting or nonaccepting basis states:  
\[\text{probability of seeing }\;a \mapsto \|\xi\cdot P(a)\|^{2}=\sum_{\{i\;|\;\eta_{i}=1\}}|(\xi\cdot P(a) )_{i}|^{2}, \tag{3}\] \[\text{probability of seeing }\;r \mapsto \|\xi\cdot P(r)\|^{2}=\sum_{\{i\;|\;\eta_{i}=0\}}|(\xi\cdot P(r) )_{i}|^{2}.\]  
Thus, the probability \(p_{A}(w)\) for \(A\) to accept \(w\in\Sigma^{*}\) is given by the probability of obtaining the outcome \(a\) from measuring \(\mathcal{O}\) at the end of the computation of \(A\) on \(w\), i.e., when \(A\) is in the final superposition \(\varphi\cdot(\prod_{i=1}^{|w|}U(w_{i}))\cdot U(\sharp)\). According to (3), this is written as  
\[p_{A}(w)=\left\|\varphi\cdot\left(\prod_{i=1}^{|w|}U(w_{i})\right)\cdot U( \sharp)\cdot P(a)\right\|^{2}=\sum_{\{i\;|\;\eta_{i}=1\}}\left|\left(\varphi \cdot\left(\prod_{i=1}^{|w|}U(w_{i})\right)\cdot U(\sharp)\right)_{i}\right|^ {2}, \tag{4}\]  
in accordance with Equation (2). When adopting the observable \(\mathcal{O}\) instead of the characteristic vector \(\eta\) of the accepting basis states, we will use the notation \(A=(\varphi,\;\{U(\sigma)\}_{\sigma\in\mathbb{I}},\;\mathcal{O})\) for an mo-qfa. The _stochastic event induced by \(A\)_ is the function \(p_{A}:\Sigma^{*}\to[0,1]\). Figure 2: First steps of the computation of the mo-qfa \(A\) on the input string \(w_{1}w_{2}\cdots w_{n}\sharp\): the resulting superposition dynamic. **Measure-many QFAs:** Let us now turn to the _measure-many_ QFA model (MM-QFA) [28,30]. In an mm-qfa \(A\), the \(m\) basis states are partitioned into _halting_ states--which in turn are partitioned into _accepting_ and _rejecting_ states--and _non-halting_ states, the latters being called _go_ states. We let \(\eta(a),\eta(r),\eta(g)\in\{0,1\}^{m}\) be the characteristic vectors of, respectively, accepting, rejecting, and go basis states. Again, we let \(\Gamma=\Sigma\cup\{\sharp\}\). Then, we define the mm-qfa \(A\) on \(\Gamma\) with \(m\) basis states as the triple \(A=(\varphi,\ \{U(\sigma)\}_{\sigma\in\Gamma},\ \mathcal{O})\), where:  
* \(\varphi\in\mathbb{C}^{m}\) is the initial superposition and satisfies \(\|\varphi\|=1\). * \(U(\sigma)\in\mathbb{C}^{m\times m}\) is the unitary evolution matrix on \(\sigma\in\Gamma\). * \(\mathcal{O}=a\cdot P(a)+r\cdot P(r)+g\cdot P(g)\), with projectors \(P(c)=\operatorname{diag}(\eta(c))\) for \(c\in\{a,r,g\}\), is the \(m\times m\) Hermitian matrix representing an observable with three possible outcomes: \(a\) stands for \"accept\", \(r\) for \"reject\", and \(g\) for \"go\". Correspondingly, the projectors \(P(a)\), \(P(r)\), and \(P(g)\) project onto the subspaces of \(\mathbb{C}^{m}\) spanned by, respectively, the accepting, rejecting, and go basis states. The computation of \(A\) on an input word \(w_{\sharp}^{u}\in\Sigma^{*}\sharp\) starts from the initial superposition \(\varphi\) by scanning the leftmost input symbol. Then, superposition transformations associated with input symbols are applied in succession. More precisely, the transformation triggered by a symbol \(\sigma\in\Gamma\) consists of two phases:  
1. _Evolution:_\(U(\sigma)\) acts on the current superposition \(\xi\in\mathbb{C}^{m}\) of \(A\), with \(\|\xi\|=1\), to yield the next superposition \(\xi^{\prime}=\xi\cdot U(\sigma)\). 2. _Observation:_ The observable \(\mathcal{O}\) is measured on \(\xi^{\prime}\), and the outcome is \(c\in\{a,r,g\}\) with probability \(\|\xi^{\prime}\cdot P(c)\|^{2}\). If the outcome is either \(a\) or \(r\), the computation of \(A\) halts and the input word is accepted or rejected, respectively. Otherwise, in case of outcome \(g\), the superposition \(\xi^{\prime}\) \"collapses\" to the norm 1 superposition \(\xi^{\prime}\cdot P(g)/\|\xi^{\prime}\cdot P(g)\|\) from which \(A\) continues its computation. Figure 3 exemplifies such an evolution/observation dynamic starting from \(U(w_{1})\), which acts on \(\varphi\).