Quantum Computing

Quantum Computing#

This Chapter introduces tha main concepts and tooling in Quantum Computing.

Introduction#

In classical computing information is typically encoded in bits, whose two possible states are often denoted \(0\) and \(1\). We can represent the bit’s state \(\psi\) in set notation as:

\[ \psi \in \{0, 1\} \]

Electronic circuitry is used to manipulate this classical state during computations. In quantum computing information is encoded in qubits, whose states can correspond to the classical \(0\) and \(1\) states or can be in a superposition of both states at once. We can represent this quantum state as:

\[ |\psi\rangle = \alpha|0\rangle + \beta|1\rangle \]

where the \(|\cdot\rangle\) expression, known as a ‘ket’ in Dirac notation, is used in the quantum computing literature to denote a state and \(\alpha\) and \(\beta\) are complex-valued amplitudes.

In contrast to a classical bit, the state of a qubit can also be correlated with the state of other qubits, a concept known as ‘entaglement’. The quantum state can be represented by a variety of media, such as light polarization or electron spin, with quantum computers performing computations via manipulation of the system’s quantum state over time. The extra properties of superposition and entanglement in qubits, along with some related others, allow quantum computers to solve certain problems much more efficiently than classical computers. Identification of such problems and the construction of noise-tolerant quantum computers are two on-going grand challenges in research.

This section introduces the mathematical background needed to describe quantum states and computations, followed by the practical implementation of digital quantum simulators and finally specifics on using a digital quantum simulator.

Theoretical Background#

Classical bits can be in a \(0\) or \(1\) state. This state can be represented by the column vectors \(\begin{pmatrix}1 \\ 0\end{pmatrix}\) and \(\begin{pmatrix}0 \\ 1\end{pmatrix}\). In quantum computing these same state vectors are typically distinguished using Dirac notation \(|0\rangle = \begin{pmatrix}1 \\ 0\end{pmatrix}\), \(|1\rangle=\begin{pmatrix}0 \\ 1\end{pmatrix}\).

A qubit can be in a linear superposition of the \(|0\rangle\) and \(|1\rangle\) states, so the state \(|\psi\rangle\) is given by:

\[ |\psi\rangle = \alpha|0\rangle + \beta|1\rangle \]

The square of the modulus of an amplitude is the probability that the qubit will be in the corresponding state at a given time, neccessitating the sum of the squares of the amplitudes to equal one. Measurement of the qubit causes the state to ‘collapse’ such that it ends up being either a \(|0\rangle\) or \(|1\rangle\) state from the measurement time (if measured in that ‘basis’, more on ‘basis’ later).

The techniques and mathematics related to quantum computing stem entirely from the above description and constraints on the nature of the quantum state. Namely, that manipulations must leave the quantum state such that the squares of its amplitudes are to equal one.

In classical computing useful computations are done by combining gates such as ‘AND, NOT, OR’ to perfom logical operations. It can be shown that a limited collection of such gates can be combined to give a universal computer - i.e. one that can implement any algorithm that another universal computer can. An important concept in these gates is that of reversibility. A NOT gate will transform a \(0\) to a \(1\). We can tell by looking at the output \(1\) that the input was \(0\), so this gate is reversible. An ‘OR’ gate will transform \(01\), \(10\) and \(11\) inputs to a \(1\). We can’t tell which of the inputs led to the \(1\) output, so information has been ‘lost’ (or heat generated) in the operation of this gate. This gate is irreversible.

In quantum computing we can deal only with ‘reversible’ gates - since any ‘leakage’ of information from the quantum system will lead to its collapse and our loss of ability to do useful computation. It turns out that it is possible to identify a set of ‘reversible’ only gates that allow universal computing on a quantum computer. One of the main challenges in quantum computing is in implementing useful algorithms efficiently using this collection of gates.

When studying quantum algortihms it is useful to have a theoretical framework to model the action of gates on the quantum system. Matrices and linear algebra are regularly used in classicial circuit analysis, and extend well to the quantum case. Considering the classical case, we can represent the action of a NOT gate in matrix form as:

\[\begin{split} X = \begin{pmatrix}0 & 1 \\ 1 & 0 \end{pmatrix} \end{split}\]

where:

\[\begin{split} X \begin{pmatrix}1 \\ 0\end{pmatrix} = \begin{pmatrix}0 \\ 1\end{pmatrix} \end{split}\]

o, put another way, it transforms a \(0\) state to a \(1\) state. If we wanted to extend this idea to two wires we first need a way to represent their combined state - which can each be either \(0\) or \(1\). This leads to four possible input states of the system \(00\), \(01\), \(10\) and \(11\).

Extending the idea of using a vector with two entries to represent the single bit, we could use a vector with four entries to represent this combined state - such that state \(00\) is represented by \(\begin{pmatrix}1&0&0&0\end{pmatrix}^\intercal\), \(01\) by \(\begin{pmatrix}0&1&0&0\end{pmatrix}^\intercal\) and so on. We want to adopt an ordering that is consistent with what others use and allows us to use standard mathematical tools to manipulate this state. Generation of this combined state vector from the individual state vector for the wires via the Kronecker product allows us to do this. Assuming the \(00\) state, which has a state vector \(\begin{pmatrix}1 \\ 0 \end{pmatrix}\) for each of the wires, application of the Kronecker product gives:

\[\begin{split} \begin{pmatrix}1 \\ 0 \end{pmatrix} \otimes \begin{pmatrix}1 \\ 0 \end{pmatrix} = \begin{pmatrix}1 \\ 0 \\ 0 \\ 0 \end{pmatrix} \end{split}\]

and so on for the other three states. It is important to note here that conventions differ on the interpreted order for reading the state binary string, e.g. \(01\). Some read from left to right (including the examples here), while others read from right to left (including the Qiskit SDK). The contents of the state-vector depend on the interpreted binary string ordering. One quick way to remember that the index of an amplitude in the state vector is given by evaluating the decimal representation of the binary number corresponding to the state, e.g. \(00=0, 10=2\) etc.

If we had two wires and applied a NOT gate to one, we want a way to represent the transformation from input to output states as a single matrix operation. We want to apply the \(X\) matrix to one of the wires but leave the other unchanged (effectively multiplying it by the identity \(I_2\) matrix). Thanks to our use of a consistent ordering in the creation of the combined state vector we can readily generate a combined matrix from the \(X\) and \(I_2\) submatrices using the Kronecker product:

\[\begin{split} U = X \otimes I_2 = \begin{pmatrix}0&1\\1&0\end{pmatrix} \otimes \begin{pmatrix}1&0\\0&1\end{pmatrix} = \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix} \end{split}\]

we can confirm this transforms our states as approriate, for example:

\[\begin{split} U 00 = U \begin{pmatrix}1\\0\\0\\0\end{pmatrix} = \begin{pmatrix}0\\0\\1\\0\end{pmatrix} = 10 \end{split}\]

flips the bit of the first wire but leaves the second unchanged. Similarly it maps the states \(10\) to \(00\), \(11\) to \(01\) and \(01\) to \(11\)

Finally, we want to generalize this concept to \(n\) wires with a NOT gate on the \(i\)th wire. Our matrix \(U\) will be of size \(2^n \times 2^n\). We use the indentity matrix for each wire note operated on by the NOT gate and combine them as follows:

\[ U = I_{2,0} \otimes I_{2,1} ... \otimes I_{2, i-1} \otimes X \otimes I_{2, i+1} ... \otimes I_{2, n-1} \]

Binary gates work in a similar manner, acting as \(4 \times 4\) matrices on the selected bit indices.

Quantum Circuits#

The above introduction applies to both quantum and classicial circuits. However for quantum circuits the operator matrices and state vectors are generally complex-valued. Quantum gates can also put qubits in a superposition of states or entangle their states. A commonly used gate to put a qubit in superposition of \(|0\rangle\) and \(|1\rangle\) states is a Hadamard gate, described by the matrix:

\[\begin{split} H = \frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&-1\end{pmatrix} \end{split}\]

. Applying this gate to the state \(|0\rangle\) gives:

\[\begin{split} H|0\rangle = H \begin{pmatrix}1 \\ 0\end{pmatrix} = \begin{pmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{pmatrix} = \frac{1}{\sqrt{2}} \begin{pmatrix}1 \\ 0\end{pmatrix} + \frac{1}{\sqrt{2}} \begin{pmatrix}0 \\ 1\end{pmatrix} = \frac{1}{\sqrt{2}} |0\rangle + \frac{1}{\sqrt{2}} |1\rangle \end{split}\]

. This resulting state is sometimes denoted the \(|+\rangle\) state. Application of the Hadamard gate to the \(|1\rangle\) state similarly gives a state denoted \(|-\rangle\).

A binary gate that is of interest for producing entangled states is the Controlled Not, CNOT or CX gate. This applies a NOT to a target qubit if an input control qubit is not in the \(|0\rangle\) state and has the matrix:

\[\begin{split} CX = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix} \end{split}\]

Its application on the \(|00\rangle\) state leaves it unchanged, while its application on the \(|10\rangle\) state sends it to \(|11\rangle\). Application of a Hadamard gate to the control qubit followed by the CNOT puts the two involved qubits in an entangled state, known as the Bell state. Following the ‘two wire’ classical circuit example we can represent the action of these gates on the state \(|0\rangle\), starting with the Hadamard gate:

\[\begin{split} H \otimes I_2 |00\rangle = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1 \end{pmatrix} \begin{pmatrix}1\\0\\0\\0\end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix}1 \\0\\1\\0\end{pmatrix} \end{split}\]

which can be shown to be equivalent to the state \(|+0\rangle\) as would be intuitively expected. Application of the \(CX\) gate then gives:

\[\begin{split} CX |+0\rangle = \frac{1}{\sqrt{2}}\begin{pmatrix}1\\0\\0\\1\end{pmatrix} = \frac{1}{\sqrt{2}}\begin{pmatrix}1\\0\\0\\0\end{pmatrix} + \frac{1}{\sqrt{2}}\begin{pmatrix}0\\0\\0\\1\end{pmatrix} = \frac{1}{\sqrt{2}}|00\rangle + \frac{1}{\sqrt{2}}|11\rangle \end{split}\]

The state \(\frac{1}{\sqrt{2}}|00\rangle + \frac{1}{\sqrt{2}}|11\rangle\) is known as a Bell state. Measurement of one of the qubits in this state results in a collapse of the other qubit to the same state.

Digital Quantum Simulators#

For prototyping or studying quantum circuits it can be neccessary to simulate them on classicial computers. A digital quantum simulator (sometimes just quantum simulator) is a piece of software to do this. There are several techniques for simulating quantum circuits. A basic, but inefficient, one involves assembling a matrix representation of all gates in a \(2^n \times 2^n\) matrix and multiplying it by the initial state vector for \(n\) qubits.

A naive assembly and application of the matrix could involve the following steps:

U = I
for each gate:
    for each qubit:
        if qubit interacts with gate:
            matrix = Kronecker product of matrix with gate matrix
        else:
            matrix = Kronecker product of matrix with Identity matrix
    U *= matrix
state_1 = U * state_0

The performance of this approach can be improved by using a sparse representation of the matrix and modifying only indices with a gate. Schemes to allow parallel assembly and solution of the system are also possible.

Further Reading#

Contents