Deutsch–Jozsa algorithm

In the Deutsch–Jozsa problem, we are given a black box quantum computer known as an oracle that implements some function ${\displaystyle f\colon \{0,1\}^{n}\rightarrow \{0,1\}}$. The function takes n-digit binary values as input and produces either a 0 or a 1 as output for each such value. We are promised that the function is either constant (0 on all outputs or 1 on all outputs) or balanced (returns 1 for half of the input domain and 0 for the other half).[4] The task then is to determine if ${\displaystyle f}$ is constant or balanced by using the oracle.

The Deutsch–Jozsa problem is specifically designed to be easy for a quantum algorithm and hard for any deterministic classical algorithm. The motivation is to show a black box problem that can be solved efficiently by a quantum computer with no error, whereas a deterministic classical computer would need a large number of queries to the black box to solve the problem. More formally, it yields an oracle relative to which EQP, the class of problems that can be solved exactly in polynomial time on a quantum computer, and P are different.[5]

Since the problem is easy to solve on a probabilistic classical computer, it does not yield an oracle separation with BPP, the class of problems that can be solved with bounded error in polynomial time on a probabilistic classical computer. Simon's problem is an example of a problem that yields an oracle separation between BQP and BPP.

For a conventional deterministic algorithm where n is number of bits, ${\displaystyle 2^{n-1}+1}$ evaluations of ${\displaystyle f}$ will be required in the worst case. To prove that ${\displaystyle f}$ is constant, just over half the set of inputs must be evaluated and their outputs found to be identical (remembering that the function is guaranteed to be either balanced or constant, not somewhere in between). The best case occurs where the function is balanced and the first two output values that happen to be selected are different. For a conventional randomized algorithm, a constant ${\displaystyle k}$ evaluations of the function suffices to produce the correct answer with a high probability (failing with probability ${\displaystyle \epsilon \leq 1/2^{k}}$ with ${\displaystyle k\geq 1}$). However, ${\displaystyle k=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 ${\displaystyle f}$.

The Deutsch–Jozsa Algorithm generalizes earlier (1985) work by David Deutsch, which provided a solution for the simple case where ${\displaystyle n=1}$.
Specifically we were given a boolean function whose input is 1 bit, ${\displaystyle f:\{0,1\}\rightarrow \{0,1\}}$ and asked if it is constant.[6]

The algorithm as Deutsch had originally proposed it was not, in fact, deterministic. The algorithm was successful with a probability of one half. In 1992, Deutsch and Jozsa produced a deterministic algorithm which was generalized to a function which takes ${\displaystyle n}$ bits for its input. Unlike Deutsch's Algorithm, this algorithm required two function evaluations instead of only one.

Further improvements to the Deutsch–Jozsa algorithm were made by Cleve et al.,[2] resulting in an algorithm that is both deterministic and requires only a single query of ${\displaystyle f}$. This algorithm is still referred to as Deutsch–Jozsa algorithm in honour of the groundbreaking techniques they employed.[2]

For the Deutsch–Jozsa algorithm to work, the oracle computing ${\displaystyle f(x)}$ from ${\displaystyle x}$ has to be a quantum oracle which doesn't decohere ${\displaystyle x}$. It also mustn't leave any copy of ${\displaystyle x}$ lying around at the end of the oracle call.

Deutsch-Jozsa algorithm quantum circuit

The algorithm begins with the ${\displaystyle n+1}$ bit state ${\displaystyle |0\rangle ^{\otimes n}|1\rangle }$. That is, the first n bits are each in the state ${\displaystyle |0\rangle }$ and the final bit is ${\displaystyle |1\rangle }$. A Hadamard transform is applied to each bit to obtain the state

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

We have the function ${\displaystyle f}$ implemented as a quantum oracle. The oracle maps the state ${\displaystyle |x\rangle |y\rangle }$ to ${\displaystyle |x\rangle |y\oplus f(x)\rangle }$, where ${\displaystyle \oplus }$ is addition modulo 2 (see below for details of implementation). Applying the quantum oracle gives

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

For each ${\displaystyle x,f(x)}$ is either 0 or 1. Testing these two possibilities, we see the above state is equal to

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

At this point the last qubit ${\displaystyle {\frac {|0\rangle -|1\rangle }{\sqrt {2}}}}$ may be ignored and therefore below is remained:

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

We apply a Hadamard transform to each qubit to obtain

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

where ${\displaystyle x\cdot y=x_{0}y_{0}\oplus x_{1}y_{1}\oplus \cdots \oplus x_{n-1}y_{n-1}}$ is the sum of the bitwise product.

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

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

which evaluates to 1 if ${\displaystyle f(x)}$ is constant (constructive interference) and 0 if ${\displaystyle f(x)}$ is balanced (destructive interference). In other words, the final measurement will be ${\displaystyle |0\rangle ^{\otimes n}}$ (i.e. all zeros) if ${\displaystyle f(x)}$ is constant and will yield some other states if ${\displaystyle f(x)}$ is balanced.

Deutsch's algorithm is a special case of the general Deutsch–Jozsa algorithm. We need to check the condition ${\displaystyle f(0)=f(1)}$. It is equivalent to check ${\displaystyle f(0)\oplus f(1)}$ (where ${\displaystyle \oplus }$ is addition modulo 2, which can also be viewed as a quantum XOR gate implemented as a Controlled NOT gate), if zero, then ${\displaystyle f}$ is constant, otherwise ${\displaystyle f}$ is not constant.

We begin with the two-qubit state ${\displaystyle |0\rangle |1\rangle }$ and apply a Hadamard transform to each qubit. This yields

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

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

${\displaystyle {\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 ))}$

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

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

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

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

Applying a Hadamard transform to this state we have

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

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

${\displaystyle f(0)\oplus f(1)=0}$ if and only if we measure ${\displaystyle |0\rangle }$ and ${\displaystyle f(0)\oplus f(1)=1}$ if and only if we measure ${\displaystyle |1\rangle }$. So with certainty we know whether ${\displaystyle f(x)}$ is constant or balanced.

• Bernstein–Vazirani algorithm

• Deutsch's lecture about the Deutsch-Jozsa algorithm