au sommaire
Pour résoudre des problèmes de mathématique ou de physique avec un ordinateurordinateur, par exemple trouver le PGCD de deux nombres entiers, calculer l'écoulement d'un fluide avec les équations de Navier-Stokes ou la conduction de la chaleur dans les parois d'Iter avec l'équation de Fourier, il faut mettre en œuvre des algorithmes. Rappelons qu'un algorithme est une suite finie d'opérations ou d'instructions permettant de résoudre un problème.
Le nom de cette suite honore la mémoire du mathématicienmathématicien perse Al-Khwarizmi (latinisé au Moyen Âge en algoritmi), qui, au IXe siècle écrivit le premier ouvrage systématique sur la solution des équations linéaires et quadratiques. Il est parfois considéré comme le père de l'algèbre bien qu'il n'ait pas été le premier à utiliser ce que l'on appelle aujourd'hui un algorithme.
Claude Aslangul, en compagnie de Richard Taillet, est interrogé par les éditions De Boeck. Dans cette vidéo, il répond aux questions : pourquoi la décohérence est-elle un obstacle à la fabrication d'un ordinateur quantique ? quelle est la différence entre un ordinateur quantique et un classique ? © Éditions De Boeck, YouTube
Le problème de la complexité algorithmique
Plus le nombre d'opérations nécessaires à l'exécution d'un algorithme est grand, plus il faudra de temps à un ordinateur pour le terminer. Il est donc important de pouvoir estimer cette durée et finalement, si cela se révèle possible et utile, de changer d'algorithme pour en utiliser un plus rapide. Toutefois, le temps d'exécution n'est pas le seul paramètre à prendre en compte pour estimer l'efficacité d'un algorithme, il y a aussi la question de l'espace mémoire nécessaire. Ces questions sont abordées en informatique par la théorie de la complexité algorithmique.
Elle étudie formellement les quantités de ressources (en temps et en espace) nécessaire pour la résolutionrésolution de problèmes au moyen de l'exécution d'un algorithme. Ainsi la complexité temporelle d'un algorithme est-elle reliée au nombre d'opérations élémentaires (affectations, comparaisons, opérations arithmétiques) effectuées par l'algorithme. Ce nombre s'exprime en fonction de la taille des données de départ que l'algorithme doit utiliser, par exemple celle d'un tableau avec n éléments à trier.
Or, pour certains problèmes, il existe des algorithmes bien plus économes, en temps ou en espace, sur un ordinateur quantique que sur un modèle classique, comme par exemple l'algorithme de Shor et celui de Glover. Il pourrait exister un grand nombre d'algorithmes de ce genre basés sur l'utilisation de qubits plutôt que de bits d'information classiques. C'est pour cette raison que l'on cherche activement de par le monde à développer des ordinateurs et des calculateurs quantiquescalculateurs quantiques.
Il y a un an, la NasaNasa et Google ont fait grand bruit en annonçant qu'il avait acheté un calculateur quantique de 512 qubits commercialisé par la société canadienne D-Wave Systems. Comme nous l'avions exposé plus en détail dans deux articles, la communauté scientifique se posait bien des questions sur la performance réelle de ce calculateur, nommé D-Wave two, et, pour dire la vérité, elle se montrait franchement sceptique. Comme nous l'expliquait le physicienphysicien Laurent Saminadayar, il était difficile de croire que D-Wave Systems avait vraiment réussi à contourner l'obstacle de la décohérence quantique en réussissant à mener des calculs avec 512 qubits alors que les laboratoires ne parviennent à travailler qu'avec une dizaine de qubits.
Le prix Nobel de physique Richard Feynman s'est intéressé à la réalisation d'ordinateurs quantiques au début des années 1980. Il est considéré comme un des pionniers de ce domaine. © Tamiko Thiel, Wikimedia Commons, cc by sa 3.0
Des algorithmes de recuit simulé pour l'optimisation
La polémique vient de rebondir avec un article publié dans Science mais en accès libre sur arxiv. Il expose les conclusions de tests qu'ont fait passer à la machine de D-Wave Systems Matthias Troyer, un physicien à l'Institut fédéral suisse de technologie de Zurich et Daniel LidarLidar, un physicien de l'université de Californie du Sud à Los Angeles, en compagnie de leurs collègues.
Pour comprendre ce test, il faut savoir que la machine n'est pas un ordinateur mais bien un calculateur quantique, qui ne peut pas être programmé pour effectuer n'importe quel algorithme. Il ne peut être utilisé que pour mettre en œuvre ceux dits de recuit simulé, des algorithmes d'optimisation utilisés par exemple pour la constructionconstruction de circuits intégréscircuits intégrés, le traitement des images et la résolution de problèmes de transports optimaux. Cela revient à trouver le minimum d'une fonction interprétée comme l'énergie d'un système physique.
Cette énergieénergie peut par exemple prendre la forme d'une surface et l'état d'énergie minimale cherché sera celui d'une bille ayant réussi à atteindre une position d'équilibre dans la cuvette la plus profonde. Pour la trouver un algorithme de recuit simulé classique considérera en quelque sorte des fluctuations thermiques faisant effectuer une sorte de mouvementmouvement brownien à la bille pour qu'elle explore toute la surface d'énergie. En utilisant des qubits quantiques pour traiter le problème, les lois de la mécanique quantiquemécanique quantique permettent, en théorie, de trouver cette cuvette bien plus rapidement.
Or, dans les problèmes simples de recuits simulés qui ont été soumis à la machine de D-Wave Systems, le temps de résolution des problèmes en fonction du nombre d'opérations utilisés a augmenté de la même façon qu'avec des algorithmes classiques, de sorte qu'aucune augmentation de la vitessevitesse de calcul n'a été observée. Bien sûr, absence de preuve n'est pas preuve de l'absence et il se peut que les problèmes particuliers de recuits simulés dans ces tests ne permettent finalement pas de tirer parti de la mécanique quantique pour les résoudre plus vite. Mais les sceptiques peuvent continuer à dire qu'il n'y a toujours aucune preuve que D-Wave Two soit réellement un calculateur quantique.
