Les ordinateurs quantiques
Algorithmes quantiques

L'algorithme de Grover est a priori le plus simple algorithme vraiment utile et il permettrait d'accélérer cette recherche. Surtout avec les fonctions précédemment introduites (mais il a fallu d'abord les inventer, ce qui est loin d'être évident).

Évidemment que l'annuaire est rangé dans l'ordre des noms ou carrément dans un désordre infâme, sinon c'est trop facile (et l'algorithme de Grover est alors sans intérêt). D'une manière générale, on suppose que toutes les entrées ont une chance équiprobable d'être le bon numéro (celui dont on recherche le proprio) -sinon il existera d'autres algorithmes plus efficaces.

Une recherche classique prendrait, dans le pire des cas où c'est le dernier nom d'un annuaire comportant N noms, N-1 comparaisons inutile de faire la dernière, c'est forcément le résultat, et en moyenne N/2 comparaisons.

L'algorithme de Grover prétend trouver le nom en √N opérations dans un annuaire désordonné. Et comment ?

Dans le temps et encore maintenant chez quelques pleutres on qualifiait cet algorithme d'algorithme de recherche dans une database. Puis le mot database a vite disparu.

Évidemment, car il y a une entourloupe : vous allez vite voir qu'il faut donner la fonction qui identifie le nom, que l'on nomme oracle : c'est une sorte de boite noire qu'il faut introduire dans l'ordinateur quantique. Et vous trouverez difficilement un article qui vous dira comment relier ça à une vraie database.

Cet algorithme est une ruse extraordinaire pour extraire un résultat particulier d'une fonction qui répond f(x)=1 pour le bon x à trouver, et f(x)=0 pour les mauvais résultats, et il faut fournir (=programmer) la fonction (l'oracle) dans l'ordinateur quantique. Et oui, on suppose que la fonction est donnée, et donc quelque part, on connait déjà le résultat, puisqu'il a fallu la programmer et donc parcourir la database.

C'est très décevant, mais je m'en doutais depuis le début, je ne comprenais pas comment on pouvait entrer un annuaire dans quelques qubits d'une manière simple.

Et en plus, ces ordinateurs quantiques ont une bien mauvaise mémoire.

Grover est un algorithme qui extrait le bon x, le seul qui retourne 1 dans la fonction booléenne en √N opérations. Et avec les indices que je vous ai donnés précédemment, et la requalification du problème je pense que vous avez déjà deviné comment ça marche :

1. On programme l'oracle = la fonction qui dit «oui» uniquement pour un |x> donné. On s'arrange pour que l'amplitude de sortie soit négative pour celui-là, et tous les autres ont le niveau positif habituel.
2. On applique le coup de la symétrie par rapport à la moyenne : le bon résultat commence " à sortir ".
3. On recommence plusieurs fois, jusqu'à ce que la probabilité de mesurer le bon résultat soit assez importante, et on prouve que cela arrive en √N itérations (il existe une jolie démonstration géométrique).

Évidemment, dit comme ça, ça parait simple. Mais il a fallu le trouver, et c'est loin d'être évident, en fait l'astuce de la symétrie par rapport à la moyenne est géniale. Cet algorithme est représenté ainsi, de manière simplifiée, avec des portes quantiques :

Le « Uω » contient la fonction qui retourne «1» quand c'est le bon «x» : c'est l'oracle. En fait, on ruse avec le |1> en bas pour que ce soit «-1», on va voir ça sur un exemple, et ça permettra de réviser un poil.

La préparation avec Hadamard appliquée sur les |0> en entrée est connue on l'a déjà vu, ou alors vous lisez vraiment trop vite en diagonale. Construire un oracle avec 1 bit a déjà été vu, on va le faire avec 3 bits, histoire de mieux percevoir ce que c'est. Mais on ne va pas se peler toutes les fonctions possibles, on va en voir uniquement 3 où il n'existe qu'une seule réponse qui donne "1". C'est une condition requise pour que l'algorithme fonctionne correctement.

Nos boites noires sont prêtes. Rappelez-vous qu'on ne devrait pas en connaitre l'intérieur. La prochaine étape est de deviner le contenu.

On met en premier la préparation avec Hadamard :

1. Initialisation :
   • Les trois qubits |x> sont initialisés à zéro : |000>
   • Le qubit |y> est mis à |1>
2. Préparation :
   • Les trois qubits |x> sont mis en superposition: toutes les amplitudes valent 1/√8 (2³ états)
   • Le qubit |y> est mis en superposition, et comme il valait |1>, il devient |y> = 1/√2 (|0> - |1>) Notez le signe négatif devant le |1>.
   • En "2", le produit tensoriel vaut : |x> ⊗ 1/√2 (|0> - |1>)

3. L'oracle est appliqué, on effectue la multiplication par la matrice de l'oracle.
   • Cela a pour effet d'inverser le signe de |010> (ce n'est pas si évident à voir, mais c'est ce qui se passe grâce au signe négatif de |y>), mais pas les autres.

Maintenant on applique la boite qui réalise la symétrie par rapport à la moyenne. C'est en fait assez simple à réaliser en termes de portes quantiques. Je ne rentre pas dans le détail du fonctionnement, on sait que ça marche, cela a même été testé.

• La moyenne vaut 1/√8 * (7 -1)/8 = 0.265
• Le symétrique de 1/√8 = 0.353 par rapport à 0.265 vaut 0.176 (0.353-0.265=0.088)
• Le symétrique de -1/√8 = -0.353 par rapport à 0.265 vaut 0.883 (0.265+0.353-=0.618)

Pourquoi s'arrêter ici ? Il suffit de recommencer pour améliorer le résultat !

On voit que la probabilité d'apparition (le carré de l'amplitude, soit 0.938) devient importante, et il est inutile d'aller plus loin. On montre qu'il faut √N itérations, ici N=2³=8 soit 2.8 qu'on arrondit à 2.

On peut alors passer à la mesure, le résultat sortira clairement.

Et là, ça rigole moins. En effet, on s'attend plutôt à devoir entrer le numéro de téléphone ttt dont on recherche le propriétaire, et que l'algorithme nous "sorte" le numéro d'index, et puis le nom.

Il faut donc entrer, par un moyen ou par un autre, une base de donnée qui sera une séquence de numéros {le premier numéro, le second numéro … le dernier numéro} dans une mémoire (quantique) quelconque (et là, le bât blesse) une bonne fois pour toutes (on aimerait faire plus tard d'autres recherches !) car sinon, durant l'introduction des numéros, comme on les aura tous vus un par un, autant faire l'unique comparaison à ce moment-là, classiquement.

C'est même pire que vous ne le croyez : idéalement, il faudra pouvoir faire des mises à jour de l'annuaire. Aaahhh ! 😱

Si on arrivait à faire tout ça, on pourra alors à loisir fournir le numéro à rechercher, puis l'algorithme de Grover nous trouvera le numéro d'index, c'est-à-dire la position de ce numéro, dans la database, qui donnera le nom du propriétaire par exemple le numéro six, non, je ne suis pas un numéro

Notez que l'annuaire n'a pas besoin d'être rangé, c'est un peu comme si vous cherchiez le nom d'une personne dans votre carton de cartes de visite que vous n'utilisez plus.

Pour ne pas arranger les choses, si jamais il existe plusieurs résultats possibles dans la database (si la fonction codée dans l'oracle possède plusieurs x différents qui donnent f(x=1), alors l'algorithme marche nettement moins bien. Alors les gens se sont mis aussi à faire des algorithmes pour extraire ce nombre, afin d'adapter l'algorithme. Et rappelez-vous qu'on joue avec des probabilités, aussi le résultat n'est pas toujours certain, faudra peut-être recommencer plusieurs fois.

Alors comment qu'on peut faire ça ? On sent bien que ça va être fastidieux.

C'est encore au stade de la recherche et de la discussion, c'est un sujet à part entière que je ne traiterai pas ici.