# Unary Quantum Finite State Automata with Control Language
## 2 Preliminaries
### Quantum Finite State Automata with Control Language  
As usual, we let \(\Gamma=\Sigma\cup\{\sharp\}\). A qfa _with control language_ (QFC) [24; 25] on \(\Gamma\) with \(q\) quantum basis states is a 4-tuple \(A=(\varphi,\ \{U(\sigma)\}_{\sigma\in\Gamma},\ \mathcal{O},\ \mathcal{L})\), where:  
* \(\varphi\in\mathbb{C}^{q}\) is the initial superposition and satisfies \(\|\varphi\|=1\). * \(U(\sigma)\in\mathbb{C}^{q\times q}\) is the unitary evolution matrix on \(\sigma\in\Gamma\). * \(\mathcal{O}=\sum_{c\in\mathbb{C}}c\cdot P(c)\) is a \(q\times q\) Hermitian matrix representing an observable, with \(C\) being the set of all possible outcomes (eigenvalues) of measuring \(\mathcal{O}\) and \(P(c)\) the projector onto the eigenspace corresponding to \(c\in C\). * \(\mathcal{L}\subseteq C^{*}\) is a _regular_ language, called the _control language_. We briefly describe the behavior of \(A\) on the input string \(x_{\sharp}^{\sharp}\in\Sigma^{*}\sharp\). The computation starts from the initial superposition \(\varphi\) by scanning the leftmost input symbol. Then, superposition transformations associated with each input symbol 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}^{q}\) of \(A\), with \(\|\xi\|=1\), yielding the next superposition \(\xi^{\prime}=\xi\cdot U(\sigma)\). _Measuring_: the observable \(\mathcal{O}\) is measured on \(g^{\prime}\), and the outcome \(c\) is seen with probability \(\|\xi^{\prime}\cdot P(c)\|^{2}\). Upon getting the outcome \(c\), the superposition \(\sigma^{\prime}\) \"collapses\" to the norm 1 superposition \(\xi^{\prime}\cdot P(c)/\|\xi^{\prime}\cdot P(c)\|\), from which \(A\) continues its computation. So the computation of \(A\) on \(x_{\sharp}^{\sharp}=x_{1}\cdots x_{n}\sharp\) produces the sequence \(y_{1}\cdots y_{n}y_{\sharp}\in C^{*}\) of outcomes of measuring \(\mathcal{O}\) at each step with probability \(p_{A}(y_{1}\cdots y_{n}y_{\sharp};x_{1}\cdots x_{n}\sharp)\) computed as  
\[p_{A}(y_{1}\cdots y_{n}y_{\sharp};x_{1}\cdots x_{n}\sharp)=\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}. \tag{8}\]  
A computation of \(A\) yielding the outcome sequence \(y_{1}\cdots y_{n}y_{\sharp}\in C^{*}\) is said to be _accepting_ (respectively, _rejecting_) if and only if \(y_{1}\cdots y_{n}y_{\sharp}\in\mathcal{L}\) (respectively, \(y_{1}\cdots y_{n}y_{\sharp}\
ot\in\mathcal{L}\)). Therefore, we define the _probability \(\mathcal{E}_{A}(x)\) that \(A\) accepts the word \(x\in\Sigma^{*}\)_ as the probability for \(A\) to exhibit an accepting computation upon processing the input string \(x_{\sharp}^{\sharp}\), namely,  
\[\mathcal{E}_{A}(x)=\sum_{y_{1}\cdots y_{n}y_{\sharp}\in\mathcal{L}}p_{A}(y_{1} \cdots y_{n}y_{\sharp};x_{1}\cdots x_{n}\sharp). \tag{9}\]  
The function \(\mathcal{E}_{A}:\Sigma^{*}\to[0,1]\) is the _stochastic event induced by \(A\)_. Intuitively, a qfc can be regarded as a hybrid system where a quantum component--a qfa--and a classical component--a dfa--cooperate. The quantum component provides the system evolution together with an observable to be measured at each step. The classical component processes the sequence of observable outcomes one outcome at a time by checking whether such a sequence leads to acceptance according to membership in the regular control language \(\mathcal{L}\). From this viewpoint, the language \(\mathcal{L}\) \"controls\" the final acceptance/rejection outcome in the computation of the qfc. Indeed, with \(\mathcal{L}\) being a regular language, the classical component checking membership in \(\mathcal{L}\) is well suited to be a dfa. When expressing the _size_ of a qfc \(A\), we must take into account the size of both its quantum and its classical component.