Ordinateur quantique (2ème partie)

Après quelques rappels sur la mécanique quantique le mois dernier, poursuivons avec quelques considérations sur l'ordinateur quantique. L’ordinateur quantique est annoncé comme une technologie à même d’assurer la continuité de la loi de Moore, avec l’Intelligence Artificielle en ligne de mire. On annonce de grandes avancées pour cette année. Depuis plus de dix ans les circuits silicium des ordinateurs classiques se frottent aux frontières du trop petit et les puces multi-cœurs pallient l’impossible poursuite de la miniaturisation des gravures. Le quantique sera-t-il le relai ?

Donnons tout de suite la réponse, c’est non. La technologie n’est pas au rendez-vous. Non que la faisabilité soit en cause : la physique l’autorise, ça devrait le faire tôt ou tard. Mais le savoir-faire technologique dans ce monde étrange ne fait que balbutier et la perspective de la maîtrise des algorithmes les plus complexes (problème NP-complets) n’est pas encore acquise. Il y a du boulot tant sur les aspects matériel qu’algorithmique.

Sémantiquement, l’appellation « ordinateur quantique » elle-même porte à discussion. Faire tourner un programme spécifique sur une machine générique est l’essence même des ordinateurs classiques ; les ordinateurs quantiques d’aujourd’hui sont des calculateurs spécifiques nantis de portes logiques pour intégrer un algorithme dédié. La programmation n’est pas à l’ordre du jour et le terme calculateur quantique est plus approprié que celui d’ordinateur quantique. Cela dit, nous utiliserons indifféremment les deux termes dans la suite de ce papier.

Quant aux performances alléchantes, elles sont attendues mais un avantage clair face aux ordinateurs classiques reste à confirmer. Les affirmations parues dans la presse sur la suprématie quantique faussent un peu la question en requérant des ordinateurs classiques une démarche identique à celle des calculateurs quantiques. Ainsi, demander à un ordinateur classique de multiplier n x p en pratiquant p additions du nombre n comme en mécanique quantique n’a pas grande signification. Les victoires annoncées aujourd’hui de la mécanique quantique portent sur des problèmes que l’informatique classique résout plus rapidement avec ses méthodes.

La cryptanalyse est doublement intéressée par le monde quantique : d’une part les calculateurs pourraient venir à bout des factorisations et d’autre part la superposition alliée à intrication offrent à la fois vrai aléatoire et transmission confidentielle de clef pour le chiffrement symétrique. Ce dernier point ne relève pas des ordinateurs quantiques mais de l’utilisation des caractéristiques du monde quantique.

En parallélisant massivement les calculs, le modèle théorique des ordinateurs quantiques rend linéaires des problèmes qui étaient exponentiels dans l’informatique classique. Le gain en puissance promet d’être substantiel. Mais quel est calendrier pour le passage à la pratique ? Arriverons-nous à étendre les lois du microscopique à un monde bien proche du macroscopique ?

Penchons-nous pour commencer sur la mécanique de ces calculateurs.

Calculons quantique

Les travaux du physicien Paul Benioff de l’ Argonne National Labs en 1981 mettent le pied sur le terrain de l’ordinateur quantique en imaginant un ordinateur classique qui exploiterait certains phénomènes quantiques.

Le grand physicien Richard Feynman, père de l’électrodynamique quantique se heurtait en 1982 à la résolution d’équations de fonctions d’onde des particules pour laquelle la totalité des chemins possibles pour aller d’un point à l’autre doit être analysée. La complexité n’a pas de limite : il faut tenir compte des trajectoires remontant le temps pour gagner quelques décimales ! L’ordinateur est incontournable dans ces recherches mais avec des limites trop tôt atteintes. Fin connaisseur du principe de superposition de la mécanique quantique, Richard Feynman a bien vite saisi le parti à en tirer pour bénéficier d’un parallélisme massif. « 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 ». C’est pour des besoins en simulation de physique quantique qu’a émergé le concept d’ordinateur quantique.

Avancée notable, David Deutsch de l’Université d’Oxford publie en 1984 un papier sur l’architecture d’un ordinateur ne reposant que sur les règles de la mécanique quantique. Les bases sont jetées, l’ordinateur quantique est possible.

L’engouement décisif – comprendre l’intérêt et les moyens financiers - sera provoqué par le mathématicien Peter Shor en 1994 avec un algorithme pour ordinateur quantique capable de s’attaquer à la factorisation de grands nombres. Menace de poids pour la cryptographie ! Depuis industrie, universités, grands laboratoires et autres Gafam’s parcourent à grand pas décidés l’univers de l’indétermination. Ça tâtonne : les résultats sont là et ne sont pas là, comme un hommage au chat mort et vivant.

Bon cela étant posé, il y a de quoi être intrigué : comment peut-on prétendre construire un ordinateur à partir d’un processus dont les réponses sont le fruit du hasard ? Plongeons dans cette informatique qui impose des raisonnements qui n’ont rien à voir avec ceux auxquels on est familier, bannissons nos intuitions. Disruptons.

Quantique et ordinateur

Le principe de superposition sur lequel est construite la mécanique quantique précise qu’entre deux interactions une particule quitte son statut « classique » pour entrer dans le domaine quantique des ondes de probabilité. Elle ne retrouve le statut « classique » que lors d’une nouvelle interaction. En quelque sorte, une particule « n’existe » que quand on l’observe. En prenant l’exemple du déplacement d’un photon, on peut préciser le lieu de départ, celui de l’arrivée mais point de trajectoire entre les deux.

Toutes les routes imaginables sont prises en compte dans une fonction mathématique nommée fonction d’onde. Cette fonction ondulatoire permet de déterminer la probabilité de présence en tout point. Mais attention : on ne fait pas la moyenne de ces possibilités comme on pourrait mélanger des liquides mais on superpose toutes les possibilités. Au moment de la lecture une seule possibilité est retenue parmi toutes. Au hasard. Les autres sont oubliées. Le résultat qui nous intéresse est noyé parmi tous les résultats. Superposés. Avec de nouveau le hasard pour la lecture. Donc … que faire d’un résultat aléatoire ?

Notons que toutes les possibilités « listées » dans la fonction d’onde ne sont pas sur le même pied de probabilité. Le calcul quantique joue sur des pondérations pour favoriser les « bons » résultats par une probabilité plus élevée.

D’une manière générale on n’a pas le choix, il faut faire avec l’aléatoire. Dieu joue aux dés. Dans la recherche des facteurs premiers d’un grand nombre par exemple, on est pas sûr que la valeur obtenue soit correcte. C’est probable mais le résultat n’est validé qu’après avoir effectivement divisé ledit grand nombre. Si ce n’est pas le cas on réitère le calcul jusqu’au tirage du bon résultat. On n’a en effet pas de deuxième chance en piochant de nouveau dans les états superposés car ils ont été détruits par la lecture, effondrement de la fonction d’onde oblige.

Les chemins du calcul quantique sont fidèles à l’étrangeté du monde quantique et pleinement en opposition avec nos approches familières en informatique classique.

Qubit

La coutume a légué à nos civilisation la base dix, héritage du dénombrement sur le bout de nos doigts. L’ordinateur classique utilise la base deux, le courant passe ou pas. Le bit informatique prend les valeurs « 0 » ou « 1 », et en juxtaposant quatre bits dans un registre on peut représenter un nombre compris entre zéro et quinze.

Dans le monde quantique, on utilise également un système à deux états grâce à des propriétés physiques comme le spin par exemple, tout comme dans un ordinateur classique. Sauf que le monde quantique vient avec sa part d’étrangeté : le qubit, ainsi nomme-t-on le bit quantique, peut prendre à la fois les valeurs zéro et un. C’est la magie du principe de superposition.

Un exemple classique illustre le bénéfice de la superposition par la mise en scène un joueur indélicat au jeu de pile ou face : il utilise des pièces truquées avec la même figure des deux côtés.

En mécanique classique, il faut faire deux lectures pour s’assurer que la pièce est non truquée, alors que la superposition quantique nous renseigne en une passe unique. Le gain est de deux. Avec quatre qubits, on obtient tout comme en informatique classique seize valeurs sauf qu’ici on manipule simultanément tous les nombres compris entre zéro et quinze. Bizarre, non ? Mais surtout très puissant car avec cent qubits on peut faire un calcul sur deux puissance cent valeurs en une seule passe. C’est massivement parallèle.

Tempérons néanmoins notre enthousiasme : le parallélisme utilisé n’est pas celui de l’informatique classique où le travail est découpé et réparti judicieusement entre des machines qui exécutent chacune une tâche spécifique et délivrent chacune un résultat dédié. À l’opposé, les calculateurs quantiques n’appliquent qu’un seul et même traitement à toutes les variables et n’obtiennent qu’un résultat unique pour tous.

Les calculs massivement parallèles, aujourd’hui identifiés comme domaine de prédilection de l’informatique quantique, font appel à un mode de fonctionnement sans grand rapport avec notre monde classique. Performance comme domaines d’application restent à être évalués.

Ordinateur sans « Copier/Coller »

Notons une conséquence majeure du principe de lecture : l’adieu à la fonction « Copier ».

Une variable quantique est un état de superposition de toutes les valeurs possibles. À la moindre lecture, seule une valeur est retenue, les autres sont oubliées. Ce qui réduit à néant tout espoir de faire un « Copier » d’une variable. Il n’y a pas de clonage possible. On ne peut pas affecter à la variable « b » la valeur de la variable « a ». La variable « a » serait immédiatement réduite à une valeur unique piochée au hasard dans toutes celles proposées par la superposition. De nouveau,  le calcul quantique est aussi déroutant que la mécanique du même nom, là encore les algorithmes quantiques sont spécifiques. On ne peut pas « porter » une application classique. Le choix entre Windows, Linux ou MacOS ne se pose pas. Ah oui, il y a encore du boulot.

Décohérence

Nous touchons là le grand défi de l’ordinateur quantique qui est de maîtriser le passage intempestif de l’état quantique à l’état classique.

Dans le monde quantique, on fait des sauts de puce entre les mesures, lectures ou plus globalement entre les interactions. Entre deux interactions on est dans cet état magique de superposition où le calculateur calcule. A chaque interaction on efface la superposition pour ne garder qu’une valeur. Le passage de la superposition quantique à la structure classique est la décohérence.

L’opération est volontaire lors de la lecture ou accidentelle lorsqu’elle est provoquée par des perturbations comme des vibrations ou de la lumière. Le physicien français Serge Haroche a reçu le prix Nobel 2012 pour ses travaux sur la décohérence du photon grâce à des pièges à photons construits avec des miroirs. La décohérence survient en un temps inversement proportionnel au nombre de particules.

L’enjeu est de rester quantique un temps suffisamment long pour avoir le temps de calculer. Les particules doivent être à l’abri de toute perturbation, d’où des températures de fonctionnement très très basses. Pas loin du zéro absolu, cet état où tout mouvement est arrêté. Isolation maximum certes, mais il faut quand même cohabiter avec d’autres qubits et franchir des portes logiques. Le « passage à l’échelle » est particulièrement délicat. On sait de nos jours manipuler des registres d’une (grosse ?) dizaine de qubits, mais guère plus.

Ingénieurs et savants ne sont pas restés les deux pieds dans le même qubit et ont élaboré un mécanisme de calcul d’erreur qui devrait repousser les limites. La décohérence se traduit par des erreurs de transmission. Les télécoms confrontées à ce même obstacle ont depuis longtemps su user des mathématiques pour maîtriser le haut-débit. Le savoir-faire en calcul et correction d’erreurs a été mis à profit ; les résultats sont spectaculaires. Le problème est que pour protéger un qubit, on a besoin de plusieurs qubits. Qu’il faut protéger, cela va de soit. La science est trop récente pour chiffrer de manière fiable ce surplus mais comptez dix à quinze qubits redondants par qubit utile dans le contexte de registres d’une dizaine de qubits utiles. Le point est d’autant plus critique que ces calculs d’erreurs ne peuvent aboutir que si au départ le taux d’erreur est suffisamment faible, condition s’accommodant mal de l’augmentation du nombre de qubits. La factorisation par exemple est d’une exigence redoutable sous peine d’une dérive rapide. Qu’en sera-t-il avec des mots d’une centaine de qubits ? Saura-t-on gérer des particules en état de superposition par millier ? J’insiste, il y a du boulot.

Algorithme de Shor

Voici juste quelques considérations sur l’application phare qui fait trembler la cryptographie.

Peter Shor, spécialiste du calcul quantique est un mathématicien américain. Il s’est penché sur la factorisation de grands nombres, et en a tiré une méthode polynomial de calcul. Polynomial ? La complexité croît linéairement avec la taille du nombre alors qu’elle était exponentielle en informatique classique. La question représente un intérêt majeur pour le fonctionnement d’Internet : c’est sur la difficulté de factoriser que repose le secret des transactions.

Voyons les performances des calculateurs classiques. Le 12 décembre 2009, après deux ans de travaux une solide équipe de treize mathématiciens et cryptologues menée par Thorsten Kleinjung a extrait avec succès les facteurs premiers d’un nombre formé de deux cent trente deux chiffres après avoir fait tourner quatre-vingt processeurs classiques pendant six mois (Factorization of a 768-bit RSA modulus, version 1.4, February 18, 2010).  Beaucoup de chiffres dans une simple phrase dont le seul but est d’illustrer l’énormité de la tâche. Les clefs RSA utilisées en cryptographie font au moins 1024 bits, la valeur 2048 bits étant recommandée par l’ANSSI pour demeurer à l’abri d’une factorisation par des ordinateurs classiques. En pratique, la complexité des meilleurs algorithmes à ce jour épouse une exponentielle fonction du nombre de bits, plus précisément deux à la puissance racine cubique (2∛n ) du nombre de bits. Les secrets sont bien gardés sous les remparts des nombres premiers.

Avec un calculateur quantique, les calculs sont plus légers car toutes les opérations sont menées simultanément. D’exponentielle, la complexité devient linéaire : elle croit avec le double du nombre de bits suivant l’algorithme de Shor, des optimisations par recyclage de qubits permettant encore de réduire ce nombre. En 2012, 21 a été factorisé avec huit qubits. La factorisation d’un nombre de 2048 bits ne prendrait qu’une petite centaine de secondes.

Cela étant posé, petit calcul : pour « casser » 2048 bits, il faut avec l’algorithme de Shor deux fois plus de qubits, soit 4096 qubits et probablement quelque cent millions de portes. Or le calcul d’erreurs pour pallier la décohérence est gourmand en qubits redondants, au minimum cinq ainsi que le mentionne le cours de Serge Haroche, mais apparemment le calculateur D-Wave 2X en demanderait un minimum de treize. Pour casser RSA ce sont plusieurs dizaines voire la centaine de milliers de qubits qu’il faut maîtriser. Ah oui quand même. Le chat de Schrödinger montre sa queue ! Ces valeurs sont (aujourd’hui …) d’autant plus inconcevables qu’il faut maintenir le tout en état de superposition suffisamment long (une centaine de secondes), alors que l’unité de temps de maintien de la superposition (aujourd’hui …) est plutôt la milliseconde. Il y a du boulot, vous dis-je. C’est sans appréhension que je continue à saisir mon code bancaire.

Relevons quand même le remarquable exploit de l’équipe de Nike Dattani de l’Université de Kyoto qui en novembre 2014 à partir de seulement quatre qubits a factorisé 56 153. Mais l’algorithme utilisé ne concerne que des séries de nombres spécifiques : 143, 56­ 153, 291 311, ce dernier sur six qubits étant attendu prochainement. Les succès pour quelques séries ne mettent pas en danger la factorisation utilisée en cryptologie.

Résumons-nous sur quelques points …

 – L’ordinateur quantique continuité de l’ordinateur classique ?

Non, l’ordinateur quantique ne se comporte pas comme un ordinateur classique. Les modes de traitement de l’information n’ont rien à voir avec nos logiciels. Seuls quelques domaines (simulation, optimisation, recherche de nombres premiers, base de données) sont aujourd’hui identifiés. La complémentarité des deux technologies dans des machines hybrides pourrait avoir un certain sens.

– L’ordinateur quantique pour demain ?

Non, et nous ne sommes pas près d’être prêts. Sur un plan matériel la décohérence se pose en obstacle majeur. Des pistes sérieuses de résolution existent, restent à les étendre à plusieurs centaines de qubits. Il reste par ailleurs à étoffer une panoplie des algorithmes aujourd’hui fort réduite.

 - La décohérence est-elle insurmontable ?

Oui, à court terme. Physiquement la quantité d’interactions entre particules rend impensable l’utilisation de registres de taille suffisante pour construire une machine opérationnelle. Cela dit … la totalité des physiciens qui en 1920 élaboraient des expériences de pensée était persuadée que jamais on ne pourrait les réaliser.

Selon Schrödinger au début des années 1950 réussir à observer une particule unique relevait du fantasme et délivrerait des résultats absurdes. La suite lui a donné à moitié raison : de telles observations ont été réalisées et les résultats en ont confirmé l’absurdité. Alors, un jour peut-être ?

- Des concurrents pour l’ordinateur quantique ?

Oui, un certain nombre. Citons l’ordinateur à ADN qui s’appuie sur la biologie moléculaire en faisant travailler des enzymes ou l’ordinateur neuronal - sans aucun lien avec les réseaux neuronaux - construit autour de neurones biologiques. Mais nous ne disposons encore que de projets prometteurs.

Beaucoup de points n’ont pas été abordés ici, format article de NewsLetter oblige. Je citerais les applications, les technologies de réalisation, les réalisations actuelles dont D-Wave, mais voilà de beaux objets pour un futur livre blanc !

 

 

 


< Revenir à la newsletter

Auteur: 
Jacques Baudron - jacques.baudron@ixtel.fr

Ajouter un commentaire

Full HTML

  • Les adresses de pages web et de courriels sont transformées en liens automatiquement.
  • Vous pouvez utiliser du code PHP. Vous devrez inclure les tags <?php ?>.
  • Les lignes et les paragraphes vont à la ligne automatiquement.

Filtered HTML

  • Les adresses de pages web et de courriels sont transformées en liens automatiquement.
  • Tags HTML autorisés : <a> <em> <strong> <cite> <blockquote> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Les lignes et les paragraphes vont à la ligne automatiquement.

Plain text

  • Aucune balise HTML autorisée.
  • Les adresses de pages web et de courriels sont transformées en liens automatiquement.
  • Les lignes et les paragraphes vont à la ligne automatiquement.