# Unary Quantum Finite State Automata with Control Language
## 2 Preliminaries
### Models of Quantum Finite State Automata and Quantum Automata with Control Language
We remark that, differently from the mo-qfa model, the mm-qfa \(A\) can halt and accept also in the middle of the input string. The probability \(p_{A}(w)\) for \(A\) to accept \(w\in\Sigma^{*}\) accumulates step by step and is finally computed as  
\[p_{A}(w)=\sum_{k=1}^{|w|+1}\left\|\varphi\cdot\left(\prod_{i=1}^{k-1}U(w_{i}) \cdot P(g)\right)\cdot U(w_{k})\cdot P(a)\right\|^{2}, \tag{5}\]  
where, for ease of notation, we let \(w_{|w|+1}=\sharp\) and let \(I^{(m)}\) be the result of the matrix product for \(k=1\). The function \(p_{A}:\Sigma^{*}\to[0,1]\) is the _stochastic event induced by \(A\)_.  
Figure 3: First steps of the computation of the mm-qfa \(A\) on the input string \(w_{1}w_{2}\cdots w_{n}\sharp\): the resulting evolution/observation dynamic. **Latvian QFAs:** We now present the _Latvian_ QFA model (LQFA) [33; 34]. As usual, we let \(\Gamma=\Sigma\cup\{\sharp\}\). An lqfa on \(\Gamma\) with \(m\) basis states is a triple \(A=(\varphi,\{U(\sigma)\}_{\sigma\in\Gamma},\{\mathcal{O}_{\sigma}\}_{\sigma\in \Gamma})\), 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\). * For any \(\sigma\in\Sigma\), we let \(\mathcal{O}_{\sigma}=\sum_{i=0}^{\infty_{\sigma}-1}c_{i}(\sigma)\cdot P_{i}( \sigma)\) be an \(m\times m\) Hermitian matrix representing an observable, where \(\{c_{0}(\sigma),\ldots,c_{\sigma_{\sigma}-1}(\sigma)\}\) is the set of all possible outcomes (eigenvalues) from measuring \(\mathcal{O}_{\sigma}\), and \(\{P_{0}(\sigma),\ldots,P_{\alpha_{\sigma}-1}(\sigma)\}\) are the projectors onto the corresponding eigenspaces. * For the final observable \(\mathcal{O}_{\sharp}\), basis states are assumed to be partitioned into accepting and rejecting. So \(\mathcal{O}_{\sharp}=a\cdot P(a)+r\cdot P(r)\), where \(P(a)\) (respectively, \(P(r)=I^{(m)}-P(a)\)) is the projector onto the subspace of \(\mathbb{C}^{m}\) spanned by the accepting (respectively, rejecting) basis states. The computation of \(A\) on an input word \(w_{\sharp}^{\sharp}\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\), yielding the next superposition \(\xi^{\prime}=\xi\cdot U(\sigma)\). 2. _Observation:_ The observable \(\mathcal{O}_{\sigma}\) is measured on \(\xi^{\prime}\), and the outcome is \(c_{i}(\sigma)\) with probability \(\|\xi^{\prime}\cdot P_{i}(\sigma)\|^{2}\). Upon getting the outcome \(c_{i}(\sigma)\), the superposition \(\xi^{\prime}\) \"collapses\" to the norm 1 superposition \(\xi^{\prime}\cdot P_{i}(\sigma)/\|\xi^{\prime}\cdot P_{i}(\sigma)\|\) from which \(A\) continues its computation, unless we are processing the endmarker \(\sharp\). Figure 4 exemplifies such an evolution/observation dynamic starting from \(U(w_{1})\), which acts on \(\varphi\). Upon processing the endmarker \(\sharp\), the final observable \(\mathcal{O}_{\sharp}\) is measured, yielding the probability of seeing \(A\) in an accepting basis state (i.e., of getting the outcome \(a\)). The probability for \(A\) to accept \(w\in\Sigma^{*}\) is given by  
\[p_{A}(w)=\sum_{i_{1}=0}^{\infty_{w_{1}}-1}\cdots\sum_{i_{|w|}=0}^{\infty_{w_{ 1}|w|-1}}\left\|\varphi\cdot\left(\prod_{j=1}^{|w|}U(w_{j})\cdot P_{j_{j}}(w_{ j})\right)\cdot U(\sharp)\cdot P(a)\right\|^{2}. \tag{6}\]  
We emphasize that, similarly to the mo-qfa model and differently from the mm-qfa model, a lqfa cannot halt accepting or rejecting in the middle of input strings.