Algorithme de Deutsch-Jozsa 2893264 31686932 2008-07-18T17:25:30Z Sherbrooke 18624 Raccourcir. Traduire. 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]].<ref name="DJ92"> {{cite journal | author = [[David Deutsch]] et [[Richard Jozsa]] | title = Rapid solutions of problems by quantum computation | journal = Proceedings of the Royal Society of London A | volume = 439 | pages = 553 | date = 1992}} </ref>{{,}}<ref name="CEMM98"> {{cite journal | author = R. Cleve, A. Ekert, C. Macchiavello, et M. Mosca | title = Quantum algorithms revisited | journal = Proceedings of the Royal Society of London A | volume = 454 | pages = 339-354 | date = 1998 | url = http://arxiv.org/pdf/quant-ph/9708016 | format = PDF}} </ref> 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. ==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 <math>f:\{0,1\}^n\rightarrow \{0,1\}</math>. Nous savons que cette fonction est soit [[constant]]e (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 <math>2^{n-1} + 1</math> évaluation de la fonction mathématique <math>f</math> 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 <math>2^{n-1} + 1</math> é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 <math>f</math>. ==Histoire== L'algorithme est basé sur des travaux de [[David Deutsch]], datant de [[1985]], concernant le cas <math>n=1</math>. La question était de savoir si une fonction booléenne, <math>f \{0,1\} \rightarrow \{0,1\}</math>, était constante.<ref name="Deu85"> {{cite journal | author = [[David Deutsch]] | title = The Church-Turing principle and the universal quantum computer | journal = Proceedings of the Royal Society of London A | volume = 400 | pages = 97 | date = 1985 | url =http://coblitz.codeen.org:3125/citeseer.ist.psu.edu/cache/papers/cs/13701/http:zSzzSzwww.qubit.orgzSzresourcezSzdeutsch85.pdf/deutsch85quantum.pdf | format =PDF}} </ref> En [[1992]], l'idée a été généralisée pour pouvoir être appliquée sur un nombre <math>n</math> bits en entrée et savoir si la fonction était constante ou équilibrée.<ref name="DJ92" /> 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 évaluation de la fonction. Plusieurs amélioration 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 <math>f</math>. Cet algorithme est appelé l'algorithme de Deutsch-Josza en l'honneur de l'importance des techniques qui ont été utilisées.<ref name="CEMM98" /> L'algorithme de Deutsch-Jozsa a servi d'inspiration pour les [[algorithme de Shor]] et de [[algorithme de Grover|Grover]], deux des algorithmes quantiques les plus révolutionnaires.<ref name="Gro85"> {{cite journal | author = Lov K. Grover | title = A fast quantum mechanical algorithm for database search | journal = Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing | pages = 212-219 | date = 1996 | url =http://arxiv.org/pdf/quant-ph/9605043 | format =PDF}} </ref><ref name="Shor85"> {{cite journal | author = Peter W. Shor | title = Algorithms for Quantum Computation: Discrete Logarithms and Factoring | journal = IEEE Symposium on Foundations of Computer Science | pages = 124-134 | date = 1994 | url = http://citeseer.ist.psu.edu/cache/papers/cs/408/http:zSzzSzwww.research.att.comzSz%7EshorzSzpaperszSzQCalgs.pdf/algorithms-for-quantum-computation.pdf | format =PDF}} </ref> ==Algorithme de Deutsch, un cas spécial== Le but est de tester la condition <math>f(0)=f(1)</math> ; Cela est équivalent à vérifier <math>f(0)\oplus f(1)</math>. Si cela vaut zéro alors <math>f</math> est constante, sinon <math>f</math> est équilibrée. L'algorithme commence avec deux qubit dans l'état <math>|0\rangle |1\rangle</math>. Une [[Transformée de Hadamard|transformation d'Hadamard]] est d'abord appliquée à chaque qubit. Cela donne :<math>\frac{1}{2}(|0\rangle + |1\rangle)(|0\rangle - |1\rangle).</math> Une implémentation quantique (oracle) de la fonction <math>f</math> permet de passer de <math>|x\rangle |y\rangle</math> à <math>|x\rangle |f(x)\oplus y\rangle</math>. En appliquant cette fonction à notre état, nous obtenons :<math>\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))</math> :<math>=\frac{1}{2}((-1)^{f(0)}|0\rangle(|0\rangle - |1\rangle) + (-1)^{f(1)}|1\rangle(|0\rangle - |1\rangle))</math> :<math>=(-1)^{f(0)}\frac{1}{2}(|0\rangle + (-1)^{f(0)\oplus f(1)}|1\rangle)(|0\rangle - |1\rangle).</math> Nous ignorons le dernier bit and la phase and alors nous avons l'état :<math>\frac{1}{\sqrt{2}}(|0\rangle + (-1)^{f(0)\oplus f(1)}|1\rangle).</math> En appliquant une transformation d'hadamard à cet état, nous obtenons :<math>\frac{1}{2}(|0\rangle + |1\rangle + (-1)^{f(0)\oplus f(1)}|0\rangle - (-1)^{f(0)\oplus f(1)}|1\rangle)</math> :<math>=\frac{1}{2}((1 +(-1)^{f(0)\oplus f(1)})|0\rangle + (1-(-1)^{f(0)\oplus f(1)})|1\rangle).</math> <math>f(0)\oplus f(1)=0</math> 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== [[Image:Deutsch-Jozsa Algorithm.svg|thumb|right|Le circut quantique de l'algorithme de Deutsch-Jozsa]] Nous commençons avec le n+1 bit dans l'état <math>|0\rangle^{\otimes n} |1\rangle </math>. Les premier n bits sont tous dans l'état <math>|0\rangle </math> et les dernier bit dans l'état <math>|1\rangle </math>. Nous appliquons ensuite la [[Transformée de Hadamard|transformation d'Hadamard]] à chaque qubit, pour obtenir :<math>\frac{1}{\sqrt{2^{n+1}}}\sum_{x=0}^{2^n-1} |x\rangle (|0\rangle - |1\rangle )</math>. 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]].<ref name="DJ92"> {{cite journal | author = [[David Deutsch]] et [[Richard Jozsa]] | title = Rapid solutions of problems by quantum computation | journal = Proceedings of the Royal Society of London A | volume = 439 | pages = 553 | date = 1992}} </ref><ref name="CEMM98"> {{cite journal | author = R. Cleve, A. Ekert, C. Macchiavello, et M. Mosca | title = Quantum algorithms revisited | journal = Proceedings of the Royal Society of London A | volume = 454 | pages = 339-354 | date = 1998 | url = http://arxiv.org/pdf/quant-ph/9708016 | format = PDF}} </ref> 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. ==Références== {{reflist}} [[Catégorie:Algorithme]] [[de:Deutsch-Jozsa-Algorithmus]] [[en:Deutsch-Jozsa algorithm]] [[es:Algoritmo de Deutsch-Jozsa]] [[lt:Doičo-Džozo algoritmas]] [[pt:Algoritmo de Deutsch-Jozsa]] [[ru:Алгоритм Дойча — Джоза]]