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