# Unary Quantum Finite State Automata with Control Language
## 4 Testing Periodicity on Quantum Finite State Automata  
In general, a _stochastic event_ on an alphabet \(\Sigma\) is a function \(p:\Sigma^{*}\to[0,1]\). In Section 2.3, for instance, we introduced stochastic events induced by QFA models as means of defining languages (by isolated cut points). Let \(p:\sigma^{*}\to[0,1]\) be a stochastic event on a _unary_ alphabet \(\{\sigma\}\). Since the unary string \(\sigma^{k}\) is basically the unary representation of the number \(k\in\mathbb{N}\), for ease of notation, we will be simply writing \(p(k)\) instead of \(p(\sigma^{k})\). Therefore, from this point of view, a unary stochastic event is a function \(p:\mathbb{N}\to[0,1]\). We say that \(p\) is _\(d\)-periodic_ for a given integer \(d>0\) (called the _period_) whenever \(p(k)=p(k+d)\) holds true for any \(k\geq 0\). Here, we study the problem of deciding whether or not a given _unary_ QFA, i.e., a QFA working on a unary alphabet, induces a periodic stochastic event. We formally state such a decision problem for _unary_ QFCs:  
Periodicity  
Input: A unary QFC A and an integer \(d\geq 0\). Question: Is \(\mathcal{E}_{A}\) a \(d\)-periodic stochastic event? We are going to prove that Periodicity_is decidable_, i.e., there exists a deterministic algorithm for its solution. We tackle this problem inspired by [38], where the same question has been posed for the more restricted model of mm-qfas. First of all, we present some formal tools useful in our investigation. From now on, we will be using the following notations introduced in Section 2.2 and here recalled: for a row vector \(\varphi\in\mathbb{C}^{m}\), we let \(\varphi^{*}\in\mathbb{C}^{m}\) be the vector satisfying \(\varphi^{*}{}_{i}=(\varphi_{i})^{*}\) and \(\varphi^{T}\in\mathbb{C}^{m\times 1}\) be the column vector obtained by transposing \(\varphi\); for a matrix \(J\in\mathbb{C}^{m\times m}\), we let \(J^{*}\in\mathbb{C}^{m\times m}\) be the matrix satisfying \(J^{*}{}_{ij}=(J_{ij})^{*}\). **Definition 1**. : _Let \(A=(\varphi,\ \{U(\sigma)\}_{\sigma\in\Gamma},\ \mathcal{O}=\sum_{c\in \mathbb{C}}c\cdot P(c),\ \mathcal{L})\) be a QFC with \(q\) quantum basis states and with \(D=(\alpha,\{M(c)\}_{c\in\mathbb{C}},\beta)\) being the Dfa with \(m\) classical states recognizing the control language \(\mathcal{L}\) (see Section 2.1 for the linear representation of a Dfa). The linear representation of \(A\) is defined as \(\mathrm{Li}(A)=(\pi,\{J(\sigma)\}_{\sigma\in\Gamma},\eta)\), where:_  
* \(\pi=\varphi\otimes\varphi^{*}\otimes\alpha\) _is a row vector in_ \(\mathbb{C}^{q^{2}\cdot m}\)_._
* \(J(\sigma)=(U(\sigma)\otimes U^{*}(\sigma)\otimes I^{(m)})\cdot\sum_{c\in \mathbb{C}}P(c)\otimes P^{*}(c)\otimes M(c)\) _for any_ \(\sigma\in\Gamma\) _is a matrix in_ \(\mathbb{C}^{q^{2}\cdot m\times q^{2}\cdot m}\)_._
* \(\eta=\sum_{i=1}^{q}\mathbf{e}_{i}^{T}\otimes\mathbf{e}_{i}^{T}\otimes\beta\) _is a column vector in_ \(\{0,1\}^{q^{2}\cdot m\times 1}\)_, with_ \(\{\mathbf{e}_{1},\ldots,\mathbf{e}_{q}\}\) _being the canonical basis of_ \(\mathbb{C}^{q}\) _and the column vector_ \(\beta\in\{0,1\}^{m\times 1}\) _being the boolean characteristic vector of the accepting states of the Dfa_ \(D\)_._  
\(\mathrm{Li}(A)\) enables us to give an alternative and more manageable representation of the stochastic event \(\mathcal{E}_{A}\) induced by the QFC\(A\), as shown in the following:  
**Proposition 1**. : _Let \(A=(\varphi,\ \{U(\sigma)\}_{\sigma\in\Gamma},\ \mathcal{O}=\sum_{c\in C}c\cdot P(c),\ \mathcal{L})\) be a QFC for which the classical component is the dfa\(D=(\alpha,\{M(c)\}_{c\in C},\beta)\) that recognizes the control language \(\mathcal{L}.\) Let \(\ \mathrm{Li}(A)=(\pi,\ \{J(\sigma)\}_{\sigma\in\Gamma},\ \eta)\) be the linear representation of \(A.\) Then for any \(x\in\Sigma^{*},\) we have_  
\[\mathcal{E}_{A}(x)=\pi\cdot\left(\prod_{i=1}^{|x|}J(x_{i})\right)\cdot J(\sharp )\cdot\eta.\]  
Proof.