The DJ Circuit

Let’s dive into the Deutsch-Jozsa algorithm that works in constant time and is exponentially faster than our fastest classical solution.

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 nn bits and returns a single bit as an output, 00 or 11 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 00 or a 11 for all inputs. However, if the function is balanced, it outputs a mixture of 00 and 11. That mixture is special. For exactly half of all inputs, that function will return 00, and for the other half, it will return 11. Hence the name, balanced, signifying a balance in the type of outputs. Mathematically, we can write this function as:


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 00s for all inputs. We could’ve chosen 11s 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 00s and 11s do not matter. What matters is that the number of times we get either output should be identical, 50%50\%.

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

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

For this investigation, we will be provided this function ff 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?

Get hands-on with 1200+ tech skills courses.