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 bits and returns a single bit as an output, or 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 or a for all inputs. However, if the function is balanced, it outputs a mixture of and . That mixture is special. For exactly half of all inputs, that function will return , and for the other half, it will return . 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 s for all inputs. We could’ve chosen 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 s and s do not matter. What matters is that the number of times we get either output should be identical, .
So now the question that Deutsch and Jozsa posed with this function is as follows:
- Determine whether the function is constant or balanced as efficiently as possible.
For this investigation, we will be provided this function 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.