Algorithme de Deutsch-Jozsa

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.

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 transformation d'Hadamard est d'abord appliquée à chaque qubit. 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 transformation d'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.

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

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 appliquons ensuite la transformation d'Hadamard à chaque qubit, pour obtenir

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

Nous avons la fonction ${\displaystyle f}$ implementé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 transformation d'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).