Modèles formels pour l'informatique quantique

3.4 Algorithme de recherche quantique (Grover) :

Le problème [Jorrand, 2005] commence comme celui de Deutsch-Josza. La fonction Booléenne de [0, 2^n-h] dans [0, 1] est réalisée par un oracle agissant sur la superposition symétrique des N = 2ⁿ qubits de A et sur le qubit B préparé par les opérations N et H dans l'état ^v2h (|0) - |1)).

FIGURE 3.3 - Algorithme de recherche quantique (Grover)

Revient à inverser l'amplitude de l'élément x = x0 dans la superposition des états de la base {x} sans toucher aux autres. Comment détecter l'élément dont l'amplitude a été inversé? On applique au registre A, après l'opération de l'oracle O(x0), l'opérateur unitaire Us = 2|s)(s|- 1 où |s)(s| est le projecteur sur la superposition symétrique de tous les états de la base x de A |s)=(_v^h_N)E_x|x).

L'action de Us sur une superposition quelconque |0) = Ex á_x|x) revient à symétriser les amplitudes de |0) par rapport à leur moyenne. De la relation (s|0) = ( iN) Ex á_x = (á)./N où (á) est la moyenne des amplitudes de l'état |0), on déduit en effet :

Us|0) = 2|s)(s|0) - |0) = Ex 2((a) - á_x)|x) = Ex bx|x)

Avec : á.+b.

(a)

2 =

- Illustration de l'algorithme de recherche quantique dans le cas n = 4(N = 16)
On applique l'oracle O(x0) sur |s), puis Us , et on itère les deux opérations. L'effet de O(x0) est
d'abaisser à chaque fois la valeur moyenne (a) (ligne horizontale rouge). L'opération de symétrie

L'état final de A est donc : ( ¹n+1

2

%y [(-1 + ^{(-1)E.i(xi?s)yii} |y1, y2, ..., y_ni

2

24

chapitre3 : Les algorithmes quantiques

par rapport à cette moyenne (Us) réduit le fond et fait ressortir la valeur marquée par l'oracle. Au bout de trois itérations, le fond devient très petit.

On mesure alors le registre A (4 qubits) et on trouve avec une probabilité de 0.96 la valeur x0 = 5 choisie par l'oracle. Il faut savoir quand arrêter la procédure (si on va trop loin, le fond augmente en valeur absolue en devenant négatif). L'itération demande un nombre d'opérations

v

croissant comme N [Gradel, 0910].

FIGURE 3.4 - Exemple de recherche quantique

3.5 L'Algorithme de Simon [Haroche, 2002]

On réalise la suite d'opérations schématisée ci-dessus : calcul parallèle de toutes les valeurs de la fonction suivie d'une mesure du registre B projetant A dans une superposition de deux états qui diffèrent bit à bit de la quantité inconnue s. On applique alors à nouveau les transformations de Hadamard aux n qubits de A : elles font évoluer chaque qubit suivant la loi :

|0i ? ¹_v2 (|0i +|1i) et |1i ? ¹_v2 (|0i-|1i) .Un état |xi (produit de n états |xii avec xi = 0 ou xi = 1) devient une superposition de produits d'états |yii avec yi = 0 ou yi = 1. Les coefficients de cette_e superposition valent + 1 ou - 1 suivant la parité de la somme %i xiyi :

{|xi_I = |x1, x2, ...x_ni ?2 21) %y (-1)E.i ^xiyi |y1, y2, ..., y_ni

25

chapitre3 : Les algorithmes quantiques

( ₁ ) P

= 2 n+' y

2

FIGURE 3.5 - L'Algorithme de Simon

> >

i xiyi h i xisiyii

(-1) 1 + (-1) |y1, y2, ...,y_ni

Une mesure répétée n fois de A va alors nous permettre de déterminer s. - Détermination de la période inconnue s

) P > >

( ₁ i xiyi _{h i}

|ø(final)i_A = y (-1) 1 + (-1) i xisiyi |y1, y2, ..., y_ni

2 n+'

L'amplitude (-1) non nulle ssi P

2

i siyi = 0 (modulo 2)

Une mesure des qubits individuels donne une suite y1a, y2a, . . . _yna de valeurs 0 et 1 qui satisfait la condition: Pi siyi = 0(modulo 2)

On recommence n fois l'opération et on obtient ainsi, en général, n relations indépendantes (si par hasard deux mesures donnent le même vecteur, on recommence une fois de plus) :

_P

i siyia = 0

_P

i siyib = 0

.

..

_P

i siyin = 0

La résolution de ce système d'équations donne s. Le processus requiert 4n² opérations. Le problème est donc quantiquement facile. De plus, il tolère des erreurs puisqu'on peut toujours vérifier le résultat en comparant f(x) et f(x ? s) une fois s obtenu.

- Rôle de l'intrication et de la mesure dans l'algorithme de Simon

Dans l'algorithme de Simon [Haroche, 2002], l'intrication et la mesure projective jouent un rôle plus essentiel que dans ceux de Deutsch et Grover. L'oracle intrique les registres A et B, puis la mesure de B projette A dans une superposition de deux états seulement. Après mélange par la lame séparatrice, la signature du signal d'interférence final nous renseigne sur la séparation de ces deux états, donc sur la période cherchée. Quoique mathématiquement plus compliqué, l'algorithme de Shor, basé sur la recherche de la période d'une fonction, ressemble beaucoup dans son principe à celui de Simon.

26

chapitre3 : Les algorithmes quantiques

FIGURE 3.6 - Rôle de l'intrication et de la mesure dans l'algorithme de Simon

Remarque : il n'est même pas besoin de lire la mesure du registre B. Il suffit d'avoir intriqué B à son appareil de mesure, ce qui réduit A à un mélange statistique de superpositions |x) + x s) Leur recombinaison finale par H1, H2, . . . , H_n ne conduit, quel que soit x, à une interférence constructive que pour les états y1, y2, ..., y_n) satisfaisant les équations linéaires de la page précédente (on peut réduire le nombre d'opérations à 3m²).