Algorithme de Deutsch-Jozsa — Wikipédia

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.

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 ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}}$. Nous savons que cette fonction est soit constante (la sortie est 0 ou 1 pour toutes les entrées) soit équilibrée (la sortie est 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.

Si un algorithme classique et déterministe est utilisé, il faut ${\displaystyle 2^{n-1}+1}$ évaluations de la fonction mathématique ${\displaystyle f}$ dans le pire des cas pour être certain de trouver la solution (c'est-à-dire tester la moitié des ${\displaystyle 2^{n}}$ entrées possibles, plus une) tel qu'expliqué ci-dessous.

La fonction accepte ${\displaystyle 2^{n}}$ entrées que nous nommerons ${\displaystyle E_{i}}$ avec ${\displaystyle i\in [1;2^{n}]}$.

Tester la fonction ${\displaystyle f}$ sur un seul cas d'entrée (par exemple ${\displaystyle E_{1}}$) ne permet évidemment pas de conclure. Mais cela fournit un premier résultat ${\displaystyle R_{ref}}$ qui servira de référence.

Calculons maintenant ${\displaystyle f(E_{2})}$.

Dans le meilleur des cas, le résultat est différent de ${\displaystyle R_{ref}}$ et nous pouvons immédiatement conclure que la fonction est équilibrée, sans avoir besoin d'aller plus loin.

Sinon, nous ne pouvons rien conclure et il convient de calculer ${\displaystyle f(E_{3})}$. Et ainsi de suite...

Dans le pire des cas, nous arrivons au point où la moitié des valeurs possibles en entrée ont été testées et elles ont toutes retourné le résultat ${\displaystyle R_{ref}}$. Nous ne pouvons toujours pas conclure puisque cette proportion de résultats identiques est possible que la fonction ${\displaystyle f}$ soit constante ou équilibrée !

Par contre, dès le test sur la valeur d'entrée suivante :

• Si le résultat est identique à ${\displaystyle R_{ref}}$ alors il est certain que la fonction ${\displaystyle f}$ est constante
• Si le résultat est différent de ${\displaystyle R_{ref}}$ alors il est certain que la fonction ${\displaystyle f}$ est équilibrée

Nous voyons donc que, dans le pire des cas, le nombre d'évaluations de ${\displaystyle f}$ à réaliser est de "la moitié des cas possibles plus un", soit ${\displaystyle 2^{n-1}+1}$.

Dans le cas de l'utilisation d'un algorithme probabiliste, un nombre d'évaluations réduit permet pour trouver la bonne réponse avec une probabilité donnée, néanmoins ${\displaystyle 2^{n-1}+1}$ évaluations sont toujours nécessaires pour que la réponse soit correcte avec une probabilité de 1.

L'algorithme quantique de Deutsch-Jozsa permet de trouver une réponse toujours correcte avec une seule évaluation de ${\displaystyle f}$.

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

L'algorithme commence avec deux qubits dans l'état ${\displaystyle |0\rangle |1\rangle }$. Une Porte de Hadamard est d'abord appliquée à chaque qubit ce qui met le qbit dans un état superposé. Cela donne

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

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

${\displaystyle {\frac {1}{2}}{\bigg \{}|0\rangle {\bigg (}|f(0)\oplus 0\rangle -|f(0)\oplus 1\rangle {\bigg )}+|1\rangle {\bigg (}|f(1)\oplus 0\rangle -|f(1)\oplus 1\rangle {\bigg )}{\bigg \}}}$

${\displaystyle ={\frac {1}{2}}{\bigg \{}(-1)^{f(0)}|0\rangle {\bigg (}|0\rangle -|1\rangle {\bigg )}+(-1)^{f(1)}|1\rangle {\bigg (}|0\rangle -|1\rangle {\bigg )}{\bigg \}}}$

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

Nous ignorons le dernier bit et la phase globale, nous avons alors l'état

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

En appliquant une Porte de Hadamard à cet état, nous obtenons

${\displaystyle {\frac {1}{2}}{\bigg (}|0\rangle +|1\rangle +{\big (}(-1)^{f(0)\oplus f(1)}{\big )}|0\rangle -{\big (}(-1)^{f(0)\oplus f(1)}{\big )}|1\rangle {\bigg )}}$

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

${\displaystyle 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.

Nous commençons avec l'état à n+1 qubit ${\displaystyle |0\rangle ^{\otimes n}|1\rangle }$. Les premiers ${\displaystyle n}$ qubits sont tous dans l'état ${\displaystyle |0\rangle }$ et le dernier qubit dans l'état ${\displaystyle |1\rangle }$. Nous faisons passer chaque qubit dans une porte de Hadamard ce qui le met dans un état superposé, pour obtenir

${\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\rangle -|1\rangle )}$.

Dans cette notation^[3] ${\displaystyle |x\rangle }$ est l'état de l'espace produit tensoriel sur les ${\displaystyle n}$ premiers qubits après passage dans leurs portes de Hadamard respectives ${\displaystyle |x\rangle }$est représenté par la suite des digits binaires de la valeur de ${\displaystyle x}$ par exemple pour ${\displaystyle n=3}$ l'expression ${\displaystyle \sum _{x=0}^{7}|x\rangle }$ vaut ${\displaystyle (|0\rangle +|1\rangle )(|0\rangle +|1\rangle )(|0\rangle +|1\rangle )=(|000\rangle +|001\rangle +...+|110\rangle +|111\rangle )}$ il existe d'autres notations pour exprimer cette somme d'états de l'espace produit: ${\displaystyle \sum _{x_{1},...,x_{n}=0}^{1}|x_{1}...x_{n}\rangle }$ ou ${\displaystyle \sum _{x\in \{|0\rangle ,|1\rangle \}^{\otimes n}}|x\rangle }$

Nous avons la fonction ${\displaystyle f}$ implémentée sous forme d'oracle quantique. L'oracle transforme l'état ${\displaystyle |x\rangle |y\rangle }$ en ${\displaystyle |x\rangle |y\oplus f(x)\rangle }$. L'application de l'oracle quantique donne donc

${\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|f(x)\rangle -|1\oplus f(x)\rangle )}$.

Pour chaque ${\displaystyle x}$, ${\displaystyle f(x)}$ vaut ${\displaystyle 0}$ ou ${\displaystyle 1}$. Une rapide vérification de ces deux possibilités nous laisse

${\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle (|0\rangle -|1\rangle )}$.

À ce point, le dernier qubit peut être ignoré. Nous appliquons alors à nouveau une Porte de Hadamard à chacun des qubits restants afin d'obtenir

${\displaystyle {\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}\sum _{y=0}^{2^{n}-1}(-1)^{x\cdot y}|y\rangle ={\frac {1}{2^{n}}}\sum _{y=0}^{2^{n}-1}\left[\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x\cdot y}\right]|y\rangle }$

où ${\displaystyle x\cdot y=x_{0}y_{0}\oplus x_{1}y_{1}\oplus \cdots \oplus x_{n-1}y_{n-1}}$ est la somme du produit bit-à-bit.

Finalement nous examinons la probabilité de mesurer ${\displaystyle |0\rangle ^{\otimes n}}$,

${\displaystyle {\bigg |}{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}{\bigg |}^{2}}$

qui vaut 1 si ${\displaystyle f(x)}$ est constant (interférence constructive) et 0 si ${\displaystyle f(x)}$ est équilibrée (interférence destructive).

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

En 1992, l'idée a été généralisée pour pouvoir être appliquée sur un nombre ${\displaystyle 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 ${\displaystyle 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^[5] et de Grover^[6], deux des algorithmes quantiques les plus importants.

• Algorithme de Bernstein-Vazirani, version restreinte de l'algorithme de Deutsch-Jozsa.

• Portail de l'informatique théorique