# Unary Quantum Finite State Automata with Control Language
## 2 Preliminaries
### Linear Algebra  
As seen in the previous section, few elementary concepts from linear algebra may suitably describe the computation of a classical device such as a dfa. When it comes to the quantum world, additional and deeper notions of linear algebra are needed to properly describe and analyze quantum computational devices. So we are now going to quickly recall such notions, and we refer the reader to, e.g., [49; 50; 51; 52], for in-depth presentations. The fields of real and complex numbers are, respectively, denoted by \(\mathbb{R}\) and \(\mathbb{C}\). Given a complex number \(z=a+ib\), with \(a,b\in\mathbb{R}\), its _conjugate_ is denoted by \(z^{*}=a-ib\) and its _modulus_ is \(|z|=\sqrt{z\cdot z^{*}}\). By \(\mathbb{C}^{n\times m}\), we denote the set of \(n\times m\) matrices with entries in \(\mathbb{C}\). Given a matrix \(M\in\mathbb{C}^{n\times m}\), we denote: by \(M_{ij}\), its \((i,j)\)th entry; by \(M^{*}\in\mathbb{C}^{n\times m}\), the matrix satisfying \(M^{*}{}_{ij}=(M_{ij})^{*}\); by \(M^{T}\in\mathbb{C}^{m\times n}\), its _transpose_, i.e., the matrix with \(M^{T}{}_{ij}=M_{ij}\); and by \(M^{\dagger}=(M^{T})^{*}\), its _adjoint_. For matrices \(A,B\in\mathbb{C}^{n\times m}\), their _sum_ is the \(n\times m\) matrix \((A+B)_{ij}=A_{ij}+B_{ij}\). For matrices \(\mathbb{C}\in\mathbb{C}^{n\times m}\) and \(D\in\mathbb{C}^{m\times r}\), their _product_ is the \(n\times r\) matrix \((\mathbb{C}\cdot D)_{ij}=\sum_{k=1}^{m}\mathbb{C}_{ik}\cdot D_{kj}\). For matrices \(A\in\mathbb{C}^{n\times m}\) and \(B\in\mathbb{C}^{p\times q}\), their _direct sum_ and _direct (or tensor or Kronecker) product_ are the \((n+p)\times(m+q)\) and \(n\cdot p\times m\cdot q\) matrices defined, respectively, as  
\[A\oplus B=\left( \begin{array}{cc}A&\mathbf{0}\\ \mathbf{0}&B\end{array} \right),\quad A\otimes B=\left( \begin{array}{ccc}A_{ 11}\cdot B&\cdots&A_{1m}\cdot B\\ \vdots&\ddots&\vdots\\ A_{n1}\cdot B&\cdots&A_{nm}\cdot B\end{array} \right),\]  
where \(\mathbf{0}\) denotes zero-matrices of suitable dimensions. When operations are allowed to take place by matrix dimensions, the following properties hold:  
\[(A\oplus B)\cdot(\mathbb{C}\oplus D)=(A\cdot\mathbb{C})\oplus(B\cdot D)\ \ \ \text{and}\ \ \ (A\otimes B)\cdot(\mathbb{C}\otimes D)=(A\cdot\mathbb{C})\otimes(B\cdot D).\]  
A _Hilbert space_ of dimension \(n\) is the linear space \(\mathbb{C}^{n}\) of \(n\)-dimensional complex row vectors equipped with the sum and product by elements in \(\mathbb{C}\) where for vectors \(\varphi,\psi\in\mathbb{C}^{n}\), the _inner product_\(\langle\varphi,\psi\rangle=\varphi\cdot\psi^{\ddagger}\) is defined. The \(i\)th component of vector \(\varphi\in\mathbb{C}^{n}\) is denoted by \(\varphi_{i}\), and the _norm_ of \(\varphi\) is given by \(\|\varphi\|=\sqrt{\langle\varphi,\varphi\rangle}=\sqrt{\sum_{i=1}^{n}|\varphi _{i}|^{2}}\). For a complex number \(z\in\mathbb{C}\), we let \(z\cdot\varphi\in\mathbb{C}^{n}\) be the vector satisfying \((z\cdot\varphi)_{i}=z\cdot\varphi_{i}\). Clearly, we have \(\|z\cdot\varphi\|=|z|\cdot\|\varphi\|\). For vectors \(\varphi,\psi\in\mathbb{C}^{n}\), the triangular inequality states that \(\|\varphi+\psi\|\leq\|\varphi\|+\|\psi\|\). Vectors \(\varphi\) and \(\psi\) are _orthogonal (orthonormal)_ whenever \(\langle\varphi,\psi\rangle=0\) (and \(\|\varphi\|=1=\|\psi\|\)). An orthonormal basis of \(\mathbb{C}^{n}\) is any set of \(n\) orthonormal vectors in \(\mathbb{C}^{n}\). In particular, the _canonical basis_ of \(\mathbb{C}^{n}\) is the set \(\{\mathrm{e}_{1},\mathrm{e}_{2},\ldots,\mathrm{e}_{n}\}\) of orthonormal vectors, where \(\mathrm{e}_{i}\in\mathbb{C}^{n}\) is the vector having \(1\) as its \(i\)th component and \(0\) elsewhere. The canonical basis _spans_\(\mathbb{C}^{n}\) in that any \(\varphi\in\mathbb{C}^{n}\) can be obtained as the (unique) linear combination \(\varphi=\sum_{i=1}^{n}\varphi_{i}\cdot\mathrm{e}_{i}\). More generally: a _subspace_ is any subset of \(\mathbb{C}^{n}\) that is a vector space.