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 f(x) that takes as input n -bit strings x and returns 0 or 1 . Suppose we are promised that f(x) is either a constant function that takes the same value c\in \{0,1\} on all inputs x , or a balanced function that takes each value 0 and 1 on exactly half of the inputs. The goal is to decide whether f is constant or balanced by making as few function evaluations as possible. Classically, it requires 2^{n-1}+1 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 f is specified by an oracle circuit U_f , such that U_f |x\rangle =(-1)^{f(x)} |x\rangle (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.

image0

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

Suppose further that the phase accumulated along a path x to a detector y equals C(-1)^{f(x)+x\cdot y} , where x\cdot y=\sum_{i=1}^n x_i y_i is the binary inner product and C is a normalizing coefficient. The probability to observe the particle at a detector y can be computed by summing up amplitudes of all paths x arriving at y and taking the absolute value squared:

\mathrm{Pr}(y)=| C\sum_x (-1)^{f(x)+x\cdot y} |^2

Normalization condition \sum_y \mathrm{Pr}(y)=1 then gives C=2^{-n} .

Let us compute the probability \mathrm{Pr}(y=0^n) of observing the particle at the detector y=0^n (all-zeros string). We have  \mathrm{Pr}(y=0^n)=| 2^{-n}\sum_x (-1)^{f(x)}|^2 . If f(x)=c is a constant function, we get \mathrm{Pr}(y=0^n)=|(-1)^c |^2 =1 . However, if f(x) is a balanced function, we get \mathrm{Pr}(y=0^n)=0 , since all the terms in the sum over x cancel each other out. We can therefore determine whether f 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 n qubits and access to the oracle circuit U_f . Indeed, consider the following algorithm:

Step 1. Initialize n qubits in the all-zeros state |0,\ldots,0\rangle .

Step 2. Apply the Hadamard gate H to each qubit.

Step 3. Apply the oracle circuit U_f .

Step 4. Repeat Step 2.

Step 5. Measure each qubit. Let y=(y_1,\ldots,y_n) be the list of measurement outcomes. We find that f is a constant function if y is the all-zeros string.

Why does this work? Recall that the Hadamard gate H maps |0\rangle to the uniform superposition of |0\rangle and |1\rangle . Thus, the state reached after Step 2 is 2^{-n/2}\sum_x |x\rangle , where the sum runs over all n -bit strings. The oracle circuit maps this state to 2^{-n/2} \sum_x (-1)^{f(x)} |x\rangle .

Finally, let us apply the layer of Hadamards at Step 4. It maps a basis state |x\rangle to a superposition 2^{-n/2}\sum_y (-1)^{x\cdot y} |y\rangle . Thus, the state reached after Step 4 is |\psi\rangle =\sum_y \psi(y)|y\rangle , where \psi(y)=2^{-n}\sum_x (-1)^{f(x)+x\cdot y} . 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 y=0^n at Step 5 is 1 if f is a constant function, and 0 if f is a balanced function. Thus, we have solved the Deutsch-Jozsa problem with certainty by making just one function evaluation.

Example circuits

Suppose n=3 and f(x)=x_0 \oplus x_1 x_2 . This function is balanced since flipping the bit x_0 flips the value of f(x) regardless of x_1,x_2 . To run the Deutsch-Jozsa algorithm, we need an explicit description of the oracle circuit U_f as a sequence of quantum gates. To this end we need a Z_0 gate such that Z_0|x\rangle =(-1)^{x_0} |x\rangle and a controlled-Z gate CZ_{1,2} such that CZ_{1,2} |x\rangle =(-1)^{x_1x_2} |x\rangle .  Using the lessons learned from rotating states between z- and x-measurement bases (see the Advanced single-qubit gates section), one can realize the controlled-Z gate as a CNOT sandwiched between two Hadamard gates.

DJ N=3 Example

image1

Open in IBM Quantum Composer


DJ N=3 Constant

image2

Open in IBM Quantum Composer