Algorithme de Deutsch-Jozsa

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

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

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

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

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

Nous voyons donc que, dans le pire des cas, le nombre d'évaluations de ${\displaystyle f}${\displaystyle f} à réaliser est de "la moitié des cas possibles plus un", soit ${\displaystyle 2^{n-1}+1}${\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}${\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)}${\displaystyle f(0)=f(1)} ; cela est équivalent à vérifier ${\displaystyle f(0)\oplus f(1)}${\displaystyle f(0)\oplus f(1)}. Si cela vaut zéro alors ${\displaystyle f}${\displaystyle f} est constante, sinon ${\displaystyle f}${\displaystyle f} est équilibrée.

L'algorithme commence avec deux qubits dans l'état ${\displaystyle |0\rangle |1\rangle }${\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 ).}${\displaystyle {\frac {1}{2}}(|0\rangle +|1\rangle )(|0\rangle -|1\rangle ).}

Une implémentation quantique (oracle) de la fonction ${\displaystyle f}${\displaystyle f} permet de passer de ${\displaystyle |x\rangle |y\rangle }${\displaystyle |x\rangle |y\rangle } à ${\displaystyle |x\rangle |f(x)\oplus 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 \{}|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 ={\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 )}.}${\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 )}.}${\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 (}|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 ={\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}${\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 }${\displaystyle |0\rangle ^{\otimes n}|1\rangle }. Les premiers ${\displaystyle n}${\displaystyle n} qubits sont tous dans l'état ${\displaystyle |0\rangle }${\displaystyle |0\rangle } et le dernier qubit dans l'état ${\displaystyle |1\rangle }${\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 )}${\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\rangle -|1\rangle )}.

Dans cette notation^[4] ${\displaystyle |x\rangle }${\displaystyle |x\rangle } est l'état de l'espace produit tensoriel sur les ${\displaystyle n}${\displaystyle n} premiers qubits après passage dans leurs portes de Hadamard respectives ${\displaystyle |x\rangle }${\displaystyle |x\rangle }est représenté par la suite des digits binaires de la valeur de ${\displaystyle x}${\displaystyle x} par exemple pour ${\displaystyle n=3}${\displaystyle n=3} l'expression ${\displaystyle \sum _{x=0}^{7}|x\rangle }${\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 )}${\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 }${\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 }${\displaystyle \sum _{x\in \{|0\rangle ,|1\rangle \}^{\otimes n}}|x\rangle }

Nous avons la fonction ${\displaystyle f}${\displaystyle f} implémentée sous forme d'oracle quantique. L'oracle transforme l'état ${\displaystyle |x\rangle |y\rangle }${\displaystyle |x\rangle |y\rangle } en ${\displaystyle |x\rangle |y\oplus f(x)\rangle }${\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 )}${\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 x}, ${\displaystyle f(x)}${\displaystyle f(x)} vaut ${\displaystyle 0}${\displaystyle 0} ou ${\displaystyle 1}${\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 )}${\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 }${\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}}${\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 |0\rangle ^{\otimes n}},

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

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