The DJ Circuit

The Deutsch-Jozsa (DJ) algorithm was proposed by David Deutsch and Richard Jozsa in 1992. It was the first algorithm that showed us the true power of quantum computing because it gave an exponential speedup to our fastest classical solution for a certain problem. Let’s see how it did that by first understanding the problem itself.

Defining the problem

At the heart of the Deutsch-Jozsa algorithm is a mathematical function. That function takes in as an input a bit-string of $n$ bits and returns a single bit as an output, $0$ or $1$ based on the type of the function itself. This function can be one of two types - balanced or constant. When the function is constant, it will return either a $0$ or a $1$ for all inputs. However, if the function is balanced, it outputs a mixture of $0$ and $1$. That mixture is special. For exactly half of all inputs, that function will return $0$, and for the other half, it will return $1$. Hence the name, balanced, signifying a balance in the type of outputs. Mathematically, we can write this function as:

$$f\{0,1\}^{n}\rightarrow\{0,1\}$$

For clarity, let’s look at the truth table for this type of function. When the function is constant, for a 2-bit input, it will have the following truth table. We assume that we’ve chosen this function to output $0$s for all inputs. We could’ve chosen $1$s too.

Input	Output
00	0
01	0
10	0
11	0

When the function is balanced, for a 2-bit input, it will have the following truth table.

Input	Output
00	0
01	1
10	1
11	0

The order of $0$s and $1$s do not matter. What matters is that the number of times we get either output should be identical, $50\%$.

So now the question that Deutsch and Jozsa posed with this function is as follows:

• Determine whether the function $f$ is constant or balanced as efficiently as possible.

For this investigation, we will be provided this function $f$ as a black-box. We won’t be able to look into it, but we can give it bit strings in input and read its output bit.

At this point, try to think about how you would go about solving this problem classically. What would be the time complexity of the solution? Can you do any better than the solution you proposed?