Deutsch-Jozsa

The Deutsch-Jozsa algorithm is one of the most basic examples of an algorithm that solves a problem quicker than any classical algorithm. It was first proposed in 1992 and is one of the oldest examples that proves how quantum computers can beat classical computers in certain tasks.

The problem is this: given a 1-bit mathematical function $f$ that takes a single bit as input and produces a single bit as output, determine if the function is "constant" or "balanced".

A constant function is a function that always returns the same output whereas a balanced one is one that returns a 0 for half of the inputs and a 1 for the other half.

Now, there are only 4 different functions that take a single bit as input and output. Here are the two constant functions:

and the two balanced functions:

So our two constant functions are the function that always returns 1 and the function that always returns 0. Our two balanced functions are the identity and the NOT (or inversion) function.

First let's analyse this problem from the classical perspective. How could we determine whether $f$ is constant or balanced?

We could start by simply evaluating $f(0)$ and seeing what value we get. If it is 0, then our function is either the constant 0 function or the identity function. One of these functions is constant and the other balanced, so we need to evaluate $f(1)$ to determine which one it is.

From this example it's fairly clear to see that in any case we will need to query the function twice to determine if it is constant or balanced. This is the best we can do classically.

What we'll see next is the remarkable result that with a quantum computer we can solve our problem by querying the function only once.

But first, we need some more mathematical setup. What does it mean to evaluate a function on a quantum computer? To answer this, we'll introduce the quantum oracle.

The quanutm oracle $U_f$ for a given function $f$ is defined as follows:

where $\oplus$ denotes addition modulo 2.

This looks a bit odd. Where does this value $y$ come from? It is a bit of a technicality, but it is there to ensure that the oracle is reversible.

Note that if we didn't have this $y$ value, the oracle wouldn't be reversible if $f$ was constant since we wouldn't be able to determine the input from the output. We won't go into the details of this here, but it is a necessary condition for quantum operations to be reversible.

We'll denote this operation in a circuit as:

If we simply set $y$ to 0, we get the following:

Now we know how to use our function in the quantum world we can start to evaluate it.

The Deutsch-Jozsa algorithm begins by preparing two qubits in the state:

We know that these are the results of applying the hadamard gate to $\ket{0}$ and $\ket{1}$ respectively. So we can get here with the following circuit:

Note that it is by convention in many of these quantum algorithm circuits that we start with all the qubits in the state $\ket{0}$. Hence why it is necessary to add the $X$ gate on the second qubit.

We then feed these two qubits into our quantum oracle:

The vertical dashed lines are simply there to help us with our mathematical book keeping and tracking the state at different stages of the circuit. We already know about $\ket{\psi_1}$, now let's look at $\ket{\psi_2}$.

We can expand the brackets on $\ket{\psi_1}$ to get:

It's now super easy to apply our quantum oracle to this state as the linear operation simply distributes across the terms in the bracket:

Note the following about the $\oplus$ operation:

Using this fact, let's now evaulate $\ket{\psi_2}$ further:

Now notice that since $f(x)$ is either 0 or 1, we have the following:

A simple test of either case $x=0$ or $x=1$ will confirm this fact.

Once again we are using a clever algebraic trick to pull a variable out of the ket and into a coefficient. You should now be getting used to the fact that these tricks to bring terms in/out of kets/coefficients lie at the heart of many quantum algorithms. There will be much more of this to come!

Let's continue:

The final step of the Deutsch-Jozsa algorithm is to apply the Hadamard gate to just the first qubit. In the current form this is fairly easy to do:

This is now our final state, so all that's left to do is some algebra to get this into a nicer form. We can see that we will end up with 4 different kets each with 2 terms, so we can expand the brackets to get these terms:

If $f$ is a constant function then $f(0) = f(1)$ so we end up with the following:

The last two terms end up with a coefficient of 0 so are dropped.

If $f$ is balanced, then we have $f(0) = \overline{f(1)}$. This has the opposite effect and makes the first two terms evaluate to 0 giving us:

And now, we can clearly see that measurement of the first qubit tells us if the function is constant or balanced. If we measure $\ket{0}$ the function is constant, if we measure $\ket{1}$ the function is balanced.

Our final circuit looks like this:

So we have proven that the Deutsch-Jozsa is indeed able to determine whether a function is constant or balanced with only a single query to the function.

This is the first time we have been able to explicitly show something that a quantum computer can do better than a classical computer. There are many more such cases, but the Deustch-Jozsa algorithm is the most basic example.

Exercises

Exercise 1 (difficult)

Generalise the Deutsch-Jozsa algorithm to any n-bit binary function.

That is, given a function $f$ that takes n bits as input and produces 1 bit as output, determine whether it is constant or balanced. The definition of constant/balanced being slightly different here:

• Constant: The function returns the same output for every input
• Balanced: The function returns 0 for exactly half the inputs and 1 for the other half.

We have the promise that the function will always be constant/balanced. Any other function is not a valid input for this problem.

For the oracle, it takes the same form, but with n qubits as input:

$$U_f(\ket{x_1} \otimes ... \otimes \ket{x_n} \otimes \ket{y}) = \ket{x_1} \otimes ... \otimes \ket{x_n} \otimes \ket{y \oplus f(x)}$$

Where $x_i$ means, the i-th bit of $x$.

In circuit form this looks like:

Show solution