Discover

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.^[1][2]. Although it is of little practical use, it is one of first examples of a quantum algorithm that is more efficient than any possible classical algorithm.

Contents

The problem statement

A classical solution

History

Deutsch's Algorithm, a special case

The Deutsch-Jozsa Algorithm, in detail

References

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$
ightarrow {0,1}. We are promised 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$ is 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\}$
ightarrow {0,1} and asked if it is constant.^[3]
In 1992 this idea was generalized to a function which takes $n$ bits for its 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.
Further 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 referred to as Deutsch-Jozsa algorithm in honour of the groundbreaking techniques they employed.²
The Deutsch-Jozsa algorithm provided inspiration for Shor's algorithm and Grover's algorithm, two of the most revolutionary quantum algorithms.^[4][5]

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$
angle |1
angle and apply a Hadamard transform to each qubit. This yields
:
angle + |1
angle)(|0
angle - |1
angle).
We are given a quantum implementation of the function $f$ which maps $|x$
angle |y
angle to $|x$
angle |f(x)oplus y
angle. Applying this function to our current state we obtain
:
angle(|f(0)oplus 0
angle - |f(0)oplus 1
angle) + |1
angle(|f(1)oplus 0
angle - |f(1)oplus 1
angle))
:
angle(|0
angle - |1
angle) + (-1)^{f(1)}|1
angle(|0
angle - |1
angle))
:
angle + (-1)^{f(0)oplus f(1)}|1
angle)(|0
angle - |1
angle).
We ignore the last bit and the global phase and therefore have the state
:
angle + (-1)^{f(0)oplus f(1)}|1
angle).
Applying a hadamard transform to this state we have
:
angle + |1
angle + (-1)^{f(0)oplus f(1)}|0
angle - (-1)^{f(0)oplus f(1)}|1
angle)
:
angle + (1-(-1)^{f(0)oplus f(1)})|1
angle).
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$
angle^{otimes n} |1
angle . That is, the first n bits are each in the state $|0$
angle and the final bit is $|1$
angle . We apply a Hadamard transformation to each bit to obtain the state
:
angle (|0
angle - |1
angle ).
We have the function $f$ implemented as quantum oracle. The oracle maps the state $|x$
angle|y
angle to $|x$
angle|yoplus f(x)
angle . Applying the quantum oracle gives us
:
angle (|f(x)
angle - |1oplus f(x)
angle ).
A quick check of the two possibilities for $f(x)$ yields
:
angle (|0
angle - |1
angle ).
At this point we may ignore the last qubit. We apply a Hadamard transformation to each bit to obtain
:
angle=
rac{1}{2^n}sum_{y=0}^{2^n-1} [sum_{x=0}^{2^n-1}(-1)^{f(x)} (-1)^{xcdot y}] |y
angle
where $xcdot\; y$ is the bitwise sum modulo 2.
Finally we examine the probability of measuring $|0$
angle^{otimes n},
:
which evaluates to 1 if $f(x)$ is constant and 0 if $f(x)$ is balanced.

References

1.
Rapid solutions of problems by quantum computation, David Deutsch and Richard Jozsa, , , Proceedings of the Royal Society of London A,

2.
Quantum algorithms revisited, R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca, , , Proceedings of the Royal Society of London A,

3.
The Church-Turing principle and the universal quantum computer, David Deutsch, , , Proceedings of the Royal Society of London A,

4.
A fast quantum mechanical algorithm for database search, Lov K. Grover, , , Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing,

5.
Algorithms for Quantum Computation: Discrete Logarithms and Factoring, Peter W. Shor, , , IEEE Symposium on Foundations of Computer Science,


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