Qu'est-ce qu'un algorithme quantique ?

Waleed Mouhali
 

Intérieur de l'un des ordinateurs quantiques développés par IBM.
IBM Research/flickr, CC BY-ND.

   Nous le savons toutes et tous, nous vivons une époque scientifique formidable ! Une transition sociétale est en cours, dominée par deux piliers majeurs : les transitions écologiques et numériques. Dans la transition digitale, il va falloir compter avec l'informatique dite « quantique ». Incontournable, on en parle (à juste titre) comme une révolution scientifique et technique et un véritable changement de paradigme. L'ordinateur quantique étant une extension de l'ordinateur « classique », il faut alors reprendre les concepts clés de l'informatique et leur donner leur « version » quantique. Dans cette perspective, il nous faut définir ce qu'est un algorithme quantique.

L'algorithme classique

   Le mot « algorithme » [1], un peu employé à tort et à travers ces dernières années, perd un peu de sa substance originelle. D'Euclide à Google en passant par Al-Khwârizmî (du nom duquel le mot algorithme est dérivé), l'algorithme est l'antidote de la résolution d'un problème formulé à l'aide des mathématiques. Dans son célèbre article de 1936 [2], Alan Turing relie l'algorithmique à la notion de « calculabilité », c'est-à-dire la possibilité de calculer sous la forme d'algorithmes, considérés en conséquence comme de « vrais » objets mathématiques prenant la forme d'une suite finie et non ambiguë d'instructions et d'opérations permettant de résoudre une classe de problèmes.

   Un algorithme devient alors une méthode générale pour résoudre un type de problèmes ; et l'informatique théorique devient une branche des mathématiques.

   Un certain nombre de qualificatifs permet de caractériser un algorithme : efficacité, performance, complexité. (Nous nous limitons ici à ces quelques notions). L'efficacité est mesurée notamment par sa durée de calcul, sa consommation de mémoire vive (en partant du principe que chaque instruction a un temps d'exécution constant), la précision des résultats obtenus (par exemple avec l'utilisation de méthodes probabilistes), ou encore sa scalabilité (son aptitude à être efficacement parallélisé). Il sera dit performant s'il utilise avec parcimonie les ressources dont il dispose, c'est-à-dire le temps CPU, la mémoire vive et (aspect objet de recherches récentes) la consommation électrique. Enfin, la complexité permet de prédire le temps de calcul nécessaire pour amener un algorithme à son terme, en fonction de la quantité de données à traiter.

   On peut essentiellement regrouper les algorithmes en 3 familles :

• fondamentaux : ils ont des tâches parfaitement bien définies, dont le résultat est facilement vérifiable
• optimisation : ils cherchent à identifier des paramètres ou une configuration qui maximise ou minimise une valeur (exemple : recherche d'un chemin le plus court entre deux points)
• cryptographiques : ils sont destinés à garantir la sécurité des communications et transactions

Animation montrant un algorithme testant plusieurs chemins
pour entre plusieurs points et choisissant le plus court

L'algorithme de Dijkstra permet
de trouver le chemin le plus court
entre les points a et b. Ibmua/Wikimedia.

   Avant d'établir l'extension quantique d'un algorithme, rappelons les bienfaits de l'informatique quantique.

Le principe de l'informatique quantique

   L'informatique classique est fondamentalement basée sur le traitement de signaux binaires, c'est-à-dire basés sur deux états. L'état d'un interrupteur ou d'un bit en mémoire est soit 0 soit 1 : un registre de n bits équivaut donc à n valeurs. L'informatique classique traitera chacune de ces valeurs de façon linéaire, les unes à la suite des autres, cela va donc prendre un certain temps de traitement.

   En mécanique quantique, les paradigmes changent profondément. Trois aspects de la mécanique quantique sous-tendent la possibilité de faire de l'informatique quantique : la dualité onde-corpuscule, la superposition d'états et l'intrication.

De par leur nature onde-corpuscule, les particules quantiques sont décrites par des probabilités évoluant dans le temps et dans l'espace. De plus, elles ont la capacité de se trouver dans un état qu'on appelle « superposé » : à la fois un peu 0 et un peu 1. Ainsi, un qubit (la version quantique du bit traditionnel) possède deux états "d'existence", nommés (par convention et par analogie avec le bit classique) |0> et |1> (prononcés : ket 0 et ket 1). Alors qu'un bit classique est numérique et a toujours pour valeur soit 0 soit 1, l'état d'un qubit est une superposition quantique linéaire de ses deux états de base (autrement dit, il vaut en même temps |0> et |1>). Par contre, si on cherche à l'observer, on va alors trouver soit un 0 ou un 1 : l'observation a changé l'état de la particule en choisissant entre les deux. Un qubit observé se conduit dès lors comme un bit classique. Enfin, par l'intrication, on peut faire vivre en « couple » deux particules quantiques et rendre leur état quantique interdépendant. Cela est très utile pour tenter de suivre et comprendre l'évolution d'un qubit.

   Avec un registre de n qubits, on a donc en même temps 2n valeurs, qui peuvent toutes être stockées simultanément (là où l'informatique classique ne peut stocker qu'une valeur à la fois). Si on arrive à faire des calculs avec de tels supports, on arrive en quelque sorte à faire tous les calculs en même temps, comme si on réalisait 2n calculs « en parallèle ». Par exemple, si n=3, un ordinateur quantique aura la possibilité de traiter 8 états quantiques différents, et donc 8 calculs en même temps. Si chaque calcul durait une seconde, un ordinateur quantique n'aurait donc besoin que de 1 seconde pour les réaliser (là où un ordinateur classique aurait eu besoin de 8 secondes, puisqu'il aurait dû traiter chaque calcul l'un après l'autre). (Note : il ne s'agit ici que d'un exemple simplifié visant à illustrer le propos, et pas de calculs ou de fonctionnement réel.)

L'ordinateur quantique se base sur des méthodologies
différentes de l'ordinateur classique.

   À la fin, il se peut qu'il n'y ait qu'un seul de ces calculs qui ait réussi, et c'est son résultat qui nous intéresse. La difficulté, c'est de l'isoler. L'art des algorithmes quantiques est donc d'effacer de façon judicieuse tous les calculs qui n'ont pas abouti.

L'algorithme quantique

   En informatique classique, un programme informatique est constitué d'une suite d'instructions réalisées séquentiellement. Au niveau microscopique, ces instructions résultent du traitement des bits par des portes logiques.

   En informatique quantique, les portes deviennent quantiques, ce qui change la nature intrinsèque du traitement des instructions. Il faut alors repenser la nature de la formulation des algorithmes, qui, par extension, deviennent quantiques.

   À ce stade, le principe de superposition [3] propre à la physique quantique permet d'appliquer ces différentes étapes à une superposition arbitraire des états de base, voire à leur somme complète. Comme la lecture du registre ne fournit qu'une valeur 0 ou 1 pour chaque bit (pour rappel, un qubit observé se fige dans un état donné et se comporte comme un bit classique), soit un des états de base du registre, tout l'art de l'algorithmique quantique consiste à concentrer l'évolution vers les états donnant une/la solution du problème cherché.

   Un ordinateur quantique n'est donc pas uniquement une machine universelle qui résoudrait tous les problèmes plus rapidement qu'un ordinateur conventionnel. Il s'agit plutôt d'une machine capable de résoudre efficacement certains problèmes hors de portée des machines conventionnelles, en utilisant une méthodologie entièrement différente. Le jeu consiste donc à comparer la complexité d'un problème d'un point de vue classique et quantique : si un algorithme peut être résolu de manière classique avec une complexité bien définie, alors il peut aussi l'être dans le modèle quantique avec une complexité équivalente ou moindre.

   Les capacités de l'algorithmique quantique sont directement reliées au nombre de qubits... mais pas seulement. Augmenter leur nombre ne sert que si « l'environnement » quantique est maintenu malgré les inévitables processus de décohérence. Une autre particularité du qubit par rapport à un bit classique est qu'il ne peut pas être dupliqué en raison des lois de la physique quantique.

Quelques algorithmes quantiques célèbres

   Mais quels problèmes intéressants peut-on aborder avec le calcul quantique ? Tous les problèmes de prédiction et contrôle de systèmes complexes, comme la finance, la météorologie, la santé, l'énergie, mais aussi la physique quantique elle-même !

   Sorte de pièce montée inversée tombant du plafond, composée de plusieurs étages constitués de cyclindres reliés par des câble. L'ensemble est doré et transparent, et très volumineux.

L'un des ordinateurs quantiques
développés par IBM.
IBM Research/flickr, CC BY-ND.

   L'algorithme de Shor [4], premier algorithme quantique reconnu comme tel, explique comment factoriser de grands nombres en facteurs premiers de manière efficace. On ne sait pas faire cela avec l'informatique classique. Les algorithmes qu'on connaît prennent un temps exponentiel. D'ailleurs, une grande partie de la cryptographie (très utilisée dans nos vies quotidiennes) est basée sur le fait qu'on ne sait pas factoriser rapidement un nombre premier. Ce problème de factorisation, on arrive à le résoudre dans le modèle quantique avec l'algorithme de Shor. Évidemment, pour que cela devienne réalisable en pratique, il faudrait savoir construire un ordinateur quantique qui manipule quelques milliers de qubits. On n'y est pas encore. L'algorithme de Shor fut utilisé en 2001 par un groupe d'IBM, qui factorisa 15 en 3 et 5, en utilisant un calculateur quantique de 7 qubits ! Récemment, c'est le nombre 21 qui a été factorisé sur un processeur quantique d'IBM. Une preuve que l'algorithme fonctionne !

   L'algorithme de Grover [5] est un autre algorithme quantique connu. Il permet de rechercher un ou plusieurs éléments qui répondent à un critère donné parmi N éléments non classés. Le problème se résout avec une complexité moindre qu'un algorithme classique.

   La course à l'algorithme quantique est lancée. Et si l'on combine les atouts de l'IA avec la puissance du calcul parallèle quantique (discipline nommée Quantum Machine Learning), aura-t-on atteint les limites de la puissance informatique ? Si la question de l'algorithme « intelligent » se résout peu à peu, il restera alors à résoudre la question éthique des algorithmes, afin de quantifier leur impact sociétal et politique.

Waleed Mouhali
Enseignant-chercheur en Physique,
ECE Paris

Waleed Mouhali ne travaille pas, ne conseille pas, ne possède pas de parts, ne reçoit pas de fonds d'une organisation qui pourrait tirer profit de cet article, et n'a déclaré aucune autre affiliation que son organisme de recherche.

Publié le 6 février 2022 sur The Conversation, l'expertise universitaire, l'exigence journalistique.
https://theconversation.com/quest-ce-quun-algorithme-quantique-175707

Cet article est sous licence Creative Commons (selon la juridiction française = Paternité - Pas de Modification). http://creativecommons.org/licenses/by-nd/2.0/fr/

NOTES

[1] https://theconversation.com/quest-ce-quun-algorithme-162896

[2] https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

[3] https://www.youtube.com/watch?v=Rj3jTw2DxXQ

[4] https://arxiv.org/abs/quant-ph/9508027

[5] https://arxiv.org/pdf/quant-ph/9711070.pdf