# Unary Quantum Finite State Automata with Control Language
## 4 Testing Periodicity on Quantum Finite State Automata
: By Definition 1 and the linear algebra properties in Section 2.2, we can write  
\[\pi\cdot\left(\prod_{i=1}^{|x|}J(x_{i})\right)\cdot J(\sharp)\cdot \eta=(\varphi\otimes\varphi^{*}\otimes\alpha)\cdot\left(\prod_{i=1}^{|x|}(U(x_ {i})\otimes U^{*}(x_{i})\otimes I^{(k)})\cdot\sum_{c\in C}P(c)\otimes P^{*}(c )\otimes M(c)\right)\] \[\cdot\left((U(\sharp)\otimes U^{*}(\sharp)\otimes I^{(k)}) \cdot\sum_{c\in C}P(c)\otimes P^{*}(c)\otimes M(c)\right)\cdot\left(\sum_{j=1 }^{d}\mathrm{e}_{j}^{T}\otimes\mathrm{e}_{j}^{T}\otimes\beta\right)\] \[=\sum_{j=1}^{q}\sum_{y_{1}\ldots y_{|x|}y_{j}\in C^{*}}\left( \varphi\cdot\left(\prod_{i=1}^{|x|}U(x_{i})\cdot P(y_{i})\right)\cdot U(\sharp )\cdot P(\sharp)\right)_{j}\cdot\left(\varphi^{*}\cdot\left(\prod_{i=1}^{|x|}U ^{*}(x_{i})\cdot P^{*}(y_{i})\right)\cdot U^{*}(\sharp)\cdot P^{*}(\sharp) \right)_{j}\] \[\cdot\left(\alpha\cdot\left(\prod_{i=1}^{|x|}M(y_{i})\right)\cdot M (y_{\sharp})\cdot\beta\right)\] \[=\sum_{y_{1}\ldots y_{|x|}y_{1}\in C^{*}}\left(\alpha\cdot\left( \prod_{i=1}^{|x|}M(y_{i})\right)\cdot M(y_{\sharp})\cdot\beta\right)\cdot\left| \left(\varphi\cdot\left(\prod_{i=1}^{|x|}U(x_{i})\cdot P(y_{i})\right)\cdot U( \sharp)\cdot P(\sharp)\right)_{j}\right|^{2}\] \[=\sum_{y_{1}\ldots y_{|x|}y_{1}\in C^{*}}\left(\alpha\cdot\left( \prod_{i=1}^{|x|}M(y_{i})\right)\cdot M(y_{\sharp})\cdot\beta\right)\cdot \left|\left|\varphi\cdot\left(\prod_{i=1}^{|x|}U(x_{i})\cdot P(y_{i})\right) \cdot U(\sharp)\cdot P(\sharp)\right|^{2}. \tag{14}\]  
As pointed out in Section 2.1, we have that \(\alpha\cdot\left(\prod_{i=1}^{|x|}M(y_{i})\right)\cdot M(y_{\sharp})\cdot \beta=1\) if and only if the string \(y_{1}\ldots y_{|x|}y_{\sharp}\in C^{*}\) is accepted by the dfa\(D\) or, equivalently, if and only if \(y_{1}\ldots y_{|x|}y_{\sharp}\in\mathcal{L}.\) Otherwise, we have \(\alpha\cdot\left(\prod_{i=1}^{|x|}M(y_{i})\right)\cdot M(y_{\sharp})\cdot \beta=0\). By this observation, we can rewrite (14) as  
\[\pi\cdot\left(\prod_{i=1}^{|x|}J(x_{i})\right)\cdot L(\sharp)\cdot\eta\] \[=\sum_{y_{1}\ldots y_{|x|}y_{\sharp}\in C^{*}}\left(\alpha\cdot \left(\prod_{i=1}^{|x|}M(y_{i})\right)\cdot M(y_{\sharp})\cdot\beta\right) \cdot\left\|\varphi\cdot\left(\prod_{i=1}^{|x|}U(x_{i})\cdot P(y_{i})\right) \cdot U(\sharp)\cdot P(\sharp)\right\|^{2}\] \[=\sum_{y_{1}\ldots y_{|x|}y_{\sharp}\in\mathcal{L}}\left\|\varphi \cdot\left(\prod_{i=1}^{|x|}U(x_{i})\cdot P(y_{i})\right)\cdot U(\sharp)\cdot P (\sharp)\right\|^{2}=\mathcal{E}_{A}(x),\]  
where the last equality follows from Equations (8) and (9). Another tool which will turn out to be useful in the analysis of the decidability of Periodicity is the notion of a generating function. Generating functions are a well known formalism in Combinatorics and Discrete Mathematics to represent and manipulate numeric sequences (see, e.g., [69]):  
**Definition 2**. : _Given a function \(p:\mathbb{N}\to\mathbb{C},\) its generating function is defined as the formal power series \(G_{p}(z)=\sum_{k=0}^{\infty}p(k)\cdot z^{k}\) for any \(z\in\mathbb{C}\) satisfying \(|z|<1.\)_  
Moreover, we will use the following property of square matrices (see, e.g., [52]):  
**Lemma 2**. : _Let the matrix \(U\in\mathbb{C}^{n\times n}\) satisfy \(\lim_{k\to\infty}U^{k}=\mathbf{0}\). Then, the matrix \((I^{(n)}-U)^{-1}\) exists, and we have \(\sum_{k=0}^{\infty}U^{k}=(I^{(n)}-U)^{-1}\)._  
Let us now focus on the unary qfc \(A=(\varphi,\ \{U(\sigma),\ U(\sharp)\},\ \mathcal{O}=\sum_{c\in C}c\cdot P(c),\ \mathcal{L})\), with control language \(\mathcal{L}\) recognized by the dfa \(D=(\alpha,\ \{M(c)\}_{c\in C^{*}},\ \beta)\) and with linear representation \(\mathrm{Li}(A)=(\pi,\ \{J(\sigma),J(\sharp)\},\ \eta)\). The following limit property holds for the dynamics of \(\mathrm{Li}(A)\):  
**Lemma 3**. : _For any \(z\in\mathbb{C}\) such that \(|z|<1\), we have \(\lim_{k\to\infty}(J(\sigma)\cdot z)^{k}=\mathbf{0}\)._  
Proof. : Let \(\Gamma=\{\sigma,\sharp\}\).