Algorithme de Deutsch-Jozsa

Algorithme de Deutsch-Jozsa

L'Algorithme de Deutsch-Jozsa est un algorithme quantique, proposé par David Deutsch et Richard Jozsa en 1992 avec des améliorations de R. Cleve, A. Ekert, C. Macchiavello, et M. Mosca en 1998[1],[2]. Bien qu'il ne soit pas d'un grand intérêt pratique, il s'agit d'un des premiers algorithmes quantiques qui est plus efficace qu'un algorithme classique.

Sommaire

Le problème

Dans le cas du problème de Deutsch-Jozsa, nous disposons d'une boîte noire quantique, connu sous le nom d'Oracle qui implémente une fonction mathématique f:\{0,1\}^n\rightarrow \{0,1\}. Nous savons que cette fonction est soit constante (0 ou 1 sur toutes les entrées) soit équilibrée (0 dans la moitié des cas, 1 dans les autres). Le but du problème est de savoir si la fonction est constante ou équilibrée à l'aide de l'oracle

La solution classique

Si un algorithme classique et déterministe est utilisé, il faut 2n − 1 + 1 évaluation de la fonction mathématique f dans le pire des cas pour trouver la solution.

Dans le cas de l'utilisation d'un algorithme probabiliste, un nombre constant d'évaluation est suffisant pour trouver la bonne réponse avec une forte probabilité, néanmoins 2n − 1 + 1 évaluation sont toujours nécessaire pour que la réponse soit toujours correcte. L'algorithme quantique de Deutsch-Jozsa permet de trouver une réponse toujours correcte avec une seule évaluation de f.

Histoire

L'algorithme est basé sur des travaux de David Deutsch, datant de 1985, concernant le cas n = 1. La question était de savoir si une fonction booléenne, f \{0,1\} \rightarrow \{0,1\}, était constante[3].

En 1992, l'idée a été généralisée pour pouvoir être appliquée sur un nombre n bits en entrée et savoir si la fonction était constante ou équilibrée[1].

L'algorithme de Deutsch n'était pas, à l'origine, déterministe. L'algorithme retournait une réponse juste avec une probabilité de 50%. L'algorithme original de Deutsch-Jozsa était déterministe, mais, à la différence de l'algorithme de Deutsch, il nécessitait deux évaluations de la fonction.

Plusieurs améliorations ont été apportées à l'algorithme de Deutsch-Jozsa par Cleve et al qui ont résulté en un algorithme qui est déterministe et ne nécessite qu'une seule évaluation de la fonction f. Cet algorithme est appelé l'algorithme de Deutsch-Josza en l'honneur de l'importance des techniques qui ont été utilisées[2].

L'algorithme de Deutsch-Jozsa a servi d'inspiration pour les algorithme de Shor et de Grover, deux des algorithmes quantiques les plus révolutionnaires[4],[5].

Algorithme de Deutsch, un cas spécial

Le but est de tester la condition f(0) = f(1) ; Cela est équivalent à vérifier f(0)\oplus f(1). Si cela vaut zéro alors f est constante, sinon f est équilibrée.

L'algorithme commence avec deux qubit dans l'état |0\rangle |1\rangle. Une transformation d'Hadamard est d'abord appliquée à chaque qubit. Cela donne

\frac{1}{2}(|0\rangle + |1\rangle)(|0\rangle - |1\rangle).

Une implémentation quantique (oracle) de la fonction f permet de passer de |x\rangle |y\rangle à |x\rangle |f(x)\oplus y\rangle. En appliquant cette fonction à notre état, nous obtenons

\frac{1}{2}(|0\rangle(|f(0)\oplus 0\rangle - |f(0)\oplus 1\rangle) + |1\rangle(|f(1)\oplus 0\rangle - |f(1)\oplus 1\rangle))
=\frac{1}{2}((-1)^{f(0)}|0\rangle(|0\rangle - |1\rangle) + (-1)^{f(1)}|1\rangle(|0\rangle - |1\rangle))
=(-1)^{f(0)}\frac{1}{2}(|0\rangle + (-1)^{f(0)\oplus f(1)}|1\rangle)(|0\rangle - |1\rangle).

Nous ignorons le dernier bit and la phase and alors nous avons l'état

\frac{1}{\sqrt{2}}(|0\rangle + (-1)^{f(0)\oplus f(1)}|1\rangle).

En appliquant une transformation d'hadamard à cet état, nous obtenons

\frac{1}{2}(|0\rangle + |1\rangle + (-1)^{f(0)\oplus f(1)}|0\rangle - (-1)^{f(0)\oplus f(1)}|1\rangle)
=\frac{1}{2}((1 +(-1)^{f(0)\oplus f(1)})|0\rangle + (1-(-1)^{f(0)\oplus f(1)})|1\rangle).

f(0)\oplus f(1)=0 si et seulement si nous observons un zéro. Donc, la fonction est constante si et seulement si nous mesurons un zéro.

L'algorithme de Deutsch-Jozsa, en détail

Le circut quantique de l'algorithme de Deutsch-Jozsa

Nous commençons avec le n+1 bit dans l'état |0\rangle^{\otimes n} |1\rangle . Les premiers n bits sont tous dans l'état |0\rangle et les derniers bit dans l'état |1\rangle . Nous appliquons ensuite la transformation d'Hadamard à chaque qubit, pour obtenir

\frac{1}{\sqrt{2^{n+1}}}\sum_{x=0}^{2^n-1} |x\rangle (|0\rangle - |1\rangle ).

Références

  1. ↑ a et b David Deutsch et Richard Jozsa, « Rapid solutions of problems by quantum computation », dans Proceedings of the Royal Society of London A, vol. 439, 1992, p. 553 
  2. ↑ a et b R. Cleve, A. Ekert, C. Macchiavello, et M. Mosca, « Quantum algorithms revisited », dans Proceedings of the Royal Society of London A, vol. 454, 1998, p. 339-354 [texte intégral [PDF]] 
  3. ↑ David Deutsch, « The Church-Turing principle and the universal quantum computer », dans Proceedings of the Royal Society of London A, vol. 400, 1985, p. 97 [texte intégral [PDF]] 
  4. ↑ Lov K. Grover, « A fast quantum mechanical algorithm for database search », dans Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, 1996, p. 212-219 [texte intégral [PDF]] 
  5. ↑ Peter W. Shor, « Algorithms for Quantum Computation: Discrete Logarithms and Factoring », dans IEEE Symposium on Foundations of Computer Science, 1994, p. 124-134 [texte intégral [PDF]] 

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de Deutsch-Jozsa de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Algorithme de Shor — En arithmétique modulaire, l’algorithme de Shor est un algorithme quantique pour factoriser un nombre N en temps O((logN)3) et en espace O(logN), nommé en l honneur de Peter Shor. Beaucoup de cryptosystèmes à clé publique, tels que le RSA,… …   Wikipédia en Français

  • David Deutsch — Pour les articles homonymes, voir Deutsch. David Deutsch Naissance 1953 Haïfa (Israël) Nationalité Israélie …   Wikipédia en Français

  • Information quantique — La théorie de l information quantique, parfois abrégée simplement en information quantique, est un développement de la théorie de l information de Claude Shannon exploitant les propriétés de la mécanique quantique, notamment le principe de… …   Wikipédia en Français

  • Calcul quantique — Calculateur quantique Cet article fait partie de la série Mécanique quantique Postulats de la mécanique quantique Histoire de …   Wikipédia en Français

  • Calculateur quantique — La Sphère de Bloch est une représentation d’un qubit Un calculateur quantique ou ordinateur[1] quantique, repose sur des propriétés quantiques de la matière : superposition et intrication d éta …   Wikipédia en Français

  • Ordinateur quantique — Calculateur quantique Cet article fait partie de la série Mécanique quantique Postulats de la mécanique quantique Histoire de …   Wikipédia en Français

  • Informatique quantique — L informatique quantique est le sous domaine de l informatique qui traite des ordinateurs quantiques utilisant des phénomènes de la mécanique quantique, par opposition à ceux de l électricité exclusivement, pour l informatique dite… …   Wikipédia en Français

  • Informatique Quantique — L informatique quantique est le sous domaine de l informatique qui traite des ordinateurs quantiques utilisant des phénomènes de la mécanique quantique, par opposition à ceux de l électricité exclusivement, pour l informatique dite… …   Wikipédia en Français

  • Qubit —  Ne doit pas être confondu avec une cubit (ou coudée), ancienne mesure d environ 45 centimètres. Représentation d un qubit par une sphère de Bloch. On nomme qubit ( …   Wikipédia en Français

  • Thèse de Church — La thèse de Church du nom du mathématicien Alonzo Church est une hypothèse ( thèse ) concernant la définition de la notion de calculabilité. Dans une forme dite physique [1], elle affirme que la notion physique de la calculabilité, définie comme… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”