Conclusion
Dans ce chapitre nous avons vu la représentation des
données quantique et comment on les manipule avec les portes quantiques
en fin on a vu la complexité des algorithmes quantiques.
CHAPITRE 3
LES ALGORITHMES QUANTIQUES
19
3.1 introduction :
Depuis le milieu des années 90 jusqu'à
présent l'effort principal a été porté à
trouver des algorithmes quantiques avec une performance meilleure que celle des
algorithmes classiques. L'algorithme quantique le plus important est
l'algorithme de Shor. L'importance de cet algorithme est qu'il indique que la
machine quantique peut être plus fondamentale que la machine classique.
Cet algorithme permet de résoudre en un temps polynomial un
problème que la machine classique n'a encore pu résoudre qu'avec
un temps exponentiel. D'autres raisons qui ont contribué à faire
de cet algorithme un algorithme très connu est d'une part que le
problème mathématique est simple à comprendre, le
problème de factorisation, et d'autre part que la solution de ce
problème a des implications importantes dans d'autres domaines comme la
cryptographie. Un autre algorithme important est celui de Grover, ou algorithme
de tri, nous allons présenter cet algorithme plus en détail dans
ce chapitre. L'algorithme classique décrivant le même
problème cependant n'est que quadratiquement supérieur en temps
que l'algorithme de Grover. Les applications de cet algorithme, comme par
exemple l'algorithme d'estimation d'amplitude auront le même type de gain
en temps par rapport à l'algorithme classique 'équivalent.
Finalement, dans les dernières années quelques algorithmes
utilisant comme base les marches quantiques ont 'été
construits.
3.2 Les problèmes posés sous forme d'une
boite noire :
Les problèmes logiques lesquelles considérer
ici [Haroche, 2002] sont posés sous forme d ' «oracle». On
suppose qu'une machine programmée selon des règles inconnues
(décrite comme une «boîte noire» ou oracle), calcule une
fonction dont nous ne connaissons que certaines caractéristiques. Le
problème consiste à déterminer une propriété
inconnue de la fonction, sans «ouvrir» la boite. Nous pouvons
interroger l'oracle en entrant des données dans la boite et en
manipulant sa sortie, sans l'ouvrir pour en analyser le contenu. La figure
suivante illustre cette notion.Le problème sera «facile» si sa
résolution demande un nombre total d'opérations croissant
chapitre3 : Les algorithmes quantiques
de façon polynomiale avec le nombre de bits,
«difficile» s'il croit de façon exponentielle avec ce
nombre.
A ce point, le passage du calcul classique au calcul
quantique transforme certains oracles classiques difficiles en oracles
quantiques faciles. Dans d'autres cas, le problème quantique reste
difficile, mais moins que le problème classique (croissance toujours
exponentielle du nombre d'opérations, mais avec un exposant plus petit
que classiquement).
20
FIGURE 3.1 - représentation par oracle.
| 
