Modèles formels pour l'informatique quantique

3.2.1 Exemples d'oracles classiquement difficiles

- L'oracle de Deutsch-Josza

f(x) est une fonction booléenne de [0, 2^7-1] dans [0, 1]. On sait qu'elle est soit constante, soit balancée. Est-elle l'un ou l'autre?

Classiquement, il faut interroger l'oracle 2^7-1 + 1 fois pour répondre à la question à coup sûr (il faut introduire 2^7-1 + 1 valeurs différentes de x et calculer f(x) à chaque fois). Croissance exponentielle avec n du nombre d'opérations est problème classique difficile.

- L'oracle de Grover

f(x) est une fonction booléenne de [0, 2^7-1] dans [0, 1] qui n'est non nulle que pour x = x0. Trouver x0.

chapitre3 : Les algorithmes quantiques

Equivaut à la recherche inversée d'un abonné dans un annuaire à partir de son numéro connu a. Les x sont les abonnés, f(x) vaut 1 si a est le numéro de x, 0 sinon.

Classiquement, il faut calculer f(x) (consulter l'annuaire) N = 2^n_1 fois pour trouver à coup sûr. Problème classique difficile.

- L'oracle de Simon

f(x) est une fonction de [0, 2^n_1] dans [0, 2^n_1] telle que :

f(x') = f(x) ssi x = x s où s est une suite inconnue à n termes de 0 et 1 et représente l'addition bit à bit (s : période de f). Déterminer s.

Classiquement, il faut calculer f(x) pour des valeurs aléatoires de xjusqu'à trouver deux x et x' tels que f(x) = f(x').

Alors x s = x' et x x' = x x s = s (car x x = 0). Il faut 2^n_1 + 1 opérations pour trouver la réponse à coup sûr. Problème classique difficile.

3.3 L'Algorithme quantique de Deutsch-Josza:

FIGURE 3.2 - L'oracle de Deutsch-Josza

21

22

chapitre3 : Les algorithmes quantiques

Le registre d'entrée A (n qubits) est préparé (par application de la transformation de Hadamard H sur chaque qubit) dans la superposition symétrique des 2ⁿ états |xi possibles.

Le registre de sortie B (1 qubit) est inversé par N, puis préparé par H dans ^1v2 (|0i - |1i) Action d'oracle : [Gradel, 0910] |xi |0i ? |xi |f(x)i et |xi |1i ? |xi |1 ? f(x)i

Si f(x) = 0 : |xi (|0i - |1i) ? |xi (|0i - |1i)
Si f(x) = 1 : |xi (|0i - |1i) ? - |xi (|0i - |1i)

donc : (-1)^f(x) |xi (|0i - |1i)

Et par superposition :

1
n+1

2 2

Ex |xi ₍|0i - |1i) ? 2 21 Ex ₍-1)^f(x) |xi ₍|0i - |1i)

Les registres restent non intriqués après l'oracle. Déphasage des amplitudes dans le registre A en (-1)^f(x). Pour résoudre le problème, il s'agit de décider entre deux possibilités :

- Si f(x) est constante :

f(x) = 0?x ou f(x) = 1?x donc 2n Ex (-1)^f(x) |xi = #177;22 ^Ex |xi alors registre A inchangé (au signe prés).

- Si f(x) est balancé :

Autant de f(x) = 0 que de f(x) = 1 donc autant d'amplitude +1 que d'amplitude -1 dans la superposition finale du registre A

? Ex (-1)^f(x) |xi orthogonal à ^Ex |xi.

Résoudre l'oracle revient à distinguer deux états orthogonaux de l'état final du registre A : On applique à nouveau H à tous les qubits. Comme H² = 1, on retrouve l'état initial {|0i} si f(x) est constante, un état orthogonal si f(x) est balancée donc au moins un des qubits doit alors être 1. On le vérifie en mesurant les qubits finals de A.

La réponse nécessite au plus 3n + 2 opérations à un qubit 2n + 1 opérations H, une opération de bascule N et au plus mesure de n qubits (on peut arrêter dès qu'on trouve un 1) donc problème quantiquement facile.

23

chapitre3 : Les algorithmes quantiques

- Comparaison avec la procédure classique

L'avantage de l'algorithme quantique n'existe que si on cherche une réponse certaine. Si on s'autorise une probabilité finie c d'erreur, aussi petite soit-elle, l'algorithme classique (calcul successif de f(x) pour des valeurs de x tirées au hasard) donne un résultat acceptable au bout de k ^_' -log2(c) opérations (nombre indépendant de n). Le problème classique devient donc facile dès qu'on accepte un taux fini d'erreur. Ceci diminue considérablement l'intérêt de l'algorithme quantique puisqu' il faut être sûr de pouvoir l'effectuer sans aucune décohérence pour qu'il soit avantageux par rapport à la version classique.