Algorithme de Deutsch-Jozsa
# 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 \{\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 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.
