# Generative Music with Partitioned Quantum Cellular Automata
## 2 Background
### Quantum Computing  
The basic unit for representing information in a quantum computer is the _qubit_. A qubit is to a quantum computer what a bit is to a digital computer. However, qubits operate at the atomic or even subatomic level. Therefore, they are subject to the laws of quantum mechanics, with their properties of superposition and entanglement. In quantum mechanics, an object does not exist in a determined state. Its state is unknown until one observes it. The state of a qubit lives in a two-dimensional complex vector space, referred to as a two-dimensional Hilbert space. The canonical basis vectors in a Hilbert space are notated as \(\ket{0}\) and \(\ket{1}\). This notation, referred to as the Dirac notation, provides an abbreviated way to represent a vector. For instance, \(\ket{0}\) and \(\ket{1}\) represent the vectors shown in Equation (1):  
\[\ket{0}= \begin{bmatrix}1\\ 0\end{bmatrix} \ \ \text{and}\ \ \ \ket{1}= \begin{bmatrix}0\\ 1\end{bmatrix}  \tag{1}\]  
The general state \(\ket{\psi}\) of a qubit is written as a linear combination of the basis vectors as follows: \(\ket{\psi}=\alpha\ket{0}+\beta\ket{1}\) with \(\alpha,\beta\in\mathbb{C}\) and \(|\alpha|^{2}+|\beta|^{2}=1\). This linear combination expresses a state of _superposition_. In a nutshell, qubits process information in a state of superposition. However, they will return binary numbers (zeros and ones) when we read them. In quantum computing terminology, the act of reading qubits is referred to as _projective measurement_. Not expressed in the equation for \(\ket{\psi}\) above, however, is the phase of the qubit. To visualize this, let us consider a single qubit as a transparent sphere with opposite poles. From its centre, the vector \(\ket{\psi}\) can point to anywhere on the surface. This sphere is called the _Bloch sphere_ and the vector is referred to as a _state vector_ (Figure 3). The angle \(\varphi\) defines the phase. Figure 1: An example of a one-dimensional CA consisting of a bar of 13 cells. Figure 2: An example of a two-dimensional CA consisting of a grid of 36 cells. Quantum computers are programmed by applying sequences of unitary linear operations \(\mathbf{U}\) to state vectors: \(\left|\psi^{\prime}\right\rangle=\mathbf{U}\left|\psi\right\rangle\). Programming languages for quantum computing provide a number of such linear operators, referred to as _gates_. For instance, the \(\mathbf{X}\) gate rotates the state vector by 180 degrees around the x-axis of the Bloch sphere. Thus, if the qubit vector is pointing to \(\left|0\right\rangle\), then this gate flips it to \(\left|1\right\rangle\): \(\left|1\right\rangle=\mathbf{X}\left|0\right\rangle\), and vice versa, \(\left|0\right\rangle=\mathbf{X}\left|1\right\rangle\). A parametric rotation \(\mathbf{R}\mathbf{x}(\theta)\) gate is typically available for quantum programming, where the angle for the rotation around the x-axis is specified. Similarly, there are \(\mathbf{R}\mathbf{z}(\varphi)\) and \(\mathbf{R}\mathbf{y}(\theta)\) gates for rotations on the z-axis and y-axis of the Bloch sphere. Mathematically, quantum gates are represented as matrices. For instance, the \(\mathbf{X}\) gate, which flips the state of a qubit is represented as shown in Equation (2). In this case, gate operation is represented mathematically as the multiplication of a matrix (gate) by a vector (qubit state). \[\mathbf{X}= \begin{bmatrix}0&1\\ 1&0\end{bmatrix}  \tag{2}\]  
Thus, the application of an \(\mathbf{X}\) gate to \(\left|0\right\rangle\) is written as shown in Equation (3):  
\[\mathbf{X}(\left|0\right\rangle)= \begin{bmatrix}0&1\\ 1&0\end{bmatrix} \times \begin{bmatrix}1\\ 0\end{bmatrix} = \begin{bmatrix}0\\ 1\end{bmatrix} =\left|1\right\rangle \tag{3}\]  
An important gate for quantum computing is the Hadamard gate, referred to as the \(\mathbf{H}\) gate. It has the matrix shown in Equation (4). \[\mathbf{H}= \begin{bmatrix}\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}}\end{bmatrix} =\frac{1}{\sqrt{2}} \begin{bmatrix}1&1\\ 1&-1\end{bmatrix}