Deutsch-Jozsa algorithm¶

The Deutsch-Jozsa algorithm was the first to show a separation between the quantum and classical difficulty of a problem. This algorithm demonstrates the significance of allowing quantum amplitudes to take both positive and negative values, as opposed to classical probabilities that are always non-negative.

The Deutsch-Jozsa problem is defined as follows. Consider a function that takes as input -bit strings and returns or . Suppose we are promised that is either a constant function that takes the same value on all inputs , or a balanced function that takes each value and on exactly half of the inputs. The goal is to decide whether is constant or balanced by making as few function evaluations as possible. Classically, it requires function evaluations in the worst case. Using the Deutsch-Jozsa algorithm, the question can be answered with just one function evaluation. In the quantum world, the function is specified by an oracle circuit , such that (see the previous section on Grover’s algorithm). To understand how the Deutsch-Jozsa algorithm works, let us first consider a typical interference experiment: a particle that behaves like a wave, such as a photon, can travel from the source to an array of detectors by following two or more paths simultaneously. The probability of observing the particle will be concentrated at those detectors where most of the incoming waves arrive with the same phase.

Imagine that we can set up an interference experiment as above, with detectors and possible paths from the source to each of the detectors. We shall label the paths and the detectors with -bit strings and , respectively.

Suppose further that the phase accumulated along a path to a detector equals , where is the binary inner product and is a normalizing coefficient. The probability to observe the particle at a detector can be computed by summing up amplitudes of all paths arriving at and taking the absolute value squared:

Normalization condition then gives .

Let us compute the probability of observing the particle at the detector (all-zeros string). We have . If is a constant function, we get . However, if is a balanced function, we get , since all the terms in the sum over cancel each other out. We can therefore determine whether is constant or balanced with certainty by running the experiment just once. Of course, this experiment is not practical since it would require an impossibly large optical table! However, we can simulate this experiment on a quantum computer with just qubits and access to the oracle circuit . Indeed, consider the following algorithm:

Step 1. Initialize qubits in the all-zeros state .

Step 2. Apply the Hadamard gate to each qubit.

Step 3. Apply the oracle circuit .

Step 4. Repeat Step 2.

Step 5. Measure each qubit. Let be the list of measurement outcomes. We find that is a constant function if is the all-zeros string.

Why does this work? Recall that the Hadamard gate maps to the uniform superposition of and . Thus, the state reached after Step 2 is , where the sum runs over all -bit strings. The oracle circuit maps this state to .

Finally, let us apply the layer of Hadamards at Step 4. It maps a basis state to a superposition . Thus, the state reached after Step 4 is , where . This is exactly what we need for the interference experiment described above.

The final measurement at Step 5 plays the role of detecting the particle. As was shown above, the probability to measure at Step 5 is if is a constant function, and if is a balanced function. Thus, we have solved the Deutsch-Jozsa problem with certainty by making just one function evaluation.