5.2.3 Deutsch-Jozsa algorithm

Are the above observations useful for anything? Yes, they are! Suppose f:{0,1}n{0,1}f\colon\{0,1\}^{n}\to\{0,1\} 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 ff (i.e., one application of OfO_{f}).

This algorithm is called the Deutsch-Jozsa algorithm, and it works in five simple steps:

  1. 1.

    Start with |00\left|0\dots 0\right\rangle.

  2. 2.

    Apply the Hadamard transform HHH\otimes\dotsb\otimes H.

  3. 3.

    Apply the sign oracle OfO_{f} corresponding to the function ff.

  4. 4.

    Apply the Hadamard transform HHH\otimes\dotsb\otimes H again.

  5. 5.

    Measure all qubits. If all outcomes are zero, the function ff 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 ff at least 2n2+1\frac{2^{n}}{2}+1 times in the worst case. Indeed, suppose that we learn the function on half of the input bitstrings (i.e., on 2n/22^{n}/2 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 2n/22^{n}/2 questions and still have not learned anything useful. To be certain whether ff is constant or balanced, we need to evaluate it on one more input. In total, this amounts to 2n2+1\frac{2^{n}}{2}+1 evaluations of ff, compared to 11 evaluation in the quantum case. Note that even for moderate values such as n=100n=100 this difference is so dramatic that you would not be able to evaluate ff 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 f:{0,1}n{0,1}f\colon\{0,1\}^{n}\to\{0,1\} is a function that is either constant or balanced then the Deutsch-Jozsa algorithm can determine using only one evaluation of ff which of the two is the case. This is exponentially better than any classical algorithm, which needs to evaluate the function on 2n2+1\frac{2^{n}}{2}+1 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.

Hack.

We add measurements and a suitably resized probability display:

[Uncaptioned image]

Since the probability of outcome [00][0\dots 0] is zero, the function is not constant. Thus it must be balanced.