Deutsch–Jozsa algorithm

The Deutsch-Jozsa algorithm is a quantum algorithm, proposed by David Deutsch and Richard Jozsa in 1992 with improvements by R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca in 1998.. Although it is of little practial use, it is one of first examples of a quantum algorithm that is more efficient than any possible classical algorithm.

The problem statement

In the Deutsch-Jozsa problem, we are given a black box quantum computer known as an oracle that implements the function $f:\{0,1\}^{n}\rightarrow \{0,1\}$. We know that the function is either constant (0 on all inputs or 1 on all inputs) or balanced (returns 1 for half of the input domain and 0 for the other half); the task then is to determine if $f$ constant or balanced by utilizing the oracle.

A classical solution

For a conventional deterministic algorithm, $2^{n-1}+1$ evaluations of $f$ will be required in the worst case. For a conventional randomized algorithm, a constant number of evaluation suffices to produce the correct answer with a high probability but $2^{n-1}+1$ evaluations are still required if we want an answer that is always correct. The Deutsch-Jozsa quantum algorithm produces an answer that is always correct with a single evaluation of $f$.

History

The algorithm builds on an earlier 1985 work by David Deutsch which provided a solution for the case $n=1$. Specifically we were given a boolean function $f\{0,1\}\rightarrow \{0,1\}$ and asked if it is constant.

In 1992 this idea was generalized to a function which takes $n$ bits for it's input and we are asked if it is constant or balanced.

Deutsch's Algorithm as he had originally proposed was not, in fact, deterministic. The algorithm was successful with a probability of one half. The original Deutsch-Jozsa algorithm was deterministic however unlike Deutsch's Algorithm it required two function evaluations instead of only one.

Futher improvements to the Deutsch-Jozsa algorithm were made by Cleve et al which resulted in an algorithm that is both deterministic and requires only a single query of $f$. This algorithm is refered to as Deutsch-Jozsa algorithm in honour of the groundbreaking techniques they employed.

The Deutsch-Jozsa algorithm provided insperation for Shor's algorithm and Grover's algorithm, two of the most revolutionary quantum algorithms.

Deutsch's Algorithm, a special case

We need to check the condition $f(0)=f(1)$. It is equivalent to check $f(0)\oplus f(1)$, if zero, then $f$ is constant, otherwise $f$ is not constant.

We begin with a two qubits in the state $|0\rangle |1\rangle$ and apply a Hadamard transform to each qubit. This yields

${\frac {1}{2}}(|0\rangle +|1\rangle )(|0\rangle -|1\rangle ).$

We are given a quantum implementation of the function $f$ which maps $|x\rangle |y\rangle$ to $|x\rangle |f(x)\oplus y\rangle$. Applying this function to our current state we obtain

${\frac {1}{2}}(|0\rangle (|f(0)\oplus 0\rangle -|f(0)\oplus 1\rangle )+|1\rangle (|f(1)\oplus 0\rangle -|f(1)\oplus 1\rangle ))$

$={\frac {1}{2}}((-1)^{f(0)}|0\rangle (|0\rangle -|1\rangle )+(-1)^{f(1)}|1\rangle (|0\rangle -|1\rangle ))$

$=(-1)^{f(0)}{\frac {1}{2}}(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle )(|0\rangle -|1\rangle ).$

We ignore the last bit and the global phase and therefore have the state

${\frac {1}{\sqrt {2}}}(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle ).$

Applying a haddamard transform to this state we have

${\frac {1}{2}}(|0\rangle +|1\rangle +(-1)^{f(0)\oplus f(1)}|0\rangle -(-1)^{f(0)\oplus f(1)}|1\rangle )$

$={\frac {1}{2}}((1+(-1)^{f(0)\oplus f(1)})|0\rangle +(1-(-1)^{f(0)\oplus f(1)})|1\rangle ).$

Obviously $f(0)\oplus f(1)=0$ if and only if we measure a zero. Therefore the function is constant if and only if we measure a zero.

The Deutsch-Jozsa Algorithm, in detail

We begin with the n+1 bit state $|0\rangle ^{\otimes n}|1\rangle$. That is, the first n bits are each in the state $|0\rangle$ and the final bit is $|1\rangle$. We apply a Hadamard transformation to each bit to obtain the state

${\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\rangle -|1\rangle )$.

We have the function $f$ implemented as quantum oracle. The oracle maps the state $|x\rangle |y\rangle$ to $|x\rangle |y\oplus f(x)\rangle$. Applying the quantum oracle gives us

${\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|f(x)\rangle -|1\oplus f(x)\rangle )$.

A quick check of the two possibilities for $f(x)$ yields

${\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle (|0\rangle -|1\rangle )$.

At this point we may ignore the last qubit. We apply a Hadamard transformation to each bit to obtain

${\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}\sum _{y=0}^{2^{n}-1}(-1)^{x\cdot y}|y\rangle ={\frac {1}{2^{n}}}\sum _{y=0}^{2^{n}-1}[\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x\cdot y}]|y\rangle$

where $x\cdot y$ is the bitwise sum modulo 2.

Finally we examine the probability of measuring $|0\rangle ^{\otimes n}$,

$|{\frac {1}{2^{n}}}[\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|^{2}$

which evaluates to 1 if $f(x)$ is constant and 0 if $f(x)$ is balanced.

References

See also [1] Deutsch's lecture about Deutsch algorithm.