# Unary Quantum Finite State Automata with Control Language
## 2 Preliminaries
### Linear Algebra
The subspace _spanned_ by a set of vectors \(X\subseteq\mathbb{C}^{n}\) is the linear space \(\{\sum_{\varphi\in S}a_{\varphi}\cdot\varphi\mid\alpha_{\varphi}\in\mathbb{C}\}\). Two subspaces \(X,Y\subseteq\mathbb{C}^{n}\) are orthogonal if any vector in \(X\) is orthogonal to any vector in \(Y\). In this case, we denote by \(X+Y\) the linear space spanned by \(X\cup Y\). The _direct sum (direct, tensor, or Kronecker product)_ of vectors \(\varphi\in\mathbb{C}^{n}\) and \(\psi\in\mathbb{C}^{m}\) is the vector \(\varphi\oplus\psi=(\varphi_{1},\ldots,\varphi_{n},\psi_{1},\ldots,\varphi_{n} )\in\mathbb{C}^{n+m}\) (\(\varphi\otimes\psi=(\varphi_{1}\cdot\psi,\ldots,\varphi_{n}\cdot\psi)\in \mathbb{C}^{n\cdot m}\)). It is easy to see that \(\|\varphi\otimes\psi\|=\|\varphi\|\cdot\|\psi\|\), and \(\|\varphi\oplus\psi\|^{2}=\|\varphi\|^{2}+\|\psi\|^{2}\). Given a vector \(\varphi\in\mathbb{C}^{n}\), we let \(\mathrm{diag}(\varphi)\in\mathbb{C}^{n\times n}\) be the _diagonal matrix_ having \(\varphi\) on its main diagonal and \(0\) elsewhere, i.e., \(\mathrm{diag}(\varphi)_{ij}=\varphi_{i}\) if \(i=j\) and \(0\) otherwise. Given the vector \(\mathbf{1}=(1,\ldots,1)\in\mathbb{C}^{n}\), we let \(I^{(n)}=\mathrm{diag}(\mathbf{1})\) be the \(n\times n\) identity matrix. The _inverse_ of a matrix \(M\in\mathbb{C}^{n\times n}\) is the unique matrix \(M^{-1}\in\mathbb{C}^{n\times n}\) (if it exists) such that \(M\cdot M^{-1}=I^{(n)}=M^{-1}\cdot M\). Let us quickly overview two matrix families playing a crucial role in the mathematical foundations of quantum mechanics and computing:* _Unitary matrices_: A matrix \(M\in\mathbb{C}^{n\times n}\) is _unitary_ whenever \(M\cdot M^{\dagger}=I^{(n)}=M^{\dagger}\cdot M\); thus, \(M^{-1}=M^{\dagger}\) for \(M\) being unitary. Equivalently, \(M\) is unitary if and only if it preserves the norm, i.e., \(\|\varphi\cdot M\|=\|\varphi\|\) for any vector \(\varphi\in\mathbb{C}^{n}\). Direct sums and products of unitary matrices are unitary as well. * _Hermitian matrices_: A matrix \(M\in\mathbb{C}^{n\times n}\) is _Hermitian (or self-adjoint)_ whenever \(M=M^{\dagger}\). Let \(\mathcal{O}\in\mathbb{C}^{n\times n}\) be an Hermitian matrix, \(\
u_{1},\
u_{2},\ldots,\
u_{s}\) its eigenvalues, and \(E_{1},E_{2},\ldots,E_{s}\subseteq\mathbb{C}^{n}\) the corresponding eigenspaces. It is well known that each eigenvalue \(\
u_{k}\) is real, that \(E_{i}\) is orthogonal to \(E_{j}\) for every \(1\leq i\
eq j\leq s\), and that \(E_{1}+E_{2}+\cdots+E_{s}=\mathbb{C}^{n}\). So any vector \(\varphi\in\mathbb{C}^{n}\) has a unique decomposition as \(\varphi=\varphi_{(1)}+\varphi_{(2)}+\cdots+\varphi_{(s)}\) for unique \(\varphi_{(j)}\in E_{j}\). The linear transformation mapping \(\varphi\) to \(\varphi_{(j)}\) is the _projector_\(P_{j}\in\mathbb{C}^{n\times n}\) onto the subspace \(E_{j}\). Actually, the Hermitian matrix \(\mathcal{O}\) is biunivocally determined by its eigenvalues and projectors as \(\mathcal{O}=\sum_{i=1}^{s}\
u_{i}\cdot P_{i}\). We recall that a matrix \(P\in\mathbb{C}^{n\times n}\) is a projector if and only if \(P\) is Hermitian and idempotent, i.e., \(P^{2}=P\). As we will see in the next section, all linear algebra concepts so far recalled will provide a suitable mathematical description of a quantum finite state automaton and its computation. In fact, in accordance with quantum mechanics principles:  
* The state of a quantum finite state automaton \(A\) at any given time during its computation is represented by a norm \(1\) vector from the Hilbert space spanned by the basis states of \(A\); such a norm \(1\) vector is called _superposition of basis states_. * The state evolution of \(A\) in a computation step is modeled by unitary matrices. * Information on certain characteristics of \(A\) are probabilistically extracted by measuring some \"observables\" represented by Hermitian matrices. The reader is referred to [50] for a gentle introduction to the mathematical foundations and interpretation of quantum mechanics.