 preamble
representations
 quantum algorithms
 Deutsch-Jozsa
 Simon
Shor
(Grover)
quantum information
prospects
|
|
|
|
Simon
|
|
|
|
The input to the problem is a function (implemented by a black box)
f:{0,1}n → {0,1}n,
promised to satisfy the property that for some s in {0,1}n we have for all y, z in {0,1}n,
f(y) = f(z) if and only if
y = z or y ⊕ z =s.
Note that the case of s = 0n is allowed, and corresponds to f being a permutation.
The query complexity is lower in the case of Simon's algorithm than with a probabilistic algorithm.
You can click on the image that allows you to see Simon's algorithm. By choosing n in the combobox and then selecting a function.
Each time you click on the checkbox representing the first measure, you will get a new equation.
If you already have gotten it, it is not rewritten, but the numbers of clicks are recorded.
Note: It implied that you know the principles of this algorithm.
For more details, cf. the end of this page.
Entanglement
In order to see the quantum entanglement, you only need to rollover the registers before the checkbox :
- Each state of the register above matches to a state of the register below.
- Each state of the register below matches to the two states of the register-above (the one that you get when you measure).
Note: from n=4, a scrollbar is necessary to see all the registers.
The ergonomic problem that appears here will become very important in the Shor's algorithm...
|
|
|
For more details on Simon algorithm:
http://www.lri.fr/~kempe/, "Presentations, lecture 2".
http://www.lri.fr/~magniez/teaching/quantum-X07-3.pdf
http://www.cqed.org/college/2002/SHCdF2002-8.pdf
http://www.cqed.org/college/lyon2007/Lyon.college.1.2007.pdf
|
|
