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