Deutsch-Jozsa algorithm

From Wikipedia, the free encyclopedia

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 the first examples of a quantum algorithm that is more efficient than any possible classical algorithm.

1 The problem statement
2 A classical solution
3 History
4 Deutsch's Algorithm, a special case
5 The Deutsch-Jozsa Algorithm, in detail
6 References
7 External links

[edit] 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 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.

[edit] A classical solution

For a conventional deterministic algorithm, $2 n - 1 + 1$ evaluations of $f$ will be required in the worst case (and in best case need only 2 queries, if function balanced), where n is number of bits/qubits. For a conventional randomized algorithm, a constant $k$ evaluations of the function suffices to produce the correct answer with a high probability (failing with probability at most 1/ 2^k-1). However, $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 $f$ .

[edit] 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.^[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.^[1]

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.^[2]

The Deutsch-Jozsa algorithm provided inspiration for Shor's algorithm and Grover's algorithm, two of the most revolutionary quantum algorithms.^[4]^[5]

[edit] Deutsch's Algorithm, a special case

A quantum circuit of Deutsch's Algorithm

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 qubit 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 hadamard 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.

[edit] The Deutsch-Jozsa Algorithm, in detail

The Deutsch-Jozsa Algorithm's quantum circuit

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=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 $|0\rangle^{\otimes n}$ ,

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

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

[edit] References

^ ^a ^b David Deutsch and Richard Jozsa (1992). "Rapid solutions of problems by quantum computation". Proceedings of the Royal Society of London A 439: 553.
^ ^a ^b R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca (1998). "Quantum algorithms revisited" (PDF). Proceedings of the Royal Society of London A 454: 339-354.
^ David Deutsch (1985). "The Church-Turing principle and the universal quantum computer" (PDF). Proceedings of the Royal Society of London A 400: 97.
^ Lov K. Grover (1996). "A fast quantum mechanical algorithm for database search" (PDF). Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing: 212-219.
^ Peter W. Shor (1994). "Algorithms for Quantum Computation: Discrete Logarithms and Factoring" (PDF). IEEE Symposium on Foundations of Computer Science: 124-134.

[edit] External links

Deutsch's lecture about Deutsch algorithm

v • d • e Quantum computing

General	Qubit • Quantum computer • Quantum information • Quantum programming • Quantum virtual machine • Timeline of quantum computing

Quantum communication	Quantum channel • Quantum cryptography • Quantum teleportation • LOCC • Entanglement distillation

Quantum algorithms	Universal quantum simulator • Deutsch-Jozsa algorithm • Grover's search • Shor's factorization • Simon's Algorithm • (BQP)

Quantum computing models	Quantum circuit (quantum gate) • One-way quantum computer (cluster state) • Adiabatic quantum computation

Decoherence prevention	Quantum error correction • Topological quantum computer

Physical implementations

Quantum optics	Linear optics QC • Cavity QED

Ultracold atoms	Trapped ion quantum computer • Optical lattice

Spin-based	Nuclear magnetic resonance (NMR) quantum computing • Kane QC • Loss-DiVincenzo (quantum dot) QC

Other	Superconducting quantum computing (Charge qubit • Flux qubit) • Nitrogen-vacancy center

Categories: Quantum algorithms

Deutsch-Jozsa algorithm

From Wikipedia, the free encyclopedia

Contents

[edit] The problem statement

[edit] A classical solution

[edit] History

[edit] Deutsch's Algorithm, a special case

[edit] The Deutsch-Jozsa Algorithm, in detail

[edit] References

[edit] External links

Views

Navigation

Interaction

Search

Languages