# Unary Quantum Finite State Automata with Control Language
## 2 Preliminaries
### Models of Quantum Finite State Automata and Quantum Automata with Control Language  
Let us review some of the main models of quantum finite state automata (QFAs) introduced in the literature and which will be considered in our investigations. We refer the reader to, e.g., [53], for a general introduction to QFAs. **Measure-once qFAs:** We start from the original, simplest, and most investigated model of a QFA, namely, the _measure-once_ qFA model (mo-qfa) [29; 31]. Let the alphabet \(\Gamma=\Sigma\cup\{\sharp\}\), with \(\Sigma\) being an input alphabet and \(\sharp\
ot\in\Sigma\) being an endmarker symbol. A mo-qfa on \(\Gamma\) with \(m\) basis states is a triple \(A=(\varphi,\ \{U(\sigma)\}_{\sigma\in\Gamma},\ \eta)\) where:  
* \(\varphi\in\mathbb{C}^{m}\), with \(\|\varphi\|=1\), is the initial _superposition_ of the basis states; the component \(\varphi_{i}\), with \(|\varphi_{i}|\leq 1\), is the _amplitude_ of the \(i\)th basis state, while \(|\varphi_{i}|^{2}\) is the _probability_ of observing \(A\) being in the \(i\)th basis state. * \(U(\sigma)\in\mathbb{C}^{m\times m}\) is the unitary evolution matrix on \(\sigma\in\Gamma\); \(U(\sigma)_{ij}\), with \(|U(\sigma)_{ij}|\leq 1\), is the amplitude of transitioning from the \(i\)th to \(j\)th basis state upon reading \(\sigma\), while \(|U(\sigma)_{ij}|^{2}\) is the related probability. * \(\eta\in\{0,1\}^{m}\) is the characteristic vector of the accepting states, i.e., \(\eta_{i}=1\) if and only if the \(i\)th basis state is accepting. At any given time along its computation, the state of \(A\) is described by a superposition \(\xi\in\mathbb{C}^{m}\), with \(\|\xi\|=1\), carrying the following probabilistic meaning: by observing \(A\) in \(\xi\), we find \(A\) to be in its \(i\)th basis state with probability \(|\xi_{i}|^{2}\). So the computation of \(A\) on an input word \(w_{\sharp}^{*}\in\Sigma^{*}\sharp\) starts from the initial superposition \(\varphi\) by scanning the leftmost input symbol. Then, the evolutions related to input symbols are applied in succession starting from \(U(w_{1})\), which acts on \(\varphi\). Figure 2 depicts the first steps of this dynamic. After the first \(k\) input symbols have been processed, \(A\) reaches the superposition \(\varphi\cdot(\prod_{i=1}^{k}U(w_{i}))\in\mathbb{C}^{m}\), which is again a norm 1 vector since \(\|\varphi\|=1\) and the matrices \(U(w_{i})\)s are unitary. After processing the whole input word, \(A\) enters the final superposition \(\varphi\cdot(\prod_{i=1}^{|w|}U(w_{i}))\cdot U(\sharp)\). At this point, we evaluate the probability of observing \(A\) in an _accepting_ basis state, yielding the probability \(p_{A}(w)\) that \(A\) accepts the string \(w\in\Sigma^{*}\). Such a probability is easily seen to be obtained as  
\[p_{A}(w)=\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{2}\]  
Equivalently, we can define \(p_{A}(w)\) by introducing the _observable_ described by the Hermitian matrix \(\mathcal{O}=a\cdot P(a)+r\cdot P(r)\), with \(P(a)=\text{diag}(\eta)\) and \(P(r)=I^{(m)}-P(a)\) being the projectors onto the two orthogonal subspaces of \(\mathbb{C}^{m}\) spanned, respectively, by the accepting and rejecting (i.e., nonaccepting) basis states. By measuring this observable\(\mathcal{O}\), we get two possible outcomes:  
* \(a\), which stands for \"accepting\": getting this outcome means seeing \(A\) in an _accepting_ basis state;
* \(r\), which stands for \"rejecting\": getting this outcome means seeing \(A\) in a _nonaccepting_ basis state. Each of these two outcomes shows up with a certain probability, which is computed as follows. Suppose at a given time \(A\) is in the norm 1 superposition \(\xi\in\mathbb{C}^{m}\), and we measure the observable\(\mathcal{O}\).