A Student Post: The Basic Mathematics of Quantum Computing

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 and mathematically applied to quantum gate transformations, thus allowing for the representation of quantum states. Qubit quantum state calculations can be represented using matrices and modeled by graphs, where the probability of a movement between vertices corresponds to the probability of the of movement between a state position.

Before reaching the mathematical theory, there are a few notations that must be defined. One of the most important being the ket. This is the notation for performing quantum operations on qubits to create quantum states of complex numbers denoted by column vectors.  \left|\varphi\right> = [C_0,C_1.....C_n]^T  Along with this we denote M as a matrix with entries for the probability of a movement between vertices, or positions. X as matrix containing entries for the probability of the system at its current state. 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 vertices, or possible positions.  X is always a column vector denoting the state of every vertex, or 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 K time clicks. This matrix can be denoted as Y. The number of time clicks, K, is equal to the number of times is multipled by itself. Therefore, the column vector Y with entries of the probability of the state being in each position is equal to M^k X = Y. However, 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 time t + k and applying it our state we will effectively receive the probability of the state at t - k. By doing this, we allow in the analysis of results without analyzing input, substantially cutting down on the level of system decoherence.

The principle notation involving the joining of two quantum states is denoted as the tensor product. This is the scalar multiplication of 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. 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 time t + 1, if U = H then the qubit system at time t + 1 would be in superposition. 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 2^m matrix.

Once a qubit has moved states with the tensor product of a unitary complex matrix it is necessary to realize how we evaluate these state probabilities as real numbers. Finding the norm of the matrix by taking the 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.

Example Operations

Here are a few examples of the above operations:

Movement between time 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}X describes the static probabilities of the positions the state is currently occupying. While Y describes those same static probabilities after a movement. Notice the sum of all columns or rows is equal to 1.

Next we will look at transforming a state of complex numbers, such as the Hadamard matrix, back to real numbers.

First we 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.

Deutsch’s Algorithm

Deutsch’s Algorithm is the one of the most representable quantum algorithms. This algorithm consists of four black box functions with an input of one or zero and an output one or of zero. Where f{0,1} -> {0,1}. If f(0) =/ f(1), f(x) is balanced and f(0) = f(1) is constant. Out of out four functions, two are balanced and two are constant. We must realize that these functions are unviewable and therefore we cannot know what operations are being performed on the input. On a normal classical computer it would take at least two evaluations in order to concur the function being used. However, the analysis of the quantum states allows for the determination with only one evaluation.

Using the principles of superposition on qubits we can evaluate both inputs at once to effectively cut our computational complexity in half. 363px-Deutsch-Jozsa_Algorithm.svg

From the diagram above we can see that by applying two qubits as the inputs and subsequently turning them both in a superposition, the value of the qubits becomes negligible as they have equal probability of being in both states. We represent this as \left|\varphi_1\right> = H\left|0\right>  \otimes H\left|1\right> = \frac{\left|0\right> + \left|1\right>}{ \sqrt{2}} \frac{\left|0\right> - \left|1\right>}{ \sqrt{2}}. We use the tensor product to combine these two states to be the result \left|\varphi_1\right> = \frac{\left|00\right> - \left|01\right> + \left|10\right> - \left|11\right>}{2} . This combined state can then be applied to our function as one input. After some simplifying of the result we obtain a piece-wise function determining the function used based on the qubit output. \left|\varphi_2\right> = \begin{cases}  (\pm 1) \frac{\left|0\right> + \left|1\right>}{ \sqrt{2}}  \frac{\left|0\right> - \left|1\right>}{ \sqrt{2}} & f = constant \\  (\pm 1) \frac{\left|0\right> - \left|1\right>}{ \sqrt{2}}  \frac{\left|0\right> - \left|1\right>}{ \sqrt{2}} & f = balanced \end{cases}

We then effectively apply our last H, as it is its own inverse, to move these qubits out of superposition for observation at \left|\varphi_3\right> and see the constraint on balanced or constant function. If the results qubit is in a state of \left|0\right> then we evaluate the function as constant, otherwise f(x) is balanced. We see this where \left|\varphi_3\right> \begin{cases}  (\pm 1) \left|0\right> \frac{\left|0\right> - \left|1\right>}{ \sqrt{2}}  & f = constant \\  (\pm 1) \left|1\right> \frac{\left|0\right> - \left|1\right>}{ \sqrt{2}} & f = balanced \end{cases}

The computational operations saved by using this algorithm may seem negligible, but when expanded into an algorithmic form the ability to evaluate data to this respect can have a quadratic decrease on time complexity. This can be shown in the implementation of Grover’s algorithm and the reduced searching time of an unordered list based on exponential speed up.

Written By: Mitchell Mesecher


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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s