# Unary Quantum Finite State Automata with Control Language
## 2 Preliminaries
### Language Recognition Capabilities and Descriptional Power
#### 2.4.1 Isolated Cut Point QFAs Recognition Power  
We quickly review the language recognition power of the QFA models described above and compare it with that of classical finite state automata. While for general computation devices (e.g., Turing machines), the quantum and the classical paradigms share the same recognition power [58; 59; 60; 61], for constant memory bounded devices, this is not the case. In fact, several results in the literature show that _pure_ quantum models of finite state automata, as those so far considered, are strictly less powerful than classical models. Let us summarize some known results witnessing such a quantum recognition weakness.  
As recalled, DFAs (and isolated cut point probabilistic finite state automata as well [26; 27]) recognize all and only regular languages. It is well known (see, e.g., [29; 31; 57]) that the class of languages recognized by isolated cut point mo-qFAs coincides with the class of group languages [62], which is a proper subclass of regular languages.  
Isolated cut point LQFAs are proved in [33; 34] to be strictly more powerful than isolated cut point mo-qFAs since their recognition power coincides with the class of block group languages. An equivalent characterization states that a language is recognized by an isolated cut point LQFA if and only if it belongs to the boolean closure of languages of the form \(L_{1}a_{1}L_{2}a_{2}\cdots a_{k}L_{k+1}\) for group languages \(L_{i}\subseteq\Sigma^{*}\), \(a_{i}\in\Sigma\) and \(|\Sigma|>1\). So even isolated cut point LQFAs turn out to be strictly less powerful than classical finite state automata: for instance, both the regular languages \(a\Sigma^{*}\) and \(\Sigma^{*}a\), with \(a\in\Sigma\) and \(|\Sigma|>1\), cannot be recognized by isolated cut point LQFAs [33; 34].  
The recognition power of isolated cut point mm-qFAs still remains an open question. However, it is known that isolated cut point mm-qFAs are strictly more powerful than isolated cut point LQFAs but strictly less powerful than dfas. In particular, isolated cut point mm-qFAs can recognize the regular language \(a\Sigma^{*}\), but still they cannot recognize the language \(\Sigma^{*}a\)[30; 33; 34]. It is worth remarking that when restricted to unary inputs, the recognition power of isolated cut point mm-qFAs reverts to that of dfas: any unary regular language can be accepted by an isolated cut point mm-qFAs [33; 34; 38]. This latter result clearly does not hold for isolated cut point mo-qFAs.  
Even for isolated cut point qRas, the recognition power has not been characterized yet, although, being a particular case of lofas, they are strictly less powerful than dfas. From [24], we have that isolated cut point qRas recognize the class of group languages. However, they are not able to accept the regular languages \(a\Sigma^{*}\) and \(\Sigma^{*}a\).  
For the reader's ease of mind, the Venn diagram displayed in Figure 5 shows at a glance the recognition power of the models of isolated cut point QFAs so far considered.  
Figure 5: The language hierarchy for the automaton models considered in this paper. In the picture, we let \(\mathscr{L}(X)\) denote the class of languages recognized by isolated cut point automata of type \(X\in\{\)mo-qFA, qRA, lQFA, mm-qFA, dfA, qFC\(\}\); QFAs with control language (qFCs) will be explained later in Section 2.5 and are here reported for the sake of completeness. Solid line language classes imply proper containments, while the dashed line language class indicates a containment still not known to be proper. The languages displayed near dots \(\bullet\) witness proper containments.