{"id":16111,"date":"2018-07-20T07:09:04","date_gmt":"2018-07-20T06:09:04","guid":{"rendered":"http:\/\/www.oezratty.net\/wordpress\/?p=16111"},"modified":"2019-02-10T19:44:05","modified_gmt":"2019-02-10T18:44:05","slug":"comprendre-informatique-quantique-algorithmes-et-applications","status":"publish","type":"post","link":"https:\/\/www.oezratty.net\/wordpress\/2018\/comprendre-informatique-quantique-algorithmes-et-applications\/","title":{"rendered":"Comprendre l’informatique quantique – algorithmes et applications"},"content":{"rendered":"

Maintenant que nous avons d\u00e9soss\u00e9 un ordinateur quantique<\/a> avec ses qubits, ses registres, ses portes et son frigo, voyons-donc comment on peut exploiter cette belle quincaillerie. L\u2019ordinateur quantique utilise des algorithmes dits quantiques qui ont la particularit\u00e9 d\u2019\u00eatre bien plus efficaces que leurs \u00e9quivalents con\u00e7us pour des ordinateurs traditionnels. Mais ces algorithmes ne sont pas tr\u00e8s nombreux et leur performance relative aux algorithmes traditionnels pas toujours \u00e9vidente \u00e0 prouver. Elle est m\u00eame parfois contest\u00e9e.<\/p>\n

Richard Feynman <\/strong>avait d\u00e9crit l\u2019id\u00e9e de cr\u00e9er des simulateurs quantiques en 1982 dans Simulating Physics with Computers<\/a> (22 pages). Son id\u00e9e consistait \u00e0 cr\u00e9er des dispositifs exploitant les effets de la m\u00e9canique quantique pour les simuler tandis que cette simulation serait quasiment impossible avec des ordinateurs traditionnels. Cela correspond aujourd\u2019hui \u00e0 l\u2019un des usages des ordinateurs quantiques, comprenant notamment la simulation des interactions atomiques dans des structures inertes ou biologiques. On peut m\u00eame faire la distinction entre simulateurs quantiques analogiques et simulateurs quantiques num\u00e9riques, \u00e0 base de qubits et de portes quantiques.<\/p>\n

Des math\u00e9maticiens planchent depuis le milieu et la fin des ann\u00e9es 1980 sur la cr\u00e9ation d\u2019algorithmes adapt\u00e9s aux simulateurs et ordinateurs quantiques, bien avant que l\u2019on en ait vu l\u2019ombre de la couleur. Les premiers algorithmes quantiques ont \u00e9t\u00e9 publi\u00e9s au d\u00e9but des ann\u00e9es 1990 et les chercheurs en cr\u00e9ent r\u00e9guli\u00e8rement de nouveaux depuis 25 ans. Le Quantum Algorithm Zoo<\/a> en identifie une soixantaine dans la litt\u00e9rature scientifique ! C\u2019est un nombre encore modeste au regard des algorithmes non quantiques qui se comptent en milliers.<\/p>\n

Leur cr\u00e9ation est un travail de recherche parall\u00e8le avec la partie mat\u00e9rielle des ordinateurs quantiques. Ce n\u2019est pas la premi\u00e8re fois dans l\u2019Histoire qu\u2019il en est ainsi. L\u2019embl\u00e9matique Ada Lovelace <\/strong>planchait sur la cr\u00e9ation des premiers algorithmes et lignes de code devant tourner sur la machine de Charles Babbage<\/strong>, qui ne vit jamais le jour. Elle avait annot\u00e9 en 1842\/1843 une traduction de son cru d\u2019un papier de l\u2019Italien Luigi Federico Menabrea <\/strong>qui d\u00e9crivait la machine de Babbage. Il fallut attendre 102 ans pour que les premiers ordinateurs voient le jour \u00e0 la fin de la seconde guerre mondiale ! Cela rappelle dans un autre domaine les dessins d\u2019h\u00e9licopt\u00e8res de L\u00e9onard de Vinci <\/strong>qui datent de 1487-1490. Un premier h\u00e9licopt\u00e8re propuls\u00e9 par l\u2019\u00e9nergie humaine et cr\u00e9\u00e9 par l\u2019Universit\u00e9 de Toronto a vol\u00e9 en 2013, AeroVelo (vid\u00e9o<\/a>) suivi d\u2019un autre sp\u00e9cimen assez voisin issu de l\u2019Universit\u00e9 de Maryland qui vient tout juste de voler en 2018 (vid\u00e9o<\/a>) ! Donc, avec plus de cinq si\u00e8cles de d\u00e9calage ! Cette m\u00eame Universit\u00e9 de Maryland est d\u2019ailleurs l\u2019une des plus en pointe dans le monde dans les ordinateurs quantiques \u00e0 base d\u2019ions pi\u00e9g\u00e9s ! Comme quoi !<\/p>\n

\"Programme<\/a><\/p>\n

Apr\u00e8s-guerre, l\u2019Histoire se r\u00e9p\u00e9ta en partie pour nombre de travaux du vaste champ de l\u2019intelligence artificielle, o\u00f9 les chercheurs planchaient \u00e9galement sur des algorithmes, notamment \u00e0 base de r\u00e9seaux de neurones, avant que les ordinateurs puissent les ex\u00e9cuter convenablement. L\u2019essor du deep learning depuis 2012 est en partie li\u00e9 \u00e0 la puissance des machines et des GPU \u00e0 m\u00eame d\u2019entra\u00eener de tels r\u00e9seaux de neurones. Le mat\u00e9riel a une fois encore rejoint les algorithmes qui \u00e9taient en avance sur leur temps.<\/p>\n

Aujourd\u2019hui, une bonne part des algorithmes quantiques qui sont invent\u00e9s ne sont pas encore ex\u00e9cutables sur les ordinateurs quantiques disponibles ni m\u00eame sur des simulateurs quantiques \u00e0 base d\u2019ordinateurs traditionnels. Les qubits sont disponibles dans un nombre bien trop faible pour qu\u2019ils servent \u00e0 quelque chose et surtout, qu\u2019ils soient plus performants que des ordinateurs traditionnels. Les supercalculateurs \u00e9mulent difficilement plus de 50 qubits.<\/p>\n

Comme dans le pass\u00e9 de l\u2019Histoire de l\u2019informatique, nous en sommes dans le quantique \u00e0 naviguer dans les couches basses du logiciel. Un peu comme pour les programmeurs en langage machine ou en assembleur d\u2019il y a 30 \u00e0 50 ans. Les algorithmes quantiques sont les couches les plus basses des solutions logicielles qui restent \u00e0 inventer puis \u00e0 assembler. Les algorithmes quantiques exploitent les portes quantiques que nous avons vues dans la partie pr\u00e9c\u00e9dente<\/a>.<\/p>\n

La cr\u00e9ation d\u2019algorithmes quantiques requiert une capacit\u00e9 d\u2019abstraction sans commune mesure avec celle des algorithmes et programmes traditionnels. Une nouvelle g\u00e9n\u00e9ration de math\u00e9maticiens et d\u00e9veloppeurs capables de raisonner en mode quantique devra se d\u00e9velopper au gr\u00e9 de la maturation des ordinateurs quantiques. Ils devront \u00eatre capables de conceptualiser des algorithmes qui ne sont pas faciles \u00e0 se repr\u00e9senter physiquement. Qui plus est, ces algorithmes devront aussi, c\u2019est la moindre des choses, \u00eatre bien plus efficaces que leurs \u00e9quivalents pour ordinateurs traditionnels ou supercalculateurs.<\/p>\n

L’ambigu\u00eft\u00e9 de la supr\u00e9matie quantique<\/strong><\/p>\n

Avant de rentrer dans le d\u00e9tail des algorithmes quantiques, il nous faut expliquer la signification de la notion de \u201csupr\u00e9matie quantique\u201d qui commence \u00e0 fleurir dans la communication de certains acteurs tels que Google. C\u2019est un terme un peu galvaud\u00e9 dont vous entendrez parler dans diverses annonces tonitruantes \u00e0 venir.<\/p>\n

Voir par exemple New twists in the road to quantum supremacy<\/a> et Google\u2019s new chip is a stepping stone to quantum computing supremacy<\/a> publi\u00e9s dans la s\u00e9rieuse MIT Technology Review en 2017. L\u2019appellation a \u00e9t\u00e9 invent\u00e9e en 2011 par l\u2019Am\u00e9ricain John Preskill dans sa communication au Congr\u00e8s de Solvay de cette ann\u00e9e-l\u00e0, d\u00e9crite dans Quantum Computing and the Entanglement Frontier<\/a>.<\/p>\n

\"Quantum<\/a><\/p>\n

Une \u201csupr\u00e9matie quantique\u201d est atteinte lorsqu\u2019un algorithme traitant un probl\u00e8me donn\u00e9\u00a0n’est ex\u00e9cutable\u00a0que\u00a0sur un ordinateur quantique,\u00a0<\/span>ce probl\u00e8me ne\u00a0pouvant\u00a0pas \u00eatre r\u00e9solu\u00a0m\u00eame sur le plus puissant des supercalculateurs. De nombreux sp\u00e9cialistes affirment que le seuil de 50 qubits de qualit\u00e9 pur porc – avec un faible taux d\u2019erreurs et un long temps de d\u00e9coh\u00e9rence – constituera une \u00e9tape cl\u00e9 de l\u2019atteinte de cette supr\u00e9matie quantique.<\/p>\n

Mais cette appellation n\u2019est pas absolue. Elle ne signifiera pas qu\u2019un ordinateur quantique donn\u00e9 est supr\u00eamement plus puissant que tous les supercalculateurs du moment. C\u2019est une appellation qui devra \u00eatre utilis\u00e9e au cas par cas avec des couples d\u2019algorithmes quantiques et d\u2019ordinateurs quantiques, et avec des tests r\u00e9alis\u00e9s s\u00e9rieusement avec le meilleur possible des algorithmes adapt\u00e9s aux supercalculateurs sachant que celui-ci est aussi mouvant.<\/p>\n

Certains benchmarks de D-Wave et Google r\u00e9alis\u00e9s en 2015 et montrant la sup\u00e9riorit\u00e9 de la solution quantique (dite adiabatique ou \u00e0 recuit quantique) ont \u00e9t\u00e9 ensuite contredits par la cr\u00e9ation d\u2019algorithmes optimis\u00e9s pour des supercalculateurs. Bref, cette supr\u00e9matie quantique naviguera dans un premier temps dans des sables mouvants.<\/p>\n

\"Suppremation<\/a><\/p>\n

Elle interviendra certainement d\u2019ici quelques ann\u00e9es pour quelques algorithmes qui ne peuvent avoir d\u2019\u00e9quivalents optimis\u00e9s pour les supercalculateurs. Voir \u00e0 ce sujet Quantum Algorithms Struggle Against Old Foe: Clever Computers<\/a> de Ariel Bleicher (f\u00e9vrier 2018) qui rappelle \u00e0 juste titre que les supercalculateurs et ceux qui les exploitent n\u2019ont pas dit leur dernier mot et cherchent aussi \u00e0 am\u00e9liorer leurs propres algorithmes. A long terme, le quantique supplantera certainement les supercalculateurs pour un grand nombre d\u2019algorithmes.<\/p>\n

Il semblerait sinon que les limitations des supercalculateurs pour simuler des algorithmes quantiques rel\u00e8vent plus de leur m\u00e9moire vive que de leur capacit\u00e9 de traitement. Il faudrait 10 Po de m\u00e9moire pour simuler 48 qubits. Quand on arrive \u00e0 50 qubits, on d\u00e9passe la capacit\u00e9 m\u00e9moire des supercalculateurs d\u2019aujourd\u2019hui. Si on passe \u00e0 96 qubits, la m\u00e9moire n\u00e9cessaire pour simuler l\u2019ensemble sur supercalculateur est multipli\u00e9e par 2 puissance 48. Bref, la loi de Moore de la m\u00e9moire ne peut pas suivre le rythme d\u2019une augmentation lin\u00e9aire du nombre de qubits align\u00e9s dans un ordinateur quantique.<\/p>\n

Il faudra se m\u00e9fier des annonces des IBM et autres Google lorsqu\u2019ils pr\u00e9tendront avoir atteint cette supr\u00e9matie quantique. Quand Google communiquait en mars 2018 sur la cr\u00e9ation d\u2019un ordinateur quantique de 72 qubits, donc bien au-del\u00e0 de 50 qubits, il se gardait bien de pr\u00e9ciser le temps de coh\u00e9rence de l\u2019ensemble ainsi que du niveau du bruit g\u00e9n\u00e9r\u00e9, sans compter le fait qu\u2019il n\u2019avait pas encore \u00e9t\u00e9 benchmark\u00e9 avec un algorithme donn\u00e9. Sans ces informations, une annonce d\u2019ordinateur quantique reste du vent !<\/p>\n

Il faut donc attendre d\u2019avoir des \u00e9l\u00e9ments d\u2019informations complets pour juger, comme l\u2019indiquent fort bien Cristian et Elena Calude de l\u2019Universit\u00e9 d\u2019Auckland en Nouvelle Z\u00e9lande dans The road to quantum computing suppremacy<\/a> publi\u00e9 fin 2017. Ils arguent aussi du fait que l\u2019on compare une limite haute de performance, celle d\u2019un ordinateur quantique pr\u00e9cis, \u00e0 une limite basse qui est la meilleure performance dans la r\u00e9solution du m\u00eame probl\u00e8me dans un supercalculateur. Or, il est plus facile de d\u00e9montrer qu\u2019un truc existe que son inexistence.<\/p>\n

Une supr\u00e9matie quantique est donc un comparable entre l\u2019existence d\u2019une performance quantique et la supposition de la non existence d\u2019une performance \u00e9quivalente dans le non quantique. Les auteurs rappellent aussi un crit\u00e8re qui manque parfois \u00e0 l\u2019analyse : il vaudrait mieux que l\u2019algorithme test\u00e9 serve \u00e0 quelque chose ! Ce qui n\u2019est pas toujours \u00e9vident avec les algorithmes quantiques comme nous le verrons plus loin.<\/p>\n

Usages des applications quantiques<\/strong><\/p>\n

Avant de rentrer dans le lard des algorithmes quantiques, faisons un d\u00e9tour de leur utilit\u00e9 pratique connue \u00e0 ce jour.<\/p>\n

Je les ai organis\u00e9s ci-dessous en trois niveaux verticaux : les fonctions de base, les algorithmes puis les applications concr\u00e8tes. Tout ceci rel\u00e8ve encore largement de la prospective car nombre de ces solutions demanderont des puissances en termes de nombre et de qualit\u00e9 de qubits qui ne seront pas disponibles avant plusieurs ann\u00e9es voire d\u00e9cennies.<\/p>\n

Dans un ordre vaguement chronologique, nous aurons tout d\u2019abord des applications d\u2019algorithmes de recherche et d\u2019optimisation bas\u00e9s sur les \u00e9quations lin\u00e9aires en g\u00e9n\u00e9ral sachant que tous les algorithmes quantiques reposent sur des \u00e9quations lin\u00e9aires. On peut y caser les solutions de r\u00e9solution de probl\u00e8mes complexes, comme la d\u00e9termination du parcours optimal d\u2019un commercial, un sujet bien connu. Sa variante est la solution d\u2019optimisation du trafic individuel de nombreux v\u00e9hicules dans une ville en tenant compte de l\u2019ensemble des trajets planifi\u00e9s pour chacun d\u2019entre eux.<\/p>\n

Cette cat\u00e9gorie de solutions comprend aussi l\u2019acc\u00e9l\u00e9ration de l\u2019entra\u00eenement des r\u00e9seaux de neurones du deep learning. L\u2019avantage par rapport aux techniques existantes s\u2019appuyant sur des processeurs neuromorphiques n\u2019est pas encore \u00e9vidente et d\u00e9montr\u00e9e. Qui plus est, la faisabilit\u00e9 de ces r\u00e9seaux de neurones est \u00e9tablie sur architectures traditionnelles, \u00e0 base de GPUs comme ceux de Nvidia ou de TPU (Tensor Processing Units) comme ceux de Google, sans compter les processeurs \u00e0 base de memristors qui sont encore au stade du laboratoire.<\/p>\n

En second lieu, dans le vaste champ de la simulation quantique, nous aurons d\u2019abord des applications dans la chimie et la physique des mat\u00e9riaux pour simuler les interactions entre atomes dans mol\u00e9cules et structures cristallines, qui d\u00e9pendent elles-m\u00eames des lois de la m\u00e9canique quantique. Cela servira si tout va bien \u00e0 inventer de nouvelles solutions comme des batteries plus efficaces, chargeables plus rapidement et avec une plus grande densit\u00e9 \u00e9nerg\u00e9tique, des proc\u00e9d\u00e9s chimiques de captation du carbone ou de fixation de l\u2019azote, ainsi que la cr\u00e9ation de mat\u00e9riaux supraconducteurs \u00e0 temp\u00e9rature ambiante. Ce sont des hypoth\u00e8ses non encore valid\u00e9es \u00e0 savoir que les algorithmes quantiques compl\u00e9t\u00e9s d\u2019ordinateurs quantiques bien dimensionn\u00e9s avec des centaines de qubits logiques seront \u00e0 m\u00eame de permettre aux chercheurs d\u2019avancer dans ces domaines-l\u00e0.<\/p>\n

\"Grandes<\/a><\/p>\n

En dernier lieu et avec des quantit\u00e9s de qubits bien plus importantes, donc \u00e0 plus lointaine \u00e9ch\u00e9ance, la simulation quantique pourra \u00e9ventuellement passer \u00e0 la simulation de mol\u00e9cules biologiques. Cela commencera avec celle de peptides, puis de polypeptides, et enfin, de prot\u00e9ines et d\u2019enzymes. Les mol\u00e9cules biologiques ont la particularit\u00e9 d\u2019\u00eatre tr\u00e8s complexes, avec des structures pouvant atteindre des dizaines de milliers d\u2019atomes. Le top du top serait la capacit\u00e9 \u00e0 simuler l\u2019assemblage puis le fonctionnement d\u2019un ribosome, qui fait plus de 100 000 atomes. C\u2019est la structure mol\u00e9culaire la plus magique du vivant, celle qui assemble les acides amin\u00e9s pour construire les prot\u00e9ines \u00e0 partir du code de l\u2019ARN messager issu de la transposition de l\u2019ADN des g\u00eanes. Suivrait alors la simulation du fonctionnement d\u2019une cellule enti\u00e8re. Mais l\u00e0, on est \u00e0 la fronti\u00e8re de la science-fiction, m\u00eame en \u00e9tant tr\u00e8s optimiste sur l\u2019informatique quantique !<\/p>\n

Mon sch\u00e9ma est une version simplifi\u00e9e d\u2019un \u00e9quivalent trouv\u00e9 dans un rapport du Gartner Group<\/a> de fin 2017, ci-dessous<\/em>.<\/p>\n

\"Schema<\/a><\/p>\n

Principes de base<\/strong><\/p>\n

Comme nous l\u2019avons vu dans la partie pr\u00e9c\u00e9dente qui d\u00e9crit la structure d\u2019un ordinateur quantique, un algorithme quantique va int\u00e9grer \u00e0 la fois la partie initialisation des donn\u00e9es puis celle des calculs et enfin de la mesure du r\u00e9sultat. Elle s\u2019appliquera \u00e0 un registre de n qubits qui sont physiquement initialis\u00e9s \u00e0 z\u00e9ro, puis modifi\u00e9s par des portes quantiques.<\/p>\n

Le r\u00e9sultat correspond \u00e0 la mesure de l\u2019\u00e9tat de ces m\u00eames qubits \u00e0 la fin de l\u2019ex\u00e9cution de l\u2019algorithme. Si le r\u00e9sultat recherch\u00e9 est purement binaire (0 ou 1 par qubits), le cycle ne sera ex\u00e9cut\u00e9 qu\u2019une seule fois. Si le r\u00e9sultat est une probabilit\u00e9 de 0 et de 1 pour chaque qubits, alors, il faudra r\u00e9p\u00e9ter de nombreuses fois le cycle initialisation-algorithme-mesure et faire une moyenne des 0 et des 1 obtenu pour chaque qubit et obtenir un nombre flottant compris entre 0 et 1.<\/p>\n

L\u2019algorithme doit \u00eatre compatible avec les caract\u00e9ristiques de l\u2019ordinateur quantique. Les principales sont le temps de coh\u00e9rence et la dur\u00e9e d\u2019ex\u00e9cution des portes quantiques. Le nombre de portes quantiques \u00e0 ex\u00e9cuter devra permettre d\u2019ex\u00e9cuter l\u2019algorithme dans un temps inf\u00e9rieur au temps de coh\u00e9rence au bout duquel les qubits perdront leur \u00e9tat de superposition. Cette v\u00e9rification est g\u00e9n\u00e9ralement r\u00e9alis\u00e9e par les compilateurs de code quantique. Elle devra tenir compte des codes de correction d\u2019erreurs qui sont souvent mis en \u0153uvre sous la forme de sous algorithmes pr\u00e9fabriqu\u00e9s int\u00e9gr\u00e9s dans l\u2019algorithme \u201cm\u00e9tier\u201d cr\u00e9\u00e9 par le d\u00e9veloppeur.<\/p>\n

Il en va de m\u00eame des portes quantiques utilis\u00e9es dans les outils de d\u00e9veloppement. Certaines portes quantiques, notamment s\u2019appliquant sur deux ou trois qubits, sont utilis\u00e9es par les d\u00e9veloppeurs mais seront converties par le compilateur en un jeu de portes quantiques universelles support\u00e9es par l\u2019ordinateur quantique. Cela va aussi multiplier le nombre de portes quantiques par rapport \u00e0 l\u2019algorithme initial. Dans la pratique,\u00a0 l\u2019ordinateur va donc ex\u00e9cuter un nombre de portes quantiques bien plus grand que l\u2019algorithme con\u00e7u par le d\u00e9veloppeur.<\/p>\n

L\u2019une des consid\u00e9rations importantes de la cr\u00e9ation d\u2019algorithmes quantiques est de s\u2019assurer qu\u2019ils sont plus efficaces que leurs \u00e9quivalents optimis\u00e9s pour des ordinateurs ou supercalculateurs traditionnels. Des th\u00e9ories permettent de v\u00e9rifier cela pour \u00e9valuer la mont\u00e9e en puissance exponentielle, polynomiale, quadratique ou logarithmique du temps de calcul en fonction de la taille du probl\u00e8me \u00e0 r\u00e9aliser, ou une combinaison des quatre. Mais rien ne remplace l\u2019exp\u00e9rience !<\/p>\n

Les grandes classes d\u2019algorithmes quantiques<\/strong><\/p>\n

Les algorithmes quantiques sont des applications pratiques de l\u2019alg\u00e8bre lin\u00e9aire, cette branche des math\u00e9matiques qui g\u00e8re des espaces vectoriels et des transformations lin\u00e9aires \u00e0 base de matrices. Elles sont appliqu\u00e9es dans des espaces \u00e0 deux dimensions, les vecteurs qui d\u00e9finissent les \u00e9tats de qubits. Leur manipulation s\u2019appuie sur des calculs matriciels qui permettent de modifier l\u2019\u00e9tat des qubits sans en lire le contenu. Leur lecture n\u2019intervient qu\u2019\u00e0 la fin des calculs. Cela rend difficile la programmation conditionnelle, du genre : faire tel calcul si tel r\u00e9sultat interm\u00e9diaire a telle valeur ou v\u00e9rifie telle condition. Mais les portes quantiques conditionnelles (CNOT & co) permettent d\u2019\u00e9muler ce genre de comportement dans un algorithme quantique.<\/p>\n

A ce jour, quatre principales cat\u00e9gories d’algorithmes quantiques sont disponibles et que nous d\u00e9taillerons plus loin :<\/p>\n