Lu dans un article récent du Monde.fr : "La NSA cherche à construire un ordinateur quantum (sic !)". J'imagine que l'auteur voulait parler d'ordinateur quantique... Qu'est-ce que la NAS peut bien vouloir faire d'un ordinateur quantique? Qu'est-ce qu'un ordinateur quantique?
Le concept d'ordinateur quantique est récent. Il a été évoqué en particulier par R.Feynman en 1982 par cette remarque : « Au lieu de nous plaindre que la simulation des phénomènes quantiques demande des puissances énormes à nos ordinateurs actuels, utilisons la puissance de calcul des phénomènes quantiques pour faire plus puissant que nos ordinateurs actuels ».
Levons tout de suite une ambiguïté : tous les ordinateurs que nous manipulons sont "quantiques". Ils fonctionnent tous en respectant les lois de la physique quantique. Le fonctionnement de tous leurs organes est conforme aux lois de la physique quantique. Mais alors, pourquoi parler d'ordinateur "quantique"?
Le terme "quantique" qualifie la façon de définir l'information traitée par l'ordinateur. Nos ordinateurs actuels, que je qualifierai de "classiques", traitent de l'information binaire, un bit vaut 1 ou 0. Et c'est là que réside la différence ! Un ordinateur quantique traite des informations qui n'ont plus rien de binaire !
Un ordinateur est une machine qui stocke et traite de l'information. Réduite à sa plus simple expression, ses fonctions fondemantales sont :
Ces fonctions se retrouvent dans tous les ordinateurs, classiques ou quantiques. La différence entre les deux types d'ordinateurs réside dans la nature de l'information, et elle est de taille!
Dans un ordinateur classique, un élement d'information est codé selon une logique binaire. Le bit, nom de cet élément d'information, peut prendre deux valeurs 0 ou 1. Pour mieux comprendre la suite, je vais utiliser une écriture un peu particulière de ce bit, que je vais nommer B.
Rappelez-vous la façon dont vous désignez un vecteur \(\vec{V}\) dans un plan muni d'un repère \( (O,\vec{i},\vec{j}) \). Vous vous souvenez, j'espère, que \( \vec{i} \) et \( \vec{j} \) forment une base qui permet d'écrire \( \vec{V} = a*\vec{i} + b*\vec{j} \), a et b étant les coordonnées du vecteur \( \vec{V} \).
Appliquons maintenant le même principe à l'écriture de B, en posant que 0 et 1 forment la base qui permet d'écrire B. On obtient B = a*0 + b*1. En logique binaire si a = 0 donc b = 1 et si a = 1 alors b = 0. B vaut donc 0 ou 1.
Parce que cela nous servira plus loin, je vais réécrire la définition de B en utilisant la notation en vigueur en physique quantique. J'écris B = a*|0> + b*|1> , |0> (on dit ket 0) et |1> (on dit ket 1) formant la base. Cette écriture décrit le "vecteur d'état" de B. J'insiste: ici a et b sont deux naturels, valant 0 ou 1 exclusivement. L'espace d'état de B comprend deux valeurs, 0 et 1.
Vous noterez que cette notation est inutile dans le cas de la logique classique, on aurait pu se contenter d'écrire B = b*|1>. Son utilité tient uniquement dans l'identité formelle avec la définition d'un qbit.
Pratiquement, dans un ordinateur classique, chaque élément d'information est stocké dans une mémoire. On se limitera ici pour nos besoins à la mémoire vive (la RAM). Très schématiquement, la RAM est formée d'une multitude (plusieurs milliards typiquement) de condensateurs microscopiques qui stockent des charges électriques. Le principe est fondamentalement simple: si le condensateur est chargé, alors on dit que le bit qu'il représente vaut 1. S'il est déchargé, le bit vaut 0. Bien sur, la réalisation technologique est un peu plus compliquée: il existe des tonnes de bouquins pour vous expliquer tout ça.... Vous pouvez deviner que lire et écrire un bit est en principe assez simple: pour écrire un bit, on charge ou décharge le condensateur, pour lire le bit, on mesure la tension aux bornes du condensateur.
Notons aussi que le phénomène est macroscopique: charger et décharger un condensateur même de capacité très faible (qq picofarad) mobilise un grand nombre d'électrons (faites le calcul...). On verra que l'ordinateur quantique travaille lui sur quelques objets quantiques (photons, atomes, molécules).
De même, il est assez simple, en principe, de disposer côte à côte un certain nombre de condensateurs sans que ceux-ci ne s'influencent.Encore que, vu le niveau d'intégration, cela devient de moins en moins vrai: imaginez plusieurs milliards de condensateurs sur quelques centimètres carrés, ce qu'est une puce mémoire de 4 ou 8 Go, courante dans nos PC. La taille des condensateurs devient si petite que les effets quantiques deviennent non négligeables voire prépondérants !
Tout le traitement de l'information dans un ordinateur classique est basé sur l'algèbre de Boole. Elle définit les opérations sur les bits. Vous connaissez certaines de ces opérations logiques, comme le ET logique (1 ET 1 = 1 , 1 ET 0 = 0, etc.) ou le OU logique (1 OU 1 = 1, 1 OU 0 = 1, etc.). Ces opérations sont effectuées dans les ordinateurs électroniques par des circuits relativement simples, que l'on appelle des portes. Aussi on retrouve des portes AND, NAND, NOR, du nom anglais des opérations qu'elles exécutent.
Pour effectuer le traitement d'une information, une chaine de caractères, une image, un nombre, celle-ci est transformée en suite de bits (c'est la numérisation) et le programme de traitement opére sur cette suite de bits selon l'algèbre de Boole. Bien sur, vous ne voyez rien de tout ça. Ces opérations sont masquées par les compilateurs, le système d'exploitation et tous les outils dont dispose l'informatique.
Parmi ces outils figure en très bonne place l'algorithmique, discipline mathématique qui permet de transformer un problème quelconque en suite d'opérations logiques de plus ou moins haut niveau. Or il se trouve que la quasi-totalité des algorithmes conçus aujourd'hui sont basés implicitement sur la logique binaire. Un seul exemple : lorsque vous faites un test dans une instruction IF condition THEN instruction1 ELSE instruction2 , vous n'envisagez que deux options: la variable condition vaut 0 ou 1. C'est le principe du tiers exclu, fondement de la logique formelle binaire : une variable vaut 1 ou 0, mais pas une valeur intermédiaire.
Nous allons voir que ce principe n'est plus directement applicable dans la logique d'un ordinateur quantique et donc que notre algorithmique est à revoir de fond en comble pour faire fonctionner un ordinateur quantique.
Une précision d'abord: on écrit Qubit ou Qbit ou encore qbit, selon les auteurs. Et l'on prononce kjubit, à l'anglaise. Pour ma part, je préfère l'orthographe "qbit", c'est plus simple!
Avant d'examiner les caractéristiques d'un qbit, il me semble indispensable de définir très succinctement, quelques termes que je vais utiliser:
La superposition et l'intrication sont les propriétés qui permettent d'envisager des calculs en parallèle avec des objets quantiques, ce qui fait la puissance d'un ordinateur quantique. La décohérence est un fléau contre lequel il va falloir lutter, du moins dans un ordinateur quantique !
Nous avons vu plus haut que l'on pouvait écrire qu'un bit classique est la combinaison linéaire de deux états 0 et 1. Une combinaison linéaire très pauvre parce qu'un bit ne peut prendre que deux états.
Un qbit lui peut prendre une infinité de valeurs entre 0 et 1. Formellement, si je reprends l'écriture employée pour un bit, je peux écrire la définition de l'état d'un qbit Φ par |Φ> = a*|0> + b*|1> . Mais dans le cas d'un qbit, a et b sont des nombres complexes, dont la valeur est telle que |a|2 + |b|2 = 1. En résumé, un bit porte une information qui peut prendre deux valeurs, 0 ou 1, alors qu'un qbit est associé à un état qui peut prendre une infinité de valeurs comprise entre 0 et 1 (inclus).
La nuance est de taille : un qbit ne porte aucune information tant qu'il n'est pas mesuré, seulement de l'information en devenir, si je puis dire. Et lorsqu'il est mesuré, la décohérence dont on a parlé toute à l'heure empêche de connaître l'état antérieur du qbit.
Il y a quand même quelques légers problèmes, dus à la nature quantique d'un qbit:
Alors me direz-vous, pourquoi utiliser les qbits s'ils présentent autant de caractéristiques ennuyeuses ? Leur intérêt tient dans une autre caractéristique quantique : l'intrication ! Imaginez deux qbits intriqués : ils forment une combinaison linéaire de 4 états. Maintenant imaginez N qbits intriqués: ils forment une combinaison de 2N états. Dans la mesure où ces N qbits sont intriqués, si l'on effectue une opération sur un qbit intrinqué, on l'effectue sur les N qbits. On double donc la puissance de calcul, chaque fois qu'on ajoute un qbit. Essayez donc de faire ça avec des bits classiques!
Pour réaliser un ordinateur quantique on se retrouve donc devant plusieurs défis physiques, mathématiques et technologiques:
Pour stocker un qbit, on peut utiliser plusieurs systèmes physiques:
La physique nécessaire pour aborder ces systèmes est hors de portée du scope de ce site, sauf peut être la notion de photon polarisé (lumière polarisée).
Ce qu'il est important de retenir, c'est que ces systèmes permettent de stocker un ou plusieurs qbits et de les faire évoluer (lire, écrire, conserver). Ils souffrent tous des mêmes défauts de cohérence dans le temps. Pour faire un calcul, il faut agir vite car l'état quantique est vite perturbé puis détruit. Ce problème ainsi que l'association d'un nombre de plus en plus élévés de qbits font l'objet de toutes les recherches actuelles.
L'état et l'évolution d'un système quantique sont déterminés par l'équation de Schrödinger, qui contient l'hamiltonien H(t) du système quantique. L'hamiltonien est l'observable associée à l'énergie totale du système. Pour le déterminer rigoureusement, il faudrait soit isoler totalement le système, afin de déterminer son énergie interne, soit considérer l'hamiltonien de l'univers entier ! On est un peu coincé ! L'équation est donc approximative et ses solutions théoriques ne correspondent plus du tout à la réalité constatée. Cet écart est appelé phénomène de décohérence, qui explique entre autre pourquoi le chat de Schrödinger est vivant OU mort dans notre monde macroscopique.
La décohérence est due à l'intrication du système quantique, un qbit par exemple, avec son environnement. On ne peut pas empêcher cette décohérence car on ne sait pas produire un système parfaitement isolé. Mais on peut la retarder suffisament pour pourvoir faire des calculs. On verra dans le chapitre suivant comment corriger les erreurs dues à cette décohérence.
Le passage d'un qbit à l'association de deux qbits (ou plus) est bien plus qu'une évolution quantitative. En effet, apparaissent dans cette association des corrélations quantiques entre les qbits qui font toute la puissance du calcul quantique.
On a vu plus haut que l'état d'un qbit s'exprimait dans une base de deux vecteurs (les kets) |0> et |1>. L'état de deux qbits s'exprime lui dans une base à 4 kets: |00>, |01>, |10> et |11>, selon toutes les combinaisons linéaires possibles dans cette base.
En général, on peut factoriser l'état d'un groupe de deux qbits dans cette base. Mais ce n'est pas toujours le cas. Les états pour lesquels ce n'est pas le cas sont dits "états intrinqués", ou enchevétrés.
Dans un groupe de qbits intriqués l’état individuel d’un qbit n’est pas défini. C’est le système qui est dans un état défini, et qui évolue au cours du temps. Ce n’est que lors d’une mesure sur un des qbits que son état est dévoilé. Sous certaines conditions d'intrication, la mesure de l'état d'un qbit permet de déduire l'état des autre qbits du groupe.
En calcul quantique, les erreurs sont dues aux interactions, même très faibles, des systèmes physiques qui portent l'information avec l'environnement extérieur. Ces erreurs sont inévitables et s'accumulent dans le temps, ce qui rend vite tout calcul impossible. Il est donc indispensable de les corriger.
Ce problème existe aussi en informatique classique dans les mémoires de nos ordinateurs. Le moindre rayon cosmique, et il y en a beaucoup, peut perturber un des condensateurs microscopique qui forment la mémoire et donc modifier l'information. Pour contourner ce phénomène, on a recours à des codes de correction d'erreurs. Ces algorithmes détectent les erreurs et les corrigent.
Ceux que ça intéresse trouveront une description de quelques codes de corrections (à 5-qbits ou à 7-qbits) dans le "Calculs et algorithmes quantiques" de David Mermin, au chapitre 5.
Le coeur de cet algorithme de 1994, est le calcul d'une transformée de Fourier (TF), autrement plus efficace que notre FFT classique. Cet algo, avec seulement des portes de 1-qbit ou 2-qbits (et encore peut on se passer de ces dernières) peut calculer une TF sur n bits en seulement n*2n opérations au lieu de (2n)2 classiquement ! Mesurez-vous bien le gain?
Bon, me direz-vous, à part pour les fanas du traitement du signal, à quoi peut bien servir de savoir calculer rapidement la TF d'une fonction? Et bien, cela sert à calculer la période de cette fonction... Et alors, toujours pas convaincus de l'intérêt de la chose? Si je vous dis que l'on démontre qu'il existe un rapport étroit entre la factorisation d'un nombre premier et la détermination de la période d'une fonction particulière, cela n'éveille toujours pas votre attention ? C'est la base du cryptage RSA et de son hacking !! L'algorithme de Shor permet de hacker n'importe quelle donnée cryptée RSA ! C'est vous dire l'intérêt de cet algo et d'un calculateur quantique ! On transforme un problème exponentiel en un problème polynomial ! Ainsi, il devient raisonnable de penser casse un code RSA, alors qu'avec un ordinateur classique, il vous faudrait un temps très déraisonnable.
Toutes les démonstrations dans le "Calculs et algorithmes quantiques" de David Mermin, au chapitre 3.
La recherche d'une information dans une liste, ou d'un nom dans un base de données non structurée, est sans doute une des opérations les plus courantes en informatique. Bien sur, il existe beaucoup d'algorithmes efficaces pour faire ça, mais ils ont pour particularité de devenir de plus en plus long à exécuter à mesure que la liste dans laquel ils cherchent devient longue. Pour le dire autrement, pour trouver un nom parmis N noms, un algorithme classique tentera N/2 opérations en moyenne.
Il existe un algorithme quantique, l'algorithme de Grover, de 1996, qui lui effectue l'opération avec un nombre moyen de sqrt(N) opérations. Imaginez : pour une liste d'un million de noms, le classique procède en moyenne à 500 000 tests et le quantique à seulement mille !!
Vous trouverez une très bonne introduction à cet algorithme dans "Introduction à l'informatique quantique" de Michel le Bellac. Une remarque en passant : qui passe son temps à chercher des données non structurées dans des bases de données immenses ? Gagné :-)
Nous venons de voir l'intérêt de l'algorithme de Shor. Il tient dans une transformation de la nature du problème posé (dans son cas, la factorisation d'un nombre premier).
Quand on parle de complexité algorithmique, on fait référence, pour faire très simple, au nombre d'opérations nécessaires pour traiter un problème. Imaginons que je mesure la taille de mon problème en nombre de bits, par exemple inverser une matrice n*n. Ce problème peut être traité en N opérations. La complexité algorithmique mesure la relation entre n et N.
Il existe des problèmes dits "polynomiaux", les plus simples. La relation entre n et N est d'ordre polynomiale, c'est à dire d'ordre xn. L'augmentation progressive de n ne provoque pas une augmentation exponentielle de N. On appelle ces problèmes faciles, les problèmes de "classe P".
Il existe une autre classe de problèmes, la classe des problèmes NP, qui sont "difficiles" c'est à dire que le calcul de la solution varie exponentiellement avec la dimension du problème, mais dont la vérification de la solution est facile. Par exemple, il est difficile de factoriser un nombre premier suffisamment grand mais il est facile de vérifier que la solution est bonne lorsqu'on a trouvé cette solution !
Un ordinateur quantique traite les mêmes problèmes que les ordinateurs classiques. On peut d'ailleurs simuler un ordinateur quantique avec un ordinateur classique. Une fonction qui ne serait pas calculable au sens de Turing sur un ordinateur classique ne le sera pas non plus sur un ordinateur quantique.
La grande, très grande différence, c'est qu'un problème "difficile", c'est à dire avec un nombre d'étapes de calcul qui croît exponentiellement avec la dimension du problème, sur un ordinateur classique, devient un problème "facile", c'est à dire avec un nombre d'étapes polynomial, sur un ordinateur quantique. La factorisation d'un très grand nombre premier sur un ordinateur classique prendrait un temps déraisonnable (plusieurs dizaines ou centaines d'annèes de calcul) alors qu'il prendra peu de temps (quelques heures ou jours) sur un ordinateur quantique.
L'ordinateur quantique, avec l'algorithme de Grover est aussi particulièrement adapté à la recherche dans les très grandes bases de données non struturées. Il sera donc très utile dans les prochaines application de "big data" et nous épargnera les fermes de milliers de processeurs, qui dépensent une quantité folle d'énergie et sont difficiles à administrer.
Un ordinateur quantique peut produire des suites de nombres aléatoires parfaitement décorrelés. C'est particulier utile pour utiliser certains algorithmes classiques archi-connus comme la méthode de Monte-Carlo, qui intervient dans la plupart des simulations.
Les caractéristiques des systèmes quantiques, en particulier le théorème de non clonage quantique, ouvrent d'autres perspectives. Par exemple, la cryptographie quantique permet de coder et de protéger un message de façon bien plus certaine que tous les codages RSA ! Il existe d'ailleurs des applications pratiques professionnelles qui fonctionnent. Vous pouvez, pour quelques milliers d'euros acheter une carte de cryptage quantique pour votre PC (voir par exemple idquantique).
Avec ces propriétés, on comprend mieux que la NSA s'intéresse au sujet !
Mais on est quand même loin d'une réalisation pratique d'un ordinateur quantique ! Au dernières nouvelles, voilà ce qu'on arrive à faire:
Et je ne parle pas des différentes intox qu'on voit apparaitre ça et là périodiquement... Nous sommes encore loin d'avoir un ordinateur quantique sur le coin de notre bureau. Mais cela viendra, d'ici 10 ou 20 ans, au moins dans les centres de calculs. Après tout, lors de l'apparition des ordinateurs "commerciaux", dans les années 50, IBM estimait le marché à quelques machines, réservées aux grandes administrations. Aujourd'hui, on a la puissance d'un IBM 360 (et même plus) dans notre poche. Alors on peut toujours rêver.
L'informatique quantique, dans son algorithmique mais aussi ses systèmes de stockage et de traitement de l'information, est pour moi l'un des domaines les plus prometteurs de progrès dans la connaissance et la technologie. Il reste beaucoup de travail avant d'aboutir à un ordinateur quantique opérationnel. Mais on peut rêver, ou cauchemarder c'est selon : la NSA et ses scientifiques ont peut être dans leurs caves de Fort Meade un splendide ordinateur quantique qui casse les codes RSA de vos mails et cartes de crédit à longueur de journée... J'ai cependant quelques doutes....
Pour ceux qui aimeraient creuser un peu plus le problème, voici deux livres intéressants:
Attention, ces ouvrages ne sont pas d'un abord immédiat, le second est plus hard que le premier. Il faudra s'accrocher un peu, mais rien d'impossible aux éléves de prépa ou de L2. Pour les autres, il serait peut être plus sage de lire les articles de "Pour la Science", qui publie assez régulièrement sur le sujet (faites des recherches sur le site www.pourlascience.fr).
Contenu et design par Dominique Lefebvre - tangenteX.com janvier 2014 
Contact : PhysiqueX ou 
Cette œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Pas de Modification 3.0 France.