A Student Post: The Basic Mathematics of Quantum Computing

Outline

This blog post is purposed with denoting and recognizing the basic principles involving the mathematics behind quantum computing. This write up is directed towards upper level undergraduates, as well as graduate students, with backgrounds in mathematics or computer science.

This article will cover the simulation and representation of quantum physics using specialized computer bits and linear algebra. These specialized bits are called qubits. As the nature of these bits was covered in the last post, here we will describe the basic operations that can be performed on them. These operations are the beginning to understanding how quantum exponential speed up is possible.

Along with the qubit, we will cover the mathematics behind quantum gate manipulation. Using quantum gates we allow our system to enter into a state of superposition. By applying one of these gates to a qubit we hence alter the probabilistic complexities of that qubit, allowing our qubit system to be derived with varying probabilities for its position.

An Overview

As discussed in the last post, the nature of superposition can be interpreted by the implementation of qubits. A qubit can be interpreted as a matrix. Each qubit represents a probabilistic quantum state, where each indincy of the matrix can be viewed as the probability of the system being in said state. As a reminder, it is important to create a basis for a qubit to possibly occupy multiple states at once, as we are trying to emulate the quantum theory of superposition (Refer to First Post). From a qubits static state, we can perform operations to transform a qubit. Qubit transformations are completed by applying whats called a quantum gate. These quantum gates take the form of square matrices, as they must also be what is called, unitary. In order to transform a qubit into a subsequent state we must apply the quantum gate with matrix multiplication. The indices of the new matrix after performing the multiplication now represent the probabilities of the system residing in each position of the new state. We will see examples of this further on.

Before reaching the mathematical theory, there are a few notations that must be defined. One of the most important being the ket, generically as \left|\varphi\right> . This is considered to be the shorthand notation for representing the probabilistic state of a qubit. Using this notation, it becomes easier to perform a quantum gate multiplication on a particular qubit without drawing out the matrices themselves, as these can get quiet large. At this point it is important to note that all qubits take the form of column vectors. In computer science terms, this can be seen as a one-dimensional array rotated to be viewed vertically. Let us know recognize the most simple of qubits,  \left|0\right> and  \left|1\right>. Where  \left|0\right> = \left(\begin{array}{c} 1\\ 0\end{array}\right)  and  \left|1\right> = \left(\begin{array}{c} 0\\ 1\end{array}\right).

Let us recognize that qubit  \left|0\right> holds a 100% chance of being in state 0 and qubit  \left|1\right>  holds a 100% chance to be in state 1.

We can denote any qubit as \left|\varphi\right> = [C_0,C_1.....C_n]^T containing 2^n number of rows.  Notice we use C to denote each indicy of the qubit. This is due to the fact that qubit state probabilities are represented as complex numbers. However, we will learn the ropes first using real numbers.

Throughout this article we recognize M as a matrix with entries denoting the probability of a movement between positions, or more simply a quantum gate and X as a qubit matrix representing the static probabilities for the systems current position. When in reference to quantum computations these matrix entries will be in terms of complex numbers where a_{ij} \in \mathbb{C}. Lastly, we want to recognize the Hadamard matrix, which is the controlled quantum gate used to transform the ket matrix into superposition. The Hadamard matrix will be denoted with H where = \left(\begin{array}{cc} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} \end{array}\right).

Principle Operations

First, it is important to note the sizes of matrices M and XM is always a square matrix made up of size N \times N where N is the number of possible positions. Qubit X is always a column vector denoting the state of the state of the system. Next, we must cover the matrix multiplication of M \times X, were the product is equal to the state of the system after one movement. This matrix can be denoted as Y which itself is a qubit. The number of movements, K, is equal to the number of times is multiplied by itself. Therefore, the column vector, or qubit, Y with constraints entries for probability of the system being in each position after movements, equal to M^k X = Y.

Lets look at an example.

Movement between position t and t + 1 described by matrices M \times X = Y

\left(\Large \begin{array}{ccc} \frac{1}{8} & \frac{3}{8} & \frac{1}{2}\\ 0 & \frac{9}{16} & \frac{7}{16}\\ \frac{7}{8} & \frac{1}{16} & \frac{1}{16} \end{array}\right) \times \left(\Large \begin{array}{ccc} \frac{1}{2} \\ \frac{1}{4} \\ \frac{1}{4} \end{array}\right) = \left(\Large \begin{array}{ccc} \frac{9}{32} \\ \frac{1}{4} \\ \frac{30}{64} \end{array}\right) .

M describes the probability of movement between the three positions. Probability of moving from positions 1 \rightarrow 3 = \frac{7}{8}. Qubit X describes the static probabilities of the positions the state is currently occupying. While qubit Y describes those same static probabilities after a movement. Notice the sum of all columns or rows is equal to 1.

Let us quickly touch upon the notation for a complex quantum gate such as H, which is the form all quantum gates must take. When in relation to the set \mathbb{C} we will denote M with U as unitary where the sum of all entries modules squared is equal to one, this allows us to fill our matrix with complex numbers, correctly representing the qubit transformation of superposition when applying matrix H.

By definition the conjugate transpose of a unitary matrix is also its inverse, we will take its conjugate transpose, or adjoint, as U(cross). The importance of this is that by taking the adjoint of U at position t + k and applying it our state we will effectively receive the qubit at the state of t - k. By doing this, we allow in the analysis of results without analyzing input, substantially cutting down on the level of system decoherence.

Let us now practice an example using a qubit that only contains complex probabilities. The importance of this example is to notice how we evaluate a qubit that contains indices of complex numbers.

Finding the norm of the matrix by taking the dot product of square roots of its vector rows and vector columns is most crucial. Then by applying this value as a scalar to the original qubit matrix and taking the square modules, we receive the probability of being in each position at time t \pm k.

First we again notice \left| 1 \right> = \left(\begin{array}{cc} 0 \\ 1 \end{array}\right), where there is a zero probability that the qubit is in state 0. Now lets consider a qubit that has been moved through a few quantum states and has different probabilities correlating to the possibilities of being in states 0 and 1. We can define such a qubit as, \left|\varphi\right> = \left(\begin{array}{cc} 2+3i \\ 4+2i\end{array}\right) = S

Here we evaluate the norm and then re-apply this to our original qubit.

\sqrt{S} = \sqrt{\left(\begin{array}{cc} 2+3i & 4+2i \end{array}\right) \times \left(\begin{array}{cc} 2+3i \\ 4+2i\end{array}\right)} = \sqrt{13 + 20} = \sqrt{33}

Now we divide S by \sqrt{33} and then evaluate the qubit by taking S^2 . Such as:

\frac{\Large S}{\Large \sqrt{33}} =  \left(\Large \begin{array}{cc} \frac{2+3i}{\sqrt{33}} \\ \frac{4+2i}{\sqrt{33}}\end{array}\right)^2 = \left(\Large \begin{array}{cc} \frac{13}{33} \\ \frac{20}{33}\end{array}\right)

From the transformed matrix we can see the probability of qubit S being in state \left|0 \right> = \frac{13}{33} and the probability of state \left|1 \right> = \frac{20}{33}. We can see this is correct because the two probabilities add to one.

The Tensor Product

Finally, we must address the operation of quantum entanglement. Quantum entanglement is the process of intertwining two separable states with their individual complex probabilities into one state, or qubit, with a new set of static probability. This quantum operation may be the most important principle, as it allows for all the matrix manipulation previously described. In addition, we can even “multiply” or append qubits that are of different rows and columns, something that is not normally achievable.

The principle notation involving the joining of two qubits is denoted as the tensor product. This is the scalar multiplication of one matrix by another, in order to combine the probability of being in both states at once. The tensor product is denoted by \otimes and is the main operation applied to qubits in order to combine states.

Let us once again look at the two most basic qubits,  \left|0\right> and  \left|1\right>. As you recall these qubits are denoted as two column matrices of probabilities 1 and 0. However let us supposed we wanted combine our two quantum states into one.

Lets evaluate,

\left|0\right> \otimes \left|1\right> = \left(\begin{array}{c} 1\\ 0\end{array}\right) \otimes  \left(\begin{array}{c} 0\\ 1\end{array}\right) = \left|01\right>  = \left(\begin{array}{c} 0\\ 1\\0\\0\end{array}\right)

Where the system has a 100% probability to be in state 01.

While this may seem counter intuitive to the complexity involved, this allows the for quick combination between qubits, especially when applying quantum gates. Here we can create any size multitude of a column vector qubit. It is important to note that the column vector representing a qubit grows exponentially with the number of bits allocated. That is a 2^m \times 1 matrix.

For instance, take the operation: \sqrt{3} \left(\begin{array}{c} 1\\ 0\\1\\1\end{array}\right)

Normally, this scalar multiplication would just be as such, but we can represent this using tensor products.

Firstly, notice that positions \left|00\right>, \left|10\right>, \left|11\right> All have 100% probability to be their respect states.

But consider this in ket notation as, \LARGE{\frac{\left|00\right> + \left|10\right> + \left|11\right>}{\sqrt{3}}}

Now we can see that all three positions of the qubit have an equal complex probability by being divided by \sqrt{3}

From here we apply our gate operations in the same respect, by using the tensor product we can apply our unitary matrices of the probability of state movement, such as H, to the matrix of a qubit. Where U\left|\varphi\right> represents the system at position t + 1, if U = H then the qubit system at position t + 1 would be in superposition.

This final concept of the Tensor Product is relatively hard to grasp especially without a practical example. For that reason, the next post will center around implementing what is known as Deutsch’s Algorithm and combination of quantum input.

Written By: Mitchell Mesecher

References: 

An Introduction to Quantum Computing, Noson S. Yanofsky

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s