quantum design - algorithme de Simon

représentations

algorithmes quantiques

information quantique

perspectives

Simon


1. Soit une fonction {0,1}ⁿ dans {0,1}ⁿ telle que ∃s ∈ {0, 1}ⁿ : ∀x ≠ y, f(x) = f(y) ≡ y = x ⊕ s. Trouvez s. La complexité en requêtes est inférieure dans le cas de l'algorithme de Simon par rapport à un algorithme probabiliste. L'outil auquel vous pouvez accéder en cliquant sur l'image ci-contre vous permet de visualiser l'algorithme de Simon, en choisissant n dans la liste déroulante, puis en sélectionnant une fonction. Chaque fois que vous cliquerez sur la boîte à cocher de la première mesure, vous obtiendrez une nouvelle équation. Si vous l'aviez déjà obtenue précédemment, elle ne se ré-écrit pas, mais le nombre de clic est comptabilisé. Nota : On suppose que les principes de l'algorithme sont connus. Pour plus de détails, cf. ce qui suit. Intrication Pour visualiser l'intrication quantique, il suffit de faire un rollover avec la souris sur les registres avant la case à cocher-mesure : - A chaque état du registre du haut, correspond un état du registre du bas. - A chaque état du registre du bas, correspondent deux états du registre du haut : ceux qui subsistent après de la mesure. Nota : à partir de n=4, un ascenseur est nécessaire pour visualiser l'intégralité des registres. Le problème ergonomique qui commence à apparaître ici va être criant dans le cas de l'algorithme de Shor...

Pour plus de détails sur l'algorithme de Simon :

http://www.lri.fr/~kempe/, rubrique "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