Deutsch-Jozsa algorithm

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.cite journal
author = David Deutsch and Richard Jozsa
title = Rapid solutions of problems by quantum computation
journal = Proceedings of the Royal Society of London A
volume = 439
pages = 553
date = 1992
] cite journal
author = R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca
title = Quantum algorithms revisited
journal = Proceedings of the Royal Society of London A
volume = 454
pages = 339–354
date = 1998
url = http://arxiv.org/pdf/quant-ph/9708016
format = PDF
] 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.

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 (and in best case need only 2 queries, if the function is 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 epsilon≤1/2k-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.

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.cite journal
author = David Deutsch
title = The Church-Turing principle and the universal quantum computer
journal = Proceedings of the Royal Society of London A
volume = 400
pages = 97
date = 1985
url =http://coblitz.codeen.org:3125/citeseer.ist.psu.edu/cache/papers/cs/13701/http:zSzzSzwww.qubit.orgzSzresourcezSzdeutsch85.pdf/deutsch85quantum.pdf
format =PDF
]

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.cite journal
author = Lov K. Grover
title = A fast quantum mechanical algorithm for database search
journal = Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing
pages = 212–219
date = 1996
url =http://arxiv.org/pdf/quant-ph/9605043
format =PDF
] cite journal
author = Peter W. Shor
title = Algorithms for Quantum Computation: Discrete Logarithms and Factoring
journal = IEEE Symposium on Foundations of Computer Science
pages = 124–134
date = 1994
url = http://citeseer.ist.psu.edu/cache/papers/cs/408/http:zSzzSzwww.research.att.comzSz%7EshorzSzpaperszSzQCalgs.pdf/algorithms-for-quantum-computation.pdf
format =PDF
]

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) (where oplus is addition modulo 2), if zero, then f is constant, otherwise f is not constant.

We begin with a two qubit in the state |0 angle |1 angle and apply a Hadamard transform to each qubit. This yields:frac{1}{2}(|0 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:frac{1}{2}(|0 angle(|f(0)oplus 0 angle - |f(0)oplus 1 angle) + |1 angle(|f(1)oplus 0 angle - |f(1)oplus 1 angle)):=frac{1}{2}((-1)^{f(0)}|0 angle(|0 angle - |1 angle) + (-1)^{f(1)}|1 angle(|0 angle - |1 angle)):=(-1)^{f(0)}frac{1}{2}(|0 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:frac{1}{sqrt{2(|0 angle + (-1)^{f(0)oplus f(1)}|1 angle).

Applying a hadamard transform to this state we have:frac{1}{2}(|0 angle + |1 angle + (-1)^{f(0)oplus f(1)}|0 angle - (-1)^{f(0)oplus f(1)}|1 angle):=frac{1}{2}((1 +(-1)^{f(0)oplus f(1)})|0 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

:frac{1}{sqrt{2^{n+1}sum_{x=0}^{2^n-1} |x 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

:frac{1}{sqrt{2^{n+1}sum_{x=0}^{2^n-1} |x angle (|f(x) angle - |1oplus f(x) angle ).

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 angle (|0 angle - |1 angle ).

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)^{xcdot y} |y angle=frac{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=x_0 y_0oplus x_1 y_1opluscdotsoplus x_{n-1} y_{n-1} is the sum of the bitwise product.

Finally we examine the probability of measuring |0 angle^{otimes n},

:igg|frac{1}{2^n}sum_{x=0}^{2^n-1}(-1)^{f(x)}igg|^2

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

References

External links

* [http://www.quiprocone.org/Protected/Lecture_5.htm Deutsch's lecture about Deutsch algorithm]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Deutsch–Jozsa algorithm — The Deutsch–Jozsa algorithm is a quantum algorithm, proposed by David Deutsch and Richard Jozsa in 1992[1] with improvements by Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca in 1998.[2] Although it is of little practical use …   Wikipedia

  • Deutsch-Jozsa-Algorithmus — Der Algorithmus von Deutsch ist ein Algorithmus für Quantencomputer, mit dem man bestimmen kann, ob eine auf einem Bit operierende Funktion konstant oder balanciert ist. Diese Aufgabenstellung ist unter dem Namen Problem von Deutsch bekannt. Der… …   Deutsch Wikipedia

  • Algorithme de Deutsch-Jozsa — L Algorithme de Deutsch Jozsa est un algorithme quantique, proposé par David Deutsch et Richard Jozsa en 1992 avec des améliorations de R. Cleve, A. Ekert, C. Macchiavello, et M. Mosca en 1998[1],[2]. Bien qu il ne soit pas d un grand intérêt… …   Wikipédia en Français

  • David Deutsch — Born 1953 (age 58) Haifa, Israel Fields Theoretical physics Quantum information science …   Wikipedia

  • Richard Jozsa — Infobox Scientist image width = 150px name = Richard Jozsa birth date = birth place = death date = death place = residence = UK nationality = Australia field = Computer scientist, Mathematics work institutions = University of BristolUniversity of …   Wikipedia

  • Grover's algorithm — is a quantum algorithm for searching an unsorted database with N entries in O(N1/2) time and using O( log N) storage space (see big O notation). It was invented by Lov Grover in 1996.Classically, searching an unsorted database requires a linear… …   Wikipedia

  • Quantum algorithm — Algorithms for a quantum computer.* Shor s algorithm * Deutsch Jozsa algorithm * Grover s algorithm * Simon s algorithm …   Wikipedia

  • Timeline of algorithms — The following timeline outlines the development of algorithms (mainly mathematical recipes ) since their inception.Before Modern Era* Before Writing about recipes (on cooking, rituals, agriculture and other themes) * c. 1600 BC Babylonians… …   Wikipedia

  • Timeline of mathematics — A timeline of pure and applied mathematics history. Contents 1 Before 1000 BC 2 1st millennium BC 3 1st millennium AD 4 1000–1500 …   Wikipedia

  • Quantenprozessor — Ein Quantencomputer bzw. Quantenrechner ist ein Computer, dessen Funktion auf den besonderen Gesetzen der Quantenmechanik beruht. Im Unterschied zum Digitalrechner arbeitet er auf der Basis quantenmechanischer Zustände, und die Verarbeitung… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”