This is the fourth post of a series of posts about Quantum Computing with Qiskit. The area is very new and the SDK is changing constantly, but hopefully, the series can help you learn a bit about quantum and help me reinforce a couple concepts.

The goal of this post is to discuss the Deutsch-Jozsa algorithm, which was one of the very first quantum algorithms. Even though it solves a very artificial problem, its main purpose is to answer: is there an advantage in using quantum computers? The answer is yes.

Deutsch problem

Before diving into the Deutsch-Jozsa algorithm, let’s discuss the Deutsch problem which is a special case solved by the algorithm. It is a problem that can be summarized as:

Imagine that you have a black box that implements a function \(f : \{0, 1 \} \rightarrow \{0, 1\}\). You can make a query to the black box with a value \(v\), and the black box will return \(f(v)\). How many queries are needed to decide if the function is constant or balanced? A balanced function is when the number of values that have \(f(v) = 0\) is equal to the number of values that have \(f(v) = 1\).

There are four possible \(f\) functions, all listed below:

It turns out that to classify the function implemented by the black box, we need to use two queries. When we do one query, we go from four possible functions to two functions, one which will be balanced and the other constant. Thus, we need an additional query to decide which one it is, totaling two queries.

From a perspective using classical computers, that is the best we can do. A question that arises is: can quantum computers do better? It can be shown yes, they can.

Quantum black box

Before we continue, it is important to discuss what a quantum black box is. It acts similarly to the classical black box we had before: it takes qubits and spits the result. Because the black box implements a function that might not have a unitary matrix and quantum circuits are composed only of unitary matrices, we need to use a working qubit to store the result of the black box.

Thus, we define the black box as a transformation \(|v\rangle|0\rangle \rightarrow |v\rangle|f(v)\rangle\), or even more detailed \(|v\rangle|w\rangle \rightarrow |v\rangle|w \oplus f(v)\rangle\) to handle the case with 1 (\(\oplus\) is the XOR operator).

An interesting aspect of the quantum black box is that it allows us to achieve something that would be impossible with a classical computer: ask \(f(0)\) and \(f(1)\) at the same time! How? Well, consider a state with a superposition such as \(\frac{(|0\rangle + |1\rangle)}{\sqrt 2}\). If we give that qubit to the black box, a part of our working qubit will have \(f(0)\) and the other will have \(f(1)\). Maybe then, we can find a clever way to recover both at the same time and classify the function with only one query!

One concern that might come now: is it even fair to compare a quantum black box to a classical black box? The answer is: it is reasonable. Even with a quantum black box, classical computers still need 2 queries because they cannot exploit superpositions, hence it is reasonable to compare.

Exploiting superposition

Now that we know that we need to use superposition in our solution, it is tempting to use a circuit like the following:

In this circuit, we generate a superposition, then apply the black box and after we measure our result. It is a very simple circuit and the core ideas of the real solution are on it. Even though it seems promising, it fails. It cannot differentiate balanced functions.

To understand why, consider the case for constant. If the value is always 0, our measure for the qubit will also be always zero. If it is 1, similarly, it will always be one. But for balanced, we have 50% for each case so in practice we cannot differentiate constant and balanced functions.

We could try to measure the balanced case by, let’s say, applying a Hadamard gate :

This solves the problem for balanced functions: now, due to the Hadamard gate, they will always output the same measurement 100% of the time. But our constant functions will now measure 50% of the times 0 and 50% of the times 1, so we still have the same problem as before. We need a more elaborate solution.

Deutsch algorithm

We will now analyze the circuit that the following circuit solves the problem:

To understand why, we can expand the algebra of the circuit. We have the following state after applying the \(X\) and Hadamard gates:

\[ |\psi\rangle = \frac{|0\rangle + |1\rangle}{\sqrt 2} \otimes \frac{|0\rangle - |1\rangle}{\sqrt 2} \]

After applying the black box, we obtain:

\[ \rightarrow \frac{|0\rangle (|0 \oplus f(0)\rangle - |1 \oplus f(0)\rangle)}{2} + \frac{|1\rangle (|0 \oplus f(1)\rangle - |1 \oplus f(1)\rangle)}{2} \]

We are then going to use the following identity to help rewrite our expression in a convenient way:

\[ |0 \oplus a \rangle - |1 \oplus a \rangle = (-1)^{a}(|0\rangle - |1\rangle) \]

We can verify that the expression is valid when \(a\) is 0 or 1. Therefore, we get:

\[ \rightarrow \frac{(-1)^{f(0)}|0\rangle (|0\rangle - |1\rangle)}{2} + \frac{(-1)^{f(1)}|1\rangle (|0\rangle - |1\rangle)}{2} \]

\[ \rightarrow \frac{(-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle}{\sqrt 2} \otimes \frac{|0\rangle - |1\rangle}{\sqrt 2} \]

This form is convenient because it tells us two things. The first is that the second qubit does not change, so measuring it is useless. The second is that the first qubit depends on the classification of the function:

• If \(f\) is constant, the qubit will be \((\pm 1)\frac{|0\rangle + |1\rangle}{\sqrt 2}\). Because having a minus sign does not matter (it is a global phase change), we can say that the qubit will always be \(\frac{|0\rangle + |1\rangle}{\sqrt 2}\)
• If \(f\) is balanced, the qubit will be \((\pm 1)\frac{|0\rangle - |1\rangle}{\sqrt 2}\). Because having a minus sign does not matter (it is a global phase change), we can say that the qubit will always be \(\frac{|0\rangle - |1\rangle}{\sqrt 2}\)

To differentiate between \(\frac{|0\rangle + |1\rangle}{\sqrt 2}\) and \(\frac{|0\rangle - |1\rangle}{\sqrt 2}\), we need to apply a Hadamard gate. The first case will become a \(|0\rangle\) and the second case will become \(|1\rangle\), so using the circuit we presented before we can decide using the rule:

• If the measurement of the first qubit is \(0\), we have a constant function
• Otherwise, if the measurement of the qubit is \(1\), we have a balanced function

The problem has been solved! With just one query, an achievement that would be impossible with classical computers.

Implementing the Deutsch algorithm

We can verify that the Deutsch algorithm works using Qiskit and running an experiment: in the Jupyter notebook below, we try the four possible cases for the black box and verify that our algorithm predicts correctly that it is balanced or constant.

Next step

The next step is to generalize the problem from 1-bit functions to n-bit functions, and that is what will happen in the second part of the blog post about the Deutsch-Jozsa algorithm.