# 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 Porte de Hadamard est d'abord appliquée à chaque qubit ce qui met le qbit dans un état superposé. 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 Porte de 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 \{\bigg1+(-1)^{f(0)\oplus f(1)}{\bigg )}|0\rangle +{\bigg1-(-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

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 faisons passer chaque qubit dans une porte de Hadamard ce qui le met dans un état superposé, pour obtenir
    ${\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\rangle -|1\rangle )$.
Dans cette notation $|x\rangle$ est l'état de l'espace produit tensoriel sur les $n$ premiers qubits après passage dans leurs portes de Hadamard respectives $|x\rangle$est représenté par la suite des digits binaires de la valeur de $x$ par exemple pour $n=3$ l'expression $\sum _{x=0}^{7}|x\rangle$ vaut $(|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: $\sum _{x_{1},...,x_{n}=0}^{1}|x_{1}...x_{n}\rangle$ ou $\sum _{x\in \{|0\rangle ,|1\rangle \}^{\otimes n}}|x\rangle$
Nous avons la fonction $f$ implémenté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 Porte de 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.