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. 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 et les solutions classiques

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 (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.

La solution déterministe

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

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

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

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

Dans le meilleur des cas, le résultat est différent de $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 $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 $R_{ref}$. Nous ne pouvons toujours pas conclure puisque cette proportion de résultats identiques est possible que la fonction $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 à $R_{ref}$ alors il est certain que la fonction $f$ est constante
• Si le résultat est différent de $R_{ref}$ alors il est certain que la fonction $f$ est équilibrée

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

La solution probabiliste

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 $2^{n-1}+1$ évaluations sont toujours nécessaires pour que la réponse soit correcte avec une probabilité de 1.

L'algorithme de Deutsch-Jozsa

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

Algorithme de Deutsch pour un cas particulier

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 qubits 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}}{\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 \}}$

$={\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 \}}$

$=(-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

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

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

${\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 )}$

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

$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

Le circuit quantique de l'algorithme de Deutsch-Jozsa.

Nous commençons avec l'état à n+1 qubit $|0\rangle ^{\otimes n}|1\rangle$. Les premiers $n$ qubits sont tous dans l'état $|0\rangle$ et le dernier qubit 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 )$.

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

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

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

${\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 transformation d'Hadamard à chacun des qubits restants afin d'obtenir

${\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ù $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 $|0\rangle ^{\otimes n}$,

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

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

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.

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.

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.

L'algorithme de Deutsch-Jozsa a servi d'inspiration pour les algorithme de Shor et de Grover, deux des algorithmes quantiques les plus importants.

Article connexe

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