Les ordinateurs quantiques
Algorithmes quantiques

Il se trouve qu'IBM, dans sa grande générosité, propose l'IBM quantum composer, une interface web qui permet de construire un programme quantique (avec des portes quantiques), et en plus, on peut exécuter ses programmes sur un vrai ordinateur quantique, avec des files d'attente à l'ancienne. On peut même choisir son ordinateur.

• IBM quantum lab

Ça ressemble à ça :

J'ai réalisé moi-même, avec mes petites mains un full adder, autrement dit l'addition de deux bits + une retenue, le résultat étant sur 2 bits.
En entrée :

• q0 : le premier bit a
• q1 : le second bit b
• q2 : la retenue c (carry)

• q3 : la somme
• q4 : la nouvelle retenue

Donc je fais a+b+c (en binaire, évidemment !), et j'ai un résultat sur 2 bit, avec la table de vérité suivante il n'y a aucune ruse, c'est très crétin :

On peut voir 3 portes "H" de Hadamard, ce qui me permet de superposer les calculs : j'ai une chance sur deux d'avoir 0 ou 1 sur mes 3 premiers bits, et j'observe ce que ça donne sur les sorties.

On voit le résultat attendu en bas, en termes de probabilité (fenêtre probabilities) —mais c'est une simulation d'IBM.
Tous les résultats sont équiprobables, mais évidemment, seules les valeurs correctes "sortent", par exemple :

• l'état 01100 sort avec une probabilité de 12.5% = 100% / 8, les 8 cas possibles.
  • 01 est le résultat de l'addition
  • 100 (à la fin, c'est q2,q1,q0) est l'entrée correspondante, soit c=1, a=0, b=0.

La somme vaut 1, ça tombe bien !

Sauf que l'exécution sur l'ordinateur quantique ibmq_manilla donne le résultat à gauche, fenêtre result-histogram. 2000 tirages réalisés, et on retrouve assez vaguement les probabilités attendues.

C'est très décevant, et ça montre que ce n'est pas gagné… Que se passera-t-il quand on aura des milliers de qubits avec des milliers d'opérations ? Du coup j'ai essayé sur un autre ordinateur (Santiago de son petit nom).

C'est vaguement mieux. Mais bon, on sent les ennuis. D'ailleurs IBM annonce la couleur en donnant des informations sur le bruit observé et les calibrations réalisées.

IBM propose également un simulateur, et là, ça se passe nettement mieux :

Cette fois, le simulateur ne montre même pas les "ratés". C'est bon, voire trop bon par rapport à la réalité.

On voit bien que l'on peut faire des calculs en parallèle.

Mais si, ça se voit.

Il existe juste un petit problème d'extraction de résultats.

Et visiblement, personne n'a proposé ce que je vais vous présenter, alors je dois faire une sacrée erreur de raisonnement quelque part, parce que ce à quoi je pense est vraiment crétin.

Par exemple, imaginez qu'au lieu de faire un additionneur, je fasse un multiplieur. On se retrouverait en sortie avec toutes les multiplications possibles en même temps, d'un coup! Parmi les résultats, on aura forcément dedans ceux qui donne la multiplication de deux nombres premiers.

Par contre, il va y avoir vraiment beaucoup de résultats, et on en voudrait qu'un seul. L'idée à deux balles est de fournir en entrée le résultat de la multiplication, et de s'arranger pour "amplifier" ce ou ces résultats particuliers (on n'aura pas une seule solution la plupart du temps, ne serait-ce que par symétrie), sinon la probabilité de sortir le résultat d'intérêt sera vraiment très faible.

Et d'une manière plus générale, on doit pouvoir "remonter" n'importe quelle fonction, par exemple un bloc de données chiffrées avec une clé (et là, je commence déjà à ricaner si j'y arrive).

C'est vraiment de la "brute force" bête et méchante, comme moi. Le post-quantique n'a qu'à bien se tenir. Donc faut que je trouve le moyen de comparer et d'extraire, mais bon, je sens que Grover devrait pouvoir m'aider.

Bon d'accord, cela paraissait vraiment trop beau.

Grover peut faire quelque chose, mais comme les qubits sont intriqués, on ne peut pas vraiment faire facilement ce qu'on veut.

Premièrement, il faut commencer par détricoter le calcul car il faut laisser les qubits d'entrée dans leur état initial. En gros, on peut effectuer f(x), mais aussi sec derrière, il faut faire l'inverse, f^-1(x). Bonjour la programmation, mais bon, ce serait encore acceptable.

Mais si on fait ça, alors Grover ne peut rien pour toi, évidemment, puisque nous sommes revenus dans l'état initial. Alors ce qu'on fait, c'est calculer un bit auxiliaire qui dira si c'est la bonne réponse ou non. Par exemple, on pourra indiquer à ce qubit si le résultat est égal ou non au nombre cible. Il vaudra 0 ou 1, et l'astuce consistera à le mettre dans l'état initial (|0> - |1>)√2. Avec les intrications, cela fera inverser la phase pour Grover.

Et même avec ça, il faudra en plus exécuter la fonction plusieurs fois pour amplifier. Et même en √n, ça va faire beaucoup d'itérations, on sent bien qu'on fait une sorte de dichotomie, alors l'exécution en parallèle commence à vraiment perdre de son intérêt…

Et c'est frustrant, car on sait que le résultat qu'on cherche est présent, mais on ne peut pas l'extraire facilement.

À la limite, heureusement que ça ne marche pas.

En effet, si ça marchait aussi simplement, alors je pense qu'on pourrait casser aussi sec n'importe quel algorithme de chiffrement par bloc. En effet, on mettrait toutes les clés possibles en superposition, puis en entrant un message connu dont on a aussi le chiffré, alors on tomberait immanquablement sur la clé !

Il nous faut au moins un message connu, sinon on ne pourrait pas dire si le résultat est OK : toutes les mauvaises réponses ressemblent à du bruit, ce qui est trop difficile à définir pour être détectable.

Ceci dit, en programmant le bloc de chiffrement et son inverse, théoriquement, avec Grover, on doit trouver la clé. Faudrait creuser pour voir si ça peut se faire en un temps raisonnable.

Voici comment il faut procéder, histoire de s'en souvenir.

Le début du programme comporte l'additionneur, on le reconnait avec ses 3 données et ses 2 qubits de résultats, c'est pareil qu'avant.

J'ai dû ajouter un qubit de plus, celui avec la racine carrée, on va y venir, mais en tout cas, c'est à cause de lui que le paquet est dupliqué dans les résultats (les barres violettes et bleuâtres).

Les 3 opérations suivantes (en grisé) vont consister à détecter le résultat spécifique "10", c'est-à-dire que la somme des 3 premiers qubits devra faire exactement 2, soit 10 en binaire (avec l'ordre des bits q4 q3).

L'idée est que le système soit capable de me dire toutes les solutions possibles pour obtenir exactement 2. Et oui, on connait déjà la réponse, c'est 3 combinaisons, d'ailleurs elles sont déjà connues de notre ordinateur, regardez de près par exemple les barres violettes : les trois avant-dernières sont 010011, 010101, 010110, le premier zéro est le qubit de plus, ensuite c'est le résultat de l'additionneur en rouge, puis les données sources en bleu qui permettent d'obtenir ce résultat (il faut exactement deux 1 parmi les trois).

Donc qu'on ne vienne pas me raconter que l'ordinateur quantique ne connait pas déjà le résultat !

Comme on veut détecter exactement 2, soit 10 binaire sur q3 q4, il faudra bien lui dire à l'animal, et c'est le rôle des 3 opérations suivantes qui détectent 10, font flipper notre qubit supplémentaire q5. On est obligé d'ajouter un NOT de plus pour rétablir l'état du qubit car on a fait un NOT juste avant -d'où les 3 étapes.

Lorsque l'on exécute ces trois étapes supplémentaires, alors on constate un changement de phase sur le dernier qubit, qui se traduit par un "échange" de couleurs, justement pour nos trois solutions recherchées.

Ça se présente bien.

D'ailleurs, arrivé là, on aimerait simplement "éteindre les autres" pour ne sortir que les infos souhaitées. Eh bien ça ne marche pas, on ne sait pas faire.

On est obligé de réaliser les opérations inverses de notre additionneur pour le remettre dans l'état où on l'a trouvé en entrant. Il se trouve que ce sont exactement les mêmes opérations pour ce cas particulier.

Arrivé là, on a l'impression d'avoir "perdu" nos trois solutions, mais en fait non, elles sont justes rangées différemment, et on constate aussi que nos qubits q3 q4 sont annulés. Il n'y a plus rien dedans. Mais il traine une corrélation (une intrication) entre nos trois données d'entrées et le dernier qubit en bas.

C'est là qu'intervient la magie du diffuseur ça s'appelle comme ça, autrement dit la ruse à Grover qui permet d'amplifier les éléments présentant une phase particulière -on s'est arrangé pour ça.

Donc on exécute l'espèce d'opération symétrique qui donne plus ou moins l'impression de ne rien faire.

Et là, le miracle est intervenu : on voit nos trois solutions "sortir du rang". Elles ont été amplifiées.

Alors oui, ce n'est pas assez amplifié. Ici, il faut recommencer une seconde fois pour que ça sorte vraiment, et nos trois solutions dépasseront franchement. Il faut donc remettre à la suite l'intégralité de toutes les opérations effectuées (sauf la toute première, le Hadamard, bien sûr), et rebelotte.

Lorsque nous effectuerons une mesure à la fin, alors on aura une probabilité énorme de sortir une des trois solutions. Et en essayant plusieurs fois, on finira par avoir les trois.