préambule
représentations
algorithmes quantiques
Deutsch-Jozsa Simon Shor (Grover)
information quantique
perspectives
|
|
|
Deutsch-Jozsa
|
|
|
1. Soit une fonction quelconque sur {0,1}. Est-elle constante ou pas ?
En classique, pour répondre de manière certaine à cette question, il faut effectuer deux mesures : f(0) et f(1).
Grâce au premier algorithme quantique, l'algorithme de Deutsch, il est possible d'obtenir la réponse avec 100% de chance, en une seule mesure.
L'outil auquel vous pouvez accéder en cliquant sur l'image ci-contre vous permet de visualiser l'algorithme de Deutsch, en choisissant 1 dans la liste déroulante,
puis en sélectionnant une fonction.
Nota : On suppose que les principes de l'algorithme sont connus. Pour plus de détails, cf. la fin de cette page.
L'algorithme de Deutsch-Jozsa généralise le problème précédent.
2. Soit une fonction de {0,1}n dans {0,1}, contante ou balancée (c'est-à-dire dont l'image contient autant de 0 que de 1).
Est-elle constante ou pas ?
Grâce à l'algorithme de Deutsch-Jozsa, il est possible d'obtenir la réponse avec 100% de chance, en une seule mesure.
Dans l'outil ci-contre, il vous suffit de choisir 2 ou 3 dans la liste déroulante, pour visualiser les exemples de cet algorithme avec n=2 ou n=3.
|
|
|
3. Le mode de représentation de l'outil est graphique. Est-il possible d'avoir un équivalent sous forme de script ?
Nous avons imaginé qu'il était possible de faire coexister les deux modes de programmation :
- Un mode fonctionnel (script) pour écrire les bases des algorithmes
- Un mode graphique pour les tester et les affiner.
La bascule se ferait via des cases à cocher telles que celles qui figurent en bas à gauche de l'écran.
Les scripts que vous voyez dans l'outil actuel sont une piste de réflexion : nous avons délibérément mis de côté le détail des classes et leur constructeur.
C'est pourquoi le style ressemble plus à du javascript qu'à du java.
Nous avons juste mis en évidence deux nécessités :
- celle de disposer d'au moins une nouvelle structure de données : la classe quBit.
- celle de disposer d'au moins une nouvelle structure de contrôle : l'instruction parallel_for, dont la syntaxe serait parallel_for(i = 0;i < n)
Pour plus de détails sur l'algorithme de Deutsch Jozsa :
http://www.lri.fr/~kempe/, rubrique "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
|
|