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:Алгоритм Дойча — Джоза]]