# An Enhanced Photonic Quantum Finite Automaton
## 3 Measure-Once One-Way Quantum Finite Automaton  
Here, we briefly overview the main concepts on automata and formal language theory. We refer the interested reader to any of the standard books on these subjects (see, e.g., in [22]), as well as to our contribution [6]. An alphabet is any finite set \(\Sigma\) of elements called symbols. A word on \(\Sigma\) is any sequence \(\sigma_{1}\sigma_{2}\cdots\sigma_{n}\) with \(\sigma_{i}\in\Sigma\). The set of all words on \(\Sigma\) is denoted by \(\Sigma^{*}\). A language \(L\) on \(\Sigma\) is any subset of \(\Sigma^{*}\), i.e., \(L\subseteq\Sigma^{*}\). If \(|\Sigma|=1\), we say that \(\Sigma\) is a _unary_ alphabet, and languages on unary alphabets are called unary languages. In case of unary alphabets, we customarily let \(\Sigma=\{a\}\) so that a unary language is any set \(L\subseteq a^{*}\). We let \(a^{k}\) be the unary word obtained by concatenating \(k\) times the symbol \(a\). In what follows, we will be interested in the unary language \(L_{m}\) defined as  
\[L_{m}=\{a^{k}\mid k\in\mathbb{N}\text{ and }k(\text{mod }m)=0\}. \tag{1}\]  
This language is rather famous in the realm of automata theory, since it has proven particularly \"size-consuming\" to be accepted by several models of classical automata, as the number of needed states increases with \(m\)[6]. The reader may find a deep investigation on this fact in the literature [22; 29; 30; 31]. On the other hand, as presented in [6], very succinct measure-once one-way quantum finite automata (1 qfa's, from now on) may be designed and physically realized for \(L_{m}\). Let us now sketch the main ingredients for a 1 qfa accepting \(L_{m}\). If we consider the two orthogonal states \(|H\rangle=(1,0)\) and \(|V\rangle=(0,1)\), the 1 qfa is defined as (here we use the formalism based on the [PERSON]'s notation; the analysis based on a more general formalism can be found in [6])  
\[\mathcal{A}_{1}=\Big{\{}|H\rangle,U_{m},P^{H}\Big{\}} \tag{2}\]  
where \(|H\rangle\) represents the initial state, the unitary operation applied by the automaton upon processing any input symbol \(a\) is defined as  
\[U_{m} =\exp(-i\theta_{m}\sigma_{y}) \tag{3}\] \[= \begin{pmatrix}\cos\theta_{m}&\sin\theta_{m}\\ -\sin\theta_{m}&\cos\theta_{m}\end{pmatrix} . \tag{4}\]  
with \(\theta_{m}=\pi/m\) and \(\sigma_{y}\) the Pauli matrix, while \(P^{H}=|H\rangle\langle H|\) is the projector onto the mono-dimensional accepting subspace spanned by \(|H\rangle\). The probability \(p_{\mathcal{A}_{1}}(a^{k})\) that the 1 qfa \(\mathcal{A}_{1}\) accepts the word \(a^{k}\) writes as  
\[p_{\mathcal{A}_{1}}(a^{k}) =p^{H}(a^{k})\equiv|\langle H|U_{m}^{k}|H\rangle|^{2} \tag{5}\] \[=\cos^{2}(k\theta_{m})\to \begin{cases}=1&k(\text{mod }m)=0\\ \leq\cos^{2}\theta_{m}&\text{otherwise}.\end{cases}  \tag{6}\]  
Therefore, the 1 qfa \(\mathcal{A}_{1}\) perfectly recognizes the word \(a^{k}\in L_{m}\), as we can set a _cut point_\(\lambda\) and an _isolation_\(\rho\) to the following values (see in [6] for details on accepting languages with isolated cut point)  
\[\lambda=\frac{1+\cos^{2}\theta_{m}}{2}\quad\text{and}\quad\rho=\frac{1-\cos^{ 2}\theta_{m}}{2}\,. \tag{7}\]  
However, \(\mathcal{A}_{1}\) may also recognize an input word not in \(L_{m}\) with a non-null probability. In the following, we let \(a^{k_{1}}\) with \(k_{1}(\text{mod }m)=1\) any of the word with the highest probability of erroneously being accepted, i.e., \(\cos^{2}\theta_{m}\), which tends to 1 as \(m\) gets large. This can be seen also by the fact that \(\rho\to 0\) as \(m\) increases. As matter of fact, we can also introduce the following 1 qft, where we still consider the initial state \(|H\rangle\), but, at the output, we focus on the final projection involving the state \(|V\rangle\), namely  
\[\mathcal{A}_{2}=\Big{\{}|H\rangle,U_{m},\mathbb{I}-P^{V}\Big{\}}, \tag{8}\]  
where \(P^{V}=|V\rangle\langle V|\). Indeed, \(\mathcal{A}_{2}\) is formally equivalent to \(\mathcal{A}_{1}\), as \(\mathbb{I}-P^{V}\equiv P^{H}\).