5.2.3 Deutsch-Jozsa algorithm
Are the above observations useful for anything? Yes, they are! Suppose is an unknown function which is either constant or balanced. Then there is a simple quantum algorithm which can determine which of these two is the case, by using only a single evaluation of (i.e., one application of ).
This algorithm is called the Deutsch-Jozsa algorithm, and it works in five simple steps:
-
1.
Start with .
-
2.
Apply the Hadamard transform .
-
3.
Apply the sign oracle corresponding to the function .
-
4.
Apply the Hadamard transform again.
-
5.
Measure all qubits. If all outcomes are zero, the function must be constant. Otherwise it must be balanced.
To see how this compares with classical algorithms, notice that any classical algorithm needs to evaluate the function at least times in the worst case. Indeed, suppose that we learn the function on half of the input bitstrings (i.e., on inputs) and we get the same answer every time. Then we still cannot conclude that the function is constant, since it could be the case that the function gives the opposite answer on the remaining half of the input bitstrings while still being balanced. Hence this is the worst case scenario. In this scenario, we have wasted questions and still have not learned anything useful. To be certain whether is constant or balanced, we need to evaluate it on one more input. In total, this amounts to evaluations of , compared to evaluation in the quantum case. Note that even for moderate values such as this difference is so dramatic that you would not be able to evaluate so many times in any reasonable amount of time (indeed, by that time the sun would run out of fuel and you would have to relocate to another solar system).
To summarize: If is a function that is either constant or balanced then the Deutsch-Jozsa algorithm can determine using only one evaluation of which of the two is the case. This is exponentially better than any classical algorithm, which needs to evaluate the function on many inputs in the worst case.
Homework 5.2 (Run Deutsch-Jozsa).
The yellow Oracle box in Quirky implements the sign oracle for a function that is either constant or balanced. Implement the Deutsch-Jozsa algorithm in Quirky and use it to determine which of the two is the case.