# Unary Quantum Finite State Automata with Control Language
## 1 Introduction  
Several impressive theoretical results, [PERSON] and [PERSON]'s algorithms [1, 2], above all, address the potential of the quantum over classical computational paradigm and motivate great efforts towards actually building quantum computational devices. From this latter viewpoint, especially in the realms of photonics (see, e.g., [3, 4, 5, 6, 7, 8, 9]) and condensed matter physics (see, e.g., [10, 11, 12, 13, 14, 15]), relevant steps have been made to engineer basic quantum components such as qubits, quantum gates, and quantum communication devices. From a physical realization point of view, _hybrid_ computational architectures featuring \"small\" and dedicated quantum components hardwired into and cooperating with a classical computational environment have proved to be quite promising. In order to precisely assess their computational power and emphasize various advantages of adopting quantum hardware, several theoretical models for hybrid architectures with _finite_ (constant, not depending on the input length) memory have been proposed in the literature. Among others, we recall _quantum finite automata_ (qfas) with open time evolution [16], qfas with quantum and classical states [17, 18, 19, 20], and semi-quantum finite state automata [21, 22, 23]. In this paper, we focus on the hybrid model of qfas _with control language_ (qfcs) introduced in [24, 25]. From an architectural point of view, a qfc \(A\) consists of:  
* A _quantum_ component, represented by a _pure_ qfa \(M\) that can be seen as the quantum counterpart of a classical deterministic finite state automaton (dfa); this component is \"controlled\" by
* A _classical_ component, which is a dfa \(D\). The aim of \(A\) is to process strings on a given input alphabet \(\Sigma\). For each input string in \(\Sigma^{*}\), \(A\) returns an \"accept\" outcome with a certain probability. The language recognized by \(A\) is the set of those strings in \(\Sigma^{*}\) for which the acceptance probability exceeds a fixed threshold. Let us overview the behavior of \(A\) in more detail. At any time during the computation of \(A\) on a given input string \(x\in\Sigma^{*}\), the state of the quantum component \(M\) is represented by a _superposition_ of basis states (formally, a norm \(1\) vector in the Hilbertspace spanned by the basis states of the QfA\(M\)). The computation step of \(A\) consists of the following two phases:  
* _Evolution_: the currently scanned symbol of \(x\) is consumed; such a symbol determines a unitary operator (formally, a unitary matrix mapping norm 1 vectors into norm 1 vectors) to be applied to the current superposition of \(M\), yielding a new superposition upon which
* _Observation_: a fixed observable is measured, yielding an outcome with a certain probability; such an outcome, represented by a symbol, is passed to and processed by the classical component, i.e., the dfa\(D\). The observation makes the superposition of \(M\) collapse to a superposition (which, in general, does not have norm 1) coherent with the observed outcome. The normalization of the collapsed superposition is clearly a norm 1 vector and is the superposition \(A\) starts from in order to process the next input symbol. Thus, the computation of \(A\) on the input string \(x\) produces a sequence \(y\) of observable outcomes with a certain probability. We say that the computation is _accepting_ whenever \(y\) is accepted by \(D\), or equivalently, whenever \(y\) belongs to the language recognized by \(D\), called the _control language_. The probability that \(A\) accepts \(x\) is the probability \(\mathcal{E}_{A}(x)\) for \(A\) to display an accepting computation on \(x\), and we call \(\mathcal{E}_{A}:\Sigma^{*}\to[0,1]\) the stochastic event induced by \(A\). Fixing a cut point \(\lambda\in[0,1]\), the _language recognized by \(A\) with cut point \(\lambda\)_ is defined to be the set of strings \(L_{A,\lambda}=\{x\in\Sigma^{*}\ \mid\ \mathcal{E}_{A}(x)>\lambda\}\).