Dans ce dossier au long cours sur la programmation, nous sommes progressivement descendus à des niveaux de plus en plus primitifs, de plus en plus fondamentaux du réel. On s’est d’abord intéressé à l’être humain et à son langage. Puis avec la complexité, nous sommes descendus à l’échelle des collectifs, humains certes, mais aussi sociétés d’insectes ou phénomènes naturels et écologiques. Ensuite, nous avons encore grossi notre focale pour aborder la programmation des cellules et de l’ADN. Reste à attaquer le niveau le plus bas, celui de la structure de l’univers lui-même, ou plutôt du multivers, puisque nous dit-on, il n’y aurait pas qu’un seul univers…

Un peu de théorie

Voyons d’abord les principes de base qui fondent l’informatique quantique. Dans les ordinateurs classiques, les bits ne peuvent prendre que deux états : 0 ou 1. Mais au sein du monde quantique, les choses ne sont pas aussi binaires. Un atome, une particule peut être dans un état de superposition : être là ET ailleurs, tourner dans un sens ET dans l’autre… Être à la fois 0 ET 1, dans différentes proportions. Attention toutefois, au moment où l’on mesure cet état, l’objet quantique prend une valeur définie : il se trouve en un point unique, il tourne dans un seul sens, il est 0 OU 1, comme dans le monde « normal » de la physique classique. C’est le fameux paradoxe du « chat de Schrödinger ». L’animal est enfermé dans une boite dans laquelle se trouve une fiole de gaz toxique. Cette dernière peut s’ouvrir ou non, selon l’état d’un seul et unique atome radioactif, qui a une chance sur deux de se désintégrer. Logiquement l’animal a donc une chance sur deux de mourir. Mais tant qu’il n’y pas d’observateur, tant que la boite n’est pas ouverte, l’atome est simultanément en train de se désintégrer et de rester intact. La fiole est à la fois ouverte et fermée, et le chat à la fois mort et vivant.

C’est cette particularité que cherchent à utiliser les concepteurs d’ordinateurs quantiques. Les qubits, équivalents quantiques des bits, se trouvent non seulement en état de superposition, mais ils sont également intriqués (une autre spécificité de l’univers quantique), autrement dit, une fois mis en contact les uns avec les autres, ils s’influencent mutuellement.

Les choses sont déjà assez bizarres comme cela, mais elles le deviennent encore plus si on découvre la théorie cosmologique qui a inspiré l’idée de l’ordinateur quantique. C’est celle des « mondes multiples » de Hugh Everett. C’est en effet pour prouver l’existence d’un « multivers » ou, si l’on préfère, d’une infinité d’univers parallèles, que David Deutsch (dont nous reportions voilà peu les derniers travaux) a élaboré en 1985 le premier concept d’ordinateur quantique (Richard Feynman en avait toutefois déjà évoqué l’idée).

Dans la théorie des mondes multiples, la problématique du chat de Schrödinger n’existe pas ; le chat n’est pas à la fois mort et vivant. Il y a un, ou plutôt des univers, où le chat est vivant. Et d’autres où le chat est mort. Lorsqu’on ouvre la boite, on sait seulement dans quel type d’univers on se trouve.

Évidemment cela peut sembler une thèse très extrême, mais est elle tellement plus absurde, que l’interprétation de Copenhague, plus classique, qui spécifie qu’un événement quantique ne quitte son état de superposition qu’en présence d’un mystérieux « observateur » ?

Dans son livre L’étoffe de la réalité, Deutsch affirme que : « le calcul quantique est la première en date des technologies permettant d’effectuer des tâches utiles en collaboration avec des univers parallèles. Un ordinateur quantique sera capable de distribuer les diverses parties d’une tâche complexe entre plusieurs univers parallèles puis de mettre en commun les résultats obtenus. » La première en date ? On se demande à quoi vont ressembler les autres !

Une autre logique

Ce qu’il faut comprendre lorsqu’on aborde l’informatique quantique, c’est qu’on ouvre la porte à une nouvelle logique, et donc à des algorithmes d’un tout nouveau genre.

Ainsi, même les bases de l’informatique, les fameuses instructions logiques (le ET, le OU, le NON) sont complétées par des variantes strictement quantiques. Par exemple, il existe une « racine carrée de NON ». En logique classique, il n’y a qu’une opération à faire pour passer d’un état à sa négation. De VRAI on peut passer à FAUX, de 1 à 0, etc. Mais en informatique quantique il faut deux étapes pour passer d’une chose à son opposé. C’est ce stade intermédiaire qu’on appelle la racine carrée du NON.

Grâce à cette nouvelle logique, il devient possible de créer de nouveaux algorithmes, irréalisables de manière classique : c’est le cas de l’algorithme de Shor, qui concerne la factorisation des grands nombres, ou celui de Grover, qui optimise la recherche au sein d’une large palette de possibilités.

Pour David Deutsch, la capacité à factoriser des grands nombres pourrait constituer une preuve supplémentaire de l’existence du multivers. En effet, explique-t-il, pour factoriser un nombre de 250 chiffres, l’ordinateur quantique devrait effectuer en parallèle 10⁵⁰⁰ calculs simultanés. Or notre univers ne contient que 10⁸⁰ atomes. « Si donc l’univers visible couvrait toute l’étendue de la réalité physique« , écrit Deutsch dans son livre, « la réalité physique ne contiendrait même pas les moyens nécessaires à la factorisation d’un nombre aussi grand. Qui a effectué la factorisation, dans ce cas ? Où et quand le calcul a-t-il été effectué ? » En effet, le monde de l’informatique n’est pas celui des mathématiques. Le calcul ne s’effectue pas dans un univers platonicien abstrait, mais doit bien être stocké quelque part !

A quoi serviraient les ordinateurs quantiques ? Essentiellement à mener en parallèle de multiples tâches. Un qubit possédant plusieurs états à la fois, on peut mener de front une multitude de calculs. Et comme ces qubits sont intriqués, il est également possible d’avoir au final, lorsqu’on ouvre la boîte (donc qu’il y a une « mesure », un observateur »), une seule et unique solution au problème posé. L’une des premières applications du calcul quantique serait ainsi, grâce à l’algorithme de Shor, de casser les codes cryptographiques en usage aujourd’hui.

Mais toutes les opérations en parallèle ne bénéficient pas du même traitement. Par exemple, dans le cas d’un ordinateur joueur d’échecs, on est bel et bien face à un programme recherchant parmi une multitude de possibilités : le logiciel traverse une base de données composée d’un nombre important de coups envisageables.

Ainsi, nous explique John Gribbin dans son livre Computing with Quantum Cats, il existe 10¹²⁰ parties d’échecs différentes. Cela devrait donc être pain bénit pour l’algorithme de Grover ! Mais une telle opération ne bénéficie que marginalement d’un calcul quantique, continue Gribbin, car, ainsi que l’a démontré Richard Cleve, professeur à l’université de Waterloo au Canada, l’algorithme de Grover n’est pas si efficace lorsque, comme au jeu d’échecs, il n’existe à chaque étape qu’un nombre limité de coups possibles (par exemple, en début de partie, il n’y en a que vingt : c’est-à-dire seize pour les pions avançant de une ou deux cases, et quatre pour les cavaliers). Cela ne signifie pas qu’un jour on ne trouvera pas un nouvel algorithme quantique capable d’optimiser le jeu d’échecs, mais en tout cas ce ne sera pas celui de Grover.

Comment programmer un ordinateur quantique ?

La réponse est simple : aujourd’hui vous ne pouvez pas, à moins de travailler dans le saint des saints de compagnies comme D-Wave ou Google.

Mais il reste néanmoins possible de s’initier à la logique quantique à l’aide d’un « simulateur » tournant sur une machine « classique ». Évidemment d’un point de vue strictement pragmatique, cela ne sert à rien : par définition, un tel simulateur classique sera infiniment plus lent qu’un « vrai » ordinateur quantique, mais au moins il peut servir à comprendre une forme de pensée qui sera – peut-être – fondamentale au cours de ce siècle, et on ne s’y prend jamais assez à l’avance !

Il y a quelques mois, Google a fait grand bruit en proposant un simulateur d’ordinateur quantique basé sur un langage particulier, le qscript, et doté d’une belle interface 3D en Webgl. L’info a fait rapidement le tour du web. Ce qui est assez injuste, car franchement à moins d’être déjà un expert en informatique quantique et de deviner le sens des exemples fournis, je ne vois pas comment on pourrait y comprendre quelque chose : aucun manuel de qscript, un tutoriel spartiate limité à la description de l’interface, c’est tout ce qu’on a à se mettre sous la dent. Si cela n’avait pas été une production Google, personne n’en aurait parlé. On ne prête qu’aux riches.

Parce que des simulateurs d’ordinateurs quantiques, il y en a d’autres. Par exemple, QCL existe depuis plusieurs années. Il est accompagné d’une documentation assez conséquente, mais pas forcément très compréhensible pour un « newbie ». Quipper est un autre langage qui a suscité l’intérêt. Là encore, il n’est pas réservé aux débutants.

Dans un article d’American Scientist, Brian Hayes expose de manière (assez) claire les difficultés liées à la programmation quantique, et montre comment QCL et Quipper ont implémenté différentes solutions.

On l’a vu, les qubits sont à la fois dans un état superposé et intriqué. Cela induit plusieurs contraintes, la première est qu’il est impossible d’interférer avec le calcul (et donc le mesurer) sans l’interrompre du même coup. Conséquence : les deux briques de la programmation classique, l’instruction IF (SI la condition X est remplie, alors exécuter Y) ou la boucle FOR ou WHILE (exécuter Y tant que la condition X est – ou n’est pas – remplie) sont indisponibles. Voilà qui est un peu gênant pour un programmeur classique ! Il y a encore d’autres contraintes, comme par exemple l’impossibilité de copier le contenu d’un qubit ou le fait qu’une opération doive toujours être réversible ; par exemple, nous dit Hayes, l’addition 3 + 4 = 7 n’est pas réversible. Une fois qu’on a 7, il est impossible de savoir qu’on l’a obtenu en faisant 3 + 4, et non 5 + 2 ou 8 – 1…

Comment donc créer un langage de programmation dans ces conditions ? Pour Hayes, QCL et Quipper ont choisi deux voies différentes. Le premier travaille de façon classique, avec ses boucles, ses conditions, jusqu’au moment où l’on demande une opération qui peut avoir sa solution de manière quantique. L’ordinateur quantique, écrit Hayes, apparaît donc comme un « oracle » qu’on interroge à partir d’une machine classique. Quipper, lui, est un langage fonctionnel. Ses instructions s’apparentent plus aux mathématiques qu’à un langage de programmation classique. Quipper « compile » le programme et produit un « circuit  » constitué de portes logiques quantiques.

« Je trouve gentiment ironique« , s’amuse Hayes, « que ces machines d’avant-garde nous ramènent à l’époque où l’on concevait des programmes comme des circuits, dans lesquels des signaux circulent à travers des chaînes de portes. Dans les années 40, on programmait ENIAC de la même manière, en branchant des câbles sur des panneaux. » Mais continue-t-il, il y a une différence : « Nous possédons maintenant des outils (tels que QCL et Quipper) qui génèrent automatiquement ces circuits à partir d’un texte écrit en code source de haut niveau. »

A noter que ni QCL ni Quipper ne sont compatible avec la technologie développée par la fameuse société D-Wave, dont nous avons déjà parlé à plusieurs reprises.

Si tout cela vous passe un peu au-dessus de la tête, vous pouvez quand même contribuer aux progrès de l’informatique quantique en contribuant à des projets de citizen science, qui, à l’instar de Foldit, permettent à tout un chacun d’aider les chercheurs.

Quantum Moves cherche à construire un meilleur ordinateur quantique, en s’amusant à bouger des atomes virtuels de manière optimale. Cela semble très prometteur, mais hélas, lorsqu’on arrive ces jours-ci sur la page d’accueil, on apprend qu’une nouvelle version est en cours d’élaboration, et l’on ne nous propose qu’une ancienne mouture à télécharger en local.

Dans la même veine, MeQuaniq est développé à l’université de Tokyo. Ce jeu en version beta propose divers puzzles représentant des algorithmes quantiques. Les concepteurs espèrent qu’avec l’aide des internautes, (quand le jeu sera véritablement crowdsourcé), on pourra un jour bâtir un ordinateur quantique optimisé utilisant le moins de ressources possibles.

Tout le monde veut son ordinateur quantique !

Où en est-on aujourd’hui ? Les ordinateurs quantiques existent, mais restent des outils de recherche, et leur performances sont loin d’être époustouflantes. Le gros problème consiste à permettre aux qubits de travailler sans interférence, c’est à dire sans aucun contact avec le monde extérieur. Plus on ajoute de qubits, plus ça devient difficile. Pendant longtemps, les ordinateurs quantiques expérimentaux n’ont pas réussi à aller plus loin que la factorisation du nombre 21. En 2012, une équipe chinoise a réussi la factorisation du nombre 143, et encore, le caractère quantique de leur opération reste contesté. D’un autre côté, la polémique D-Wave continue, divisant ceux qui sont convaincus du caractère révolutionnaire des travaux de cette compagnie (ainsi le site Next Big Future qui nous informe régulièrement avec enthousiasme, des progrès de ces machines), tandis que d’autres publient des papiers affirmant qu’un système D-Wave n’est en réalité pas capable d’aller plus vite qu’un ordinateur classique…

Malgré le flou concernant l’existence d’ordinateurs quantiques, cette technologie intéresse beaucoup de monde. Les agences gouvernementales au premier chef, à cause, vous l’aurez deviné, de l’algorithme de Shor, que Jonathan Dowling, physicien qui a beaucoup travaillé sur ces sujets en collaboration avec le département américain de la défense, nomme la « Schrödinger’s killer app » dans un livre paru sous le même titre. En 2014, on apprenait ainsi, suite aux révélations d’Edward Snowden, que la NSA travaillait sur un projet d’ordinateur quantique, dans le but de décrypter sans difficulté toutes les conversation codées.

Google n’est pas en reste. L’entreprise a acheté deux ordinateurs D-Wave, l’un en 2009 et l’autre en 2013. Mais alors que les doutes sur la technologie D-Wave continuent, Google ne veut manifestement pas mettre tous ses œufs dans le même panier. La compagnie a ainsi engagé récemment un spécialiste du domaine, John Martinis, afin de construire sa propre machine quantique, basée sur une technologie différente de celle de D-Wave. Scott Aaronson, un chercheur qui a toujours été sceptique sur les performances de D-Wave, applaudit l’arrivée de Martinis au sein de Google et note que, par ailleurs, ce chercheur est l’un des coauteurs d’un papier mettant en doute la supériorité des machines D-Wave sur les calculateurs classiques.

Microsoft, de son côté, cherche à construire un nouveau type de qubits qui permettrait, éventuellement, la première production de masse. On parle enfin, depuis la publication d’une étude parue en juillet dans Physical Review X, de l’avantage qu’auraient des « robots quantiques ». Ceux-ci pourraient se montrer plus créatifs, plus efficaces et bien sûr vous piquer votre job au passage. Pourquoi cela ? Tout simplement parce qu’un processeur quantique leur permettrait de faire des choix plus rapidement. En effet, peu importe qu’un robot calcule correctement le moyen d’éviter un obstacle s’il prend pour cela un temps bien trop long. Le calcul quantique, en accélérant leur réflexion, mettrait les robots plus en phase avec le monde réel.

Reste donc à savoir si les concepteurs de ces systèmes réussiront à contourner tous les problèmes liés à la mesure et à réaliser des machines capables d’aller plus loin que la factorisation du nombre 143, la limite qu’ont atteint aujourd’hui les ordinateurs quantiques… Du moins dans cet univers-là !

Rémi Sussan

Retrouvez le dossier L’avenir de la programmation :

• 1e partie : programmer, une activité culturelle ?
• 2e partie : la programmation pour les non-programmeurs
• 3e partie : programmer le langage naturel
• 4e partie : programmer la complexité
• 5e partie : programmer le vivant
• 6e partie : programmer le multivers