Disclaimer

The current posting is considered to be a simple example application of the theorems and mathematics discussed in the last post, The Basic Mathematics of Quantum Computing. The information here will be hard to grasp unless you have covered the operations specified previously. For this reason this post, and most postings following this, will be regarded as a continuation.

Background

Deutsch’s Algorithm is the one of the most representable quantum algorithms. This algorithm was developed in order to illustrate the processing of qubit input and the difference in performance when compared to a classical Turing machine. This algorithm covers the testing of black box functions, or modules of which the operations performed upon the input at the time of execution isn’t known.

In this fashion, in order to determine how the black box executes we would have to test multiple inputs and examine patterns in the outputs. However, for this example we limit the possibilities used to only four boolean functions, two being balanced and two constant.

To clarify, a constant function has the same Boolean output for every input. While a balanced function yields as many 0s as it does 1s. We define our functions as such,

Both inputs of 0 and 1 map to the output 0 or 1 alike.

Both inputs of 0 and 1 map to the opposite output.

In the illustration below, functions one and three are constant, while two and four are balanced.

Normally, with a classic implementation we would need to test at least two inputs to determine if the function inside the black box was constant or balanced. Alternatively, using the principles of superposition on qubits we can evaluate both inputs at once to effectively cut our computational complexity in half.

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 the constant running time of a system.

Complexities

Before learning about the procedure of the algorithm, it’s important to review the mathematics needed in order to complete this excersise. If you recall from the last post we covered something known as the Hadarmad matrix, which is the quantum gate used to tranform a qubit into the state of superposition.

Recall:  H .

Again this is done through matrix tensor multiplication.

It is important to remember that every qubit in any current state can be evaulated as a column vector made up of probabilites of possible occupying states. These column vectors representing the possible state positions of the qubits are represented as complex numbers where  and each indicy belongs to the domain of complex numbers, such that .

Lets review the tensor multiplication of two qubits that contain real number probabilites. Such that   has a 100% to occupy state 0 and has a 100% chance to occupy state 1. Next we apply the tensor product:

Once evaulated, he resulting qubit has four possible states but always has a 100% probabilty to be in the state 01.

Following this procedure we can apply the same operations between and the quantum gate H. Such that,

Hence, the resulting qubit has a complex probability of 50% being in state 0 and 50% of being in state 1. As shown previoulsy, if we wanted to evaulate these as real number probabilites we take the sqaure of the complex numbers.

Now that we have identified a basis for transitioning qubits into a state of superposition we are ready to evaulate Deutch’s Algorithm. Recall, this is possible because of the qubits ability to occupy both testable inputs at once.

Deutsch’s Algorithm

As we recognized, this algorithm consists of four black box functions with an input of one or zero and an output one or of zero. Again, if is balanced, otherwise if is constant.

Now consider  the diagram below. First, notice that this graphic is a quantum circuit in which the two qubit inputs on the left are manipulated through the quantum gates denoted by H. They are then passed to the function which is our black box test.

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 now explain the qubit state at each stage of the algorithm.

At    we start with the initial separated qubit inputs 

Where 

Next we examine state 

First we must apply the matrix H to both our qubits, where

  and 

Finally we tensor together our two superposition qubits to achieve,

.

We use the tensor product to combine these two states to obtain the result  .

Therefore the probability of qubit 

This combined state can then be applied to our function as one input. We then evaualte the state of qubit  as the output after having been applied to the black box function.

Here notice that the sign of this output changes dependent on which function was applied during execution, such that

.

From this expression we can see that depending on the values of we can determine whether the function is balanced or constant. This is because a constant function always yields  

while a balanced always yields   due to the change in sign.

Finally we can put this in terms of a piece wise function where the first qubit is the one that shows the attributes of the function and the second is the static transformation of the bottom qubit.

Recall that because H unitary, or its own inverse, we then effectively apply our last H to the top qubit in order to move it out of superposition for observation at and see the constraint on balanced or constant function.

We see this where 

For clarification, the top qubit is the one that was manipulated by the function and brought out of a state of superposition, while the bottom qubit stayed statically bound to superposition in order to preserve the systems level of decoherence.

While this algorithm is simple, it still gives a tangible example of the applications of qubit mathematics and quantum computation. This procedure was later proven to be useful in determining the contents of many block box functions and can be implemented in a variety of different ways. Unfortunately, I cannot delve into all of the specific applications, as there are many other topics that needed to be covered. However, if you are interested in learning more, an extension of Deutsch’s Algorithm is called the Deutsch-Jozsa Algorithm and can be applied to a much larger domain of input. In fact Deutsch’s Algorithm serves as a basis for many algorithms in quantum computing that serve to expand upon evaluating multiple outputs at once.

Written By: Mitchell Mesecher

Citations: 

Quantum Computing for Computer Scientists, Noson S. Yanofsky

The Discrete Fourier Transform

The Fourier Transformation is a high level mathematical function using the integrals over a continuous wave to compute the component that make up such a wave. As this is done in a continuous fashion, the Discrete Fourier Transform(DFT) is not. The DFT uses the summation of real numbers representing points in time of wave motion. Which makes it an extremely powerful tool to computers because of their discrete nature.

This transformation is accomplished by computing the value of each signal component using every point in time chosen. Every signal value is made of a summation of all the points in time chosen with the value of the signal applied. This is done in the form of circle rotation. Euler’s formula allows us to recognize a basis of imaginary polar coordinates where , thus creating an arbitrary point in . This basis allows us to apply an exponential rotation to all of our points , where K is the signal component being evaluated and n is the point in time. After the transformation is complete we are left with a “list” containing all of the signal components of the original wave.

Written as:

When the DFT is implemented on an algorithmic level it becomes quickly apparent that this runs at an time complexity belonging to . That is because to compute every value K we must add together all of the point by point computations. Also, because of the discrete computation this algorithm is implemented using arrays. Where every index in array K is filled with the summation of points stored in array n. Finally, array K contains the value of every signal component spanned by the wave points chosen. While isn’t inapplicable, the Fast Fourier Transform creates a one layer speed up in time complexity to reach .

The Fast Fourier Transform

The Fast Fourier Transform, or FFT, is a proven way to implement a substantial array transformation on a large amount of data, due to its time complexity of . This speed up was possible due to the amount of redundant calculations made by the Discrete Fourier Transform. These redundant calculations come from the periodic nature of imaginary numbers, where . Due to this property, by splitting the data up into even and odd indices, we are then able to apply the logarithmic time complexity. Using our original equation

,

and denoting as . So we have

,

Now that we’ve condensed the formula, it becomes possible to split between indices  and , as halves of the array n respectively, to perform the Fourier transform as:

Now that the formula has been established and we are aware of the properties of W as

…

Where N is equal to 8.

We define the even summation of the FFT as $latex  G[m] $ and the odd summation as . Therefore we can see that:

…

Given that the input is a power of 2, we can then perform the operation know as the decimating-in-time-algorithm. This is, recursively breaking down every set of transforms into even and odd inputs until only two point DFT’s remain. That is, point transformations, where we implement the recursion until hitting summations or arrays of length 1. At each stage of the algorithm complex operations are needed to build the previous level. Because of the stage construction in \log N, we only have to compute the summations of values themselves N,  while recycling the complex computations.

Quantum Fourier Transform

Now that this basis has been firmly established and we have denoted the fastest time complexity of the Fourier transform using classical computing as , we can further use Quantum gate transformations to a achieve a time complexity such as . Needless to say, this is an exponential speed up of an entire magnitude. To define the transform we first note that can also be defined as set of column matrices denoted as , where s the index of the “array”. We then form the formula as

While this may seem complex, it is important to realize this is a re-representation of the previously defined FFT formula in order to define as a form of column matrices. As we know from the previous post, qubits are defined as column vectors representing system  state probability. If we can reform our input array to be represented as such then we can apply our gate matrices in order to introduce a state of superposition.

Following this the form of basis P is proven under a few propositions, however for the sake of this article we will assume the propositions as true while giving a brief explanation for each.

1.   Each row of matrices  only contains two non zero entries

In the matrices of  we see that the non zero entries are located in the main diagonal and the sub-diagonal depending on the column values of . If we look at this a little closer it becomes clear why this. Putting at this in terms of a double array, if indices and j are equal at all times then we will receive only the diagonal values stored in the array and the same for our matrices. When we traverse all indices in the main diagonal of each matrix, when we receive all entries in the lower sub-diagonal, and yields all entries in the upper sub-diagonal. Because we assumed proposition one we can now say each matrix has been defined depending on the piece-wise function of the indices i and j.

2.  The matrices of P are unitary

If you refer from the last post, unitary is defined as a square matrix where the conjugate transpose is also its inverse. Recall, we need this to be true in order to evaluate output transformations as we due input, in our time steps denoted by t. Subsequently, this allows these quantum gates to be implemented on a quantum computer. However, we must determine what these gates are first. We do this by whats called QR decomposition. The decomposition states that any matrix belonging to  can be broken up into the product of a unitary matrix  and an upper triangular matrix . This then brings us to our next proposition.

3. For any matrix s belonging to    can be made up of the matrices and 

Because the depth of the proofs are being conceded right now, I am going to use proposition three in order to explain the mathematical composition of both  and . Firstly, by multiplying the matrices M and N before traversing the matrix on the left side of the solution we can see that these sets of matrices build  , such as

We then denote that matrix can be written as its form of induction using the Identity and the Hadamard matrix H. By recursively using the formula

for every matrix of matrices we can see this induction compose to

Thus, building every matrix belonging to and completing the unitary requirement of

Lastly, we form our matrices of N as triangular matrices. This is simply the product of all triangular matrices in reverse using R at time denoted by

Finally, we are able to build the Quantum Fourier Transform from the defined decomposition. We first prepare our quantum state as and every complex matrix in  such as,

Where contains every value of the input in the form of ket complex matrices.

Thus we can say, 

The algorithm takes a complex array X as input and uses our quantum gates in to output a quantum state that correspond the probabilities of the real values and amplitudes, given by the original DFT. Thus, we prepare our quantum register of input as

We then move in reverse as an outer loop from

and as an inner loop from

.

At every step in t, we apply our unitary gate operation of as

After applying the quantum gate operation to every matrix at step t, we apply the Hadamard matrix H to the value of at time step s.

After completing every matrix in the reverse time step of s, we have completed the algorithm, this yielding a quantum state $latex \left|\varphi_n \right> $ corresponding to elements of the complex matrix Y.

If we evaluate the time complexity of this transformation we see that the outer loop as steps or equivalently . We see that classically this is equal to the original DTF, however every qubit operation compounds the probabilistic superposition to . Due to this we can say that the operation becomes . This incredible exponential speed up becomes the driving factor of the algorithm and the reason it must be defined in terms of qubits and quantum space.

Written By: Mitchell Mesecher

 

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 . 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,  and  Where    and 

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

We can denote any qubit as  containing number of rows.  Notice we use 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 . 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 H .

Principle Operations

First, it is important to note the sizes of matrices M and X. M is always a square matrix made up of size 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 , 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 M is multiplied by itself. Therefore, the column vector, or qubit, Y with constraints entries for probability of the system being in each position after K movements, equal to .

Lets look at an example.

Movement between position t and described by matrices

.

M describes the probability of movement between the three positions. Probability of moving from positions . 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  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 and applying it our state we will effectively receive the qubit at the state of . 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 .

First we again notice , 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, 

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

Now we divide S by and then evaluate the qubit by taking . Such as:

From the transformed matrix we can see the probability of qubit S being in state  and the probability of state . 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 and is the main operation applied to qubits in order to combine states.

Let us once again look at the two most basic qubits,  and  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,

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 matrix.

For instance, take the operation:

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

Firstly, notice that positions All have 100% probability to be their respect states.

But consider this in ket notation as,

Now we can see that all three positions of the qubit have an equal complex probability by being divided by

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 represents the system at position , if then the qubit system at position 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

What is Quantum Computing?

The nature behind the implementation of quantum computers comes from the attempt to simulate and use principles of quantum mechanics to enhance computational run-time exponentially. Theoretically, any task given to a classical Turing machine can be completed with exponentially less computations on a quantum computer. In order to accomplish this, quantum systems adopt the principle of superposition, or more simply, being in every position at once. When it comes to quantum mechanics this is usually thought of in the realm of photons or waves, but with computers we can apply this theory to the most basic of measurements, a bit. A bit has only two positions, a one or a zero, but by taking advantage of the concept of superposition we can create a bit in both positions at the same time. We define this as a qubit. These qubits, along with high-level mathematics and statistics, allow us to use a small finite space to “hold” many theoretical data values at once, thus maximizing the possible perform-able computations.

The Constraints on Implementation

Having addressed a few of the high level abstractions involved in the implementations of a quantum system, we will now look at some of the physical and theoretical constraints involved. One of the fundamental concepts of quantum physics is that of  observation. You may recall hearing of a study called Schrodinger’s Cats. Using this principle of superposition, Schrodinger stated that an unobserved cat may be in both states of alive and dead at once, until observed by an individual. Once observation occurs, the quantum state of superposition collapses to the classical state of which it was perceived. This principle is denoted as decoherence and is also applied to our integration of qubits. Once the value of a qubit is observed at a certain position, it collapses to the classical state of which it was accessed. Subsequently, there is a limit to a quantum system’s ability to belong to a set of mixed states. It was shown that pure state symmetry breaking imposes a time constraint on which a system as a whole can stay quantum coherent. Additionally, miniaturization of a system compounds upon this time constraint.

After covering the theoretical aspects involved , we can now define the concrete system requirements needed, such as: a well processed and dynamic qubit register for stability when dealing with decoherence; a set of gate matrices to perform necessary operations on the state of a qubit; the longest decoherence time possible given the size of the system; and, the ability for singular measurements when dealing in a state defined by superposition.

Applications of Quantum Computers

One of the most famous applications behind the implementation of quantum computers involves the study of cryptography and encryption. Namely the ability of a computer to factor incredibly large numbers and find their primes. This is the basis behind the world’s asymmetric encryption protocol, such as RSA. If suitable quantum systems become commercially available then new encryption protocol would have to developed and integrated almost overnight. Currently, the factorization ability of a classical binary computer reaches a super non-deterministic polynomial time complexity. Where a normal polynomial time complexity allows an algorithm to be predictable in its run-time based on the size of an input N. When we talk about a super non-deterministic complexity, its understood that the run-time of a specific algorithm cannot be generally determined and may take time exponentially longer than the size of the input. These two time complexities are denoted as NP (non-deterministic polynomial) and P (polynomial-time). The most famous algorithm for the factorization of numbers is known as Shor’s algorithm. This algorithm uses modular arithmetic and a discrete recursive method to factor its input, but unfortunately still falls under our aforementioned NP running time. However, when implemented in a quantum state, this algorithm becomes applicable.

A more relatable example of an application in quantum computing is that of searching through an unordered list of items. The function of searching takes up a large percentage of all computer computation. Subsequently, being able to reduce the run time for this operation for any sized input would be innovative in reducing the total amount of time for computational operations. The current time it takes to find a particular object in an unordered list is evaluated in the worst case scenario. That is, you must search the entire list to find the item you’re looking for. Your time complexity becomes the size of the input N. Using a quantum system, we can do better. Grover’s algorithm takes advantage of the probabilistic principles of quantum computing in order to reduce this running time to O(√N). Unfortunately, this does not still fall under a NP-Complete time complexity; where searching time would be reduced exponentially, Grover’s algorithm offers a quadratic speedup and in the worst case scenario still takes time N. However, this quadratic speedup is not insignificant. Using the aspect of superposition, we can allow every item to be both item we’re looking for and the item we’re not. From here we can use our qubit equation and quantum gate manipulation to infer this answer from the theoretically output, such as the tensor product of input and the function being used. Additionally, the increase in probability for item I+1 ∈ N once we know that item I is not our specific value, is very helpful in lowering our running time. It is important to note that Grover’s algorithm is, in part, a functional expansion on Deutsch’s algorithm.

Written By: Mitchell Mesecher

 

References:

Difficulties in the Implementations of Quantum Computers, Abhilash Ponnath*