Sciences

D-Wave Two, l'ordinateur censément quantique, rate un test

ActualitéClassé sous :physique , ordinateur quantique , algorithme

Il y a un an, la société D-Wave Systems réussissait à vendre à Google ce qu'elle présentait comme un véritable calculateur quantique performant, malgré l'incrédulité à peu près générale de la communauté scientifique quant à la faisabilité même d'une telle machine. Une équipe de chercheurs a fait passé de nouveaux tests à D-Wave Two, sans pouvoir apporter la preuve qu'il était plus performant qu'un ordinateur classique.

La société canadienne D-Wave Systems commercialise des calculateurs prétendument quantiques. Deux générations de ces calculateurs utilisant un processeur avec des circuits quantiques supraconducteurs se sont succédé. © D-Wave Systems

Pour résoudre des problèmes de mathématique ou de physique avec un ordinateur, 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é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é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 quantiques.

Il y a un an, la Nasa 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 physicien 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 Lidar, 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 construction de circuits 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 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 mouvement 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 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 vitesse 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.