# Unary Quantum Finite State Automata with Control Language
## 1 Introduction
### Main Contributions  
In this paper, we start from this simulation ability. We construct size efficient qFCs that simulate measure-once, measure-many, reversible, and Latvian qFAs having \(q\) basis states. In particular, the simulating qFCs feature at most \(2q\) quantum basis states for the first three models and \(2q^{2}\) basis state for the last model. In addition, the control languages turn out to be very simple and require at most 3 states for the first three models, and \(q\) states for the last model to be recognized by the classical control unit (dfa component).  
Next, we study the decidability of the problem Periodicity: given a qFC \(A\) working on a unary (i.e., with a single-letter) alphabet \(\{\sigma\}\) and an integer \(d\geq 0\), decide whether or not the stochastic event \(\mathscr{E}_{A}:\sigma^{*}\to[0,1]\) is \(d\)-periodic (i.e., whether \(\mathscr{E}_{A}(\sigma^{k})=\mathscr{E}_{A}(\sigma^{k+d})\) holds true for any \(k\geq 0\)). By using a suitable linear representation of qFCs and generating function arguments, we prove the decidability of Periodicity. This, together with the constructive QFA simulation results quoted above, shows that Periodicity is decidable on measure-once, measure-many, reversible, and Latvian qFAs as well.  
It is important to remark that the ability of inducing periodic stochastic events by using a very restricted amount of basis states is at the core of the construction of extremely succinct QFAs for language recognition (see, e.g., [28; 35; 36; 37; 38; 39]). Therefore, from this point of view, our algorithm to decide Periodicity may represent a relevant diagnostic tool in the actual project of size efficient qFAs.  
Finally, we show that isolated cut point qFCs are generally more size efficient than equivalent DAs when recognizing _unary regular languages_. It is well known (see, e.g., [46; 47]) that any given unary regular language \(L\subseteq\sigma^{*}\) is recognized by a minimal dfa whose state diagram consists of an initial path of \(T\) states joined to a simple cycle of \(P\) states for suitable integers \(T\geq 0\) and \(P>0\); accepting states are suitably located on both the initial path and the cycle. This clearly enables us to view \(L\) as the disjoint union of the finite language \(L_{T}\) consisting of the strings in \(L\) of length less than \(T\) with the ultimately \(P\)-periodic language \(L_{P}\) of the strings in \(L\) of length greater than or equal to \(T\).  
Following this view, we design a qFC in which, very roughly speaking, the classical component takes care of \(L_{T}\) while its quantum component accounts for membership in \(L_{P}\). In particular, this latter component can fully exploit the ability of qFAs to induce periodic stochastic events with a very restricted amount of quantum basis states. The resulting qFC recognizes \(L\) with an isolated cut point, uses a dfa with \(T+3\) states for its control language, and features a quantum component with only \(O(\sqrt{P})\) states. The global amount of \(T+O(\sqrt{P})\) states is to be compared with the \(T+P\) states required for equivalent DfAs.  
We feel it interesting to point out that our construction scheme for unary qFCs is fully modular and naturally allows a \"plug-and-play\" approach by which more size efficient classical or quantum components can be easily hardwired in order to obtain even more size efficient QFCs for certain language families.