Deutsch-Jozsa algorithm

                    The Deutsch-Jozsa algorithm - published by David Deutsch and Richard Jozsa in 1992 - is one of the first quantum algorithms with nice speedup over its classical counterpart, and it represents a good example of quantum parallelism.

Constant and balanced functions

In most typical cases where functions are involved, we are mostly interested in finding the result of a function. But in some cases though, the function evaluations are not important, but the characteristics or the properties of the functions are. In this area, quantum algorithms can be helpful.

In general, the functions we consider are noted as f(x) where f is the function that operates on an input variable called x. The evaluation of a function for a specific input is also called the result and sometimes noted as y, where y = f(x).

Let's start with a very simple function f which takes a single bit (a boolean value) as its input, and it produces a single bit as well. The function thus only operates on either '0' and '1' and its result is either '0' or '1'

Let f :{0, 1}→{0, 1}.

The combination of 2 input options and 2 output options leads to 4 possible cases for this function, which we will name f1, f2, f3 and f4:

f1: f(0) = 0 and f(1) = 0

f2: f(0) = 0 and f(1) = 1

f3: f(0) = 1 and f(1) = 0

f4: f(0) = 1 and f(1) = 1

The Deutsch problem

This being said, the question that we ask ourselves is very simple: does f(0) =f(1)?

This is often stated in a much more pedantic way for whatever reasons: “Is f constant or balanced?

- by constant, we mean f(0) = f(1),

- by balanced we mean f(0) != f(1).

This is to say in much more words ;-)

From those defintions, it appears that f1 and f4 are constant functions, and f2 and f3 are balanced functions.

We can state the Deutsch problem in an even more pedantic way, as follows:

Determine the value of the parity of f(0) ⊕ f(1) where ⊕ denotes addition modulo two.

Show that if f is constant then the parity is zero, and if f is balanced then the parity is one.

In the Deutsch algorithm, one of the four functions is provided, but we don’t know what function it is. We know it is f1, f2, f3 or f4 but that’s all we know.

We are now asked to find out if this function is constant or balanced. Keep in mind that our task is not to find out if the provided function is f1, f2, f3 or f4 .

Now we get to the intersting part, solving the problem.

Solving the problem

First, we can ask ourselves how many classical queries does it take to solve this problem?

That’s a pretty easy exercise.  It’s two.  It must be two since the values of f(0) and f(1) are completely independent of each other.

We have to ask what both values are, then compare to see if they’re the same ordifferent.

For example, suppose we measure f(0) and the result is 1. From the table above, it seems that in this case, our function is either f3 (which is balanced) or f4 (which is constant). Hence, we don’t have enough information.

In case the result of measuring f(0) is 0, the table above shows that the function is either f1 (which is constant) or f4 (which is balanced). Again, this proves that measuring f(0) is not enough to conclude whether the function is constant or balanced. It can be either.

If the number of input bits is increased to n, to verify a function is balanced, we query f for 2^n-1 +1 in the worst case. We have a problem with query complexity that can grow exponentially in the worst case

From functions to Oracle

We can not simply apply a function to a qubit. In our article  Introduction to quantum logic gates we explained that all quantum gates need to be reversible.

A function that, after being applied makes it impossible to retrieve the original input, can not be used in a quantum circuit. Therefore, the function first need to be transformed into a reversible quantum gate.

That is, the Hadamard transform produces an equal superposition of all computational basis states.

After the Hadamard transform on the query register (or first qubit) and the Hadamard gate on the answer register (or second qubit) we have the state

The query register is now a superposition of all values, and the answer register is in an evenly weighted superposition of 0 and 1.

Next, the function f is evaluated by applying the same oracle which maps the state to , and for the same reasons as for above, giving:

Then, we apply n Hadamard gate again.

Fortunately, we know from our previous article Parallel superposition and Hadamard gates that  the general equation for the Hadamard gate transformation on multiple qubits can be summarized in the very useful below equation:

 Applying this equation to |φ₂> we get

Let's consider now the state |0>^⊗n, its amplitude is easily deduced as

Let’s look at the two possible cases – f constant and f balanced – to discern what happens. In the case where f is constant, the amplitude for |0>^⊗n is +1 if f(x)=0 or −1 if f(x)=1.

And because the state is of unit length, it follows that all the other amplitudes must be zero, and an observation will yield 0s for all qubits in the query register.

At the contrary, if f is balanced then the positive and negative contributions to the amplitude for |0>^⊗n cancel, leaving an amplitude of zero, and a measurement must yield a result other than 0 on at least one qubit in the query register.

We’ve shown that a quantum computer can solve Deutsch-Jozsa’s problem with one evaluation of the function f compared to the classical requirement for 2^n-1 + 1 evaluations.