 preamble
representations
 quantum algorithms
 Deutsch-Jozsa
 Simon
Shor
(Grover)
quantum information
prospects
|
|
|
|
Deutsch-Jozsa
|
|
|
|
1. Let f be a Boolean function on {0,1}. Is it constant ?
In a classical way, to determine with certainty whether f is constant, we need two measures: f(0) et f(1).
Thanks to the first quantum algorithm, the Deutsch one, it is possible to get the result with 100% accuracy in only one measure.
The proposed tool can be opened by clicking on the image beside it. This allows you to see the Deutsch algorithm by choosing 1 in the combo-box, and then a function.
Note: It is implied that you know the principles of this algorithm.
For more details, cf. the end of this page.
Deutsch-Jozsa algorithm generalizes the previous problem.
2. Let f be a function from {0,1}n to {0,1}.
f is either a constant function (f(x) = 0 for all x or f(x) = 1 for all x)
or a "balanced" function in the sense that f(x) = 0 resp. 1 for exactly half of the 2n
inputs x.
Thanks to the Deutsch-Jozsa algorithm, just one query suffices (with O(n) extra processing steps) in every case.
In our tool, you can choose 2 or 3 in the combo to see examples with n=2 or n=3.
|
|
|
3. The previous representation of the algorithms is graphical. Is it possible to write them with scripts ?
We imagined it could be possible to have these two kinds of representation at the same time:
- scripts to write the basis of the algorithms.
- a graphical mode to test and adapt them.
The trig between the two could be put through checkboxes, like the one in the left-bottom side of the screen.
The example you see in the scripts are a food for thought (piste de réflexion): we put aside details of classes and their constructor.
It is for this reason the style looks like Javascript rather than java.
We only highlighted two needs:
- have at least one new data structure: the class quBit.
- have at least one new control structure: parallel_for, whose syntax could be
parallel_for(i = 0;i < n)
For more details on Deutsch-Jozsa algorithm:
http://www.lri.fr/~kempe/, "Presentations, lecture 2".
http://www.cs.uwaterloo.ca/~watrous/lecture-notes/519/05.pdf
http://perso.ens-lyon.fr/guilhem.jaber/TIPE/Rapport-TIPE.pdf
http://www.cqed.org/college/2002/SHCdF2002-8.pdf
|
|
