Découvert en 1994, l'algorithme de Shor permettrait de casser rapidement les clés utilisées pour les transactions bancaires. Il suppose l'existence d'un calculateur quantique avec un très grand nombre de qubits. Une équipe de chercheurs français de l’Institut de physique théorique (IPhT) du CEA Paris-Saclay a trouvé le moyen de faire la même chose avec 1.000 fois moins de ces bits quantiques d'informations.
au sommaire
La découverte de la physique quantiquephysique quantique a été tout d'abord une révolution conceptuelle avant de déboucher sur une révolution technologique. On peut dire qu'elle s'est étalée de 1900 à 1930 et qu'elle a mobilisé quelques dizaines des esprits les plus brillants du début du XXe siècle, aussi bien chez les physiciensphysiciens, les mathématiciensmathématiciens et les expérimentateurs. On doit au changement de paradigme qui s'est mis en place à cette époque la technologie actuelle des laserslasers mais aussi, par exemple, celle de l'imagerie par résonance magnétiqueimagerie par résonance magnétique et bien sûr des pans entiers de l'électronique.
Des années 1930 aux années 1970, de la découverte du paradoxe du chat de Schrödingerchat de Schrödinger aux travaux de John Bell et Alain Aspect, une seconde révolution conceptuelle et technologique s'est préparée et nous la voyons en cours aujourd'hui avec l'essor des technologies de l'information quantique. On attend beaucoup de celle des simulateurs et des ordinateurs quantiques bien que les avis diffèrent encore quant à savoir si ces artefacts de la noosphère vont vraiment prendre l'ascendant sur les ordinateurs classiques. La question est subtile.
Découvrez en animation-vidéo l'histoire de la physique quantique : depuis la catastrophe ultraviolette jusqu'aux promesses de l'ordinateur quantique en passant par la première et la deuxième révolution quantique avec les idées de Feynman et Peter Shor. Une animation-vidéo co-réalisée avec L’Esprit Sorcier. © CEA Recherche
Un monde d'informations quantiques fragile
Ces ordinateurs utilisent les lois du monde quantique comme celle de la superposition des états et de l'intricationintrication pour effectuer des algorithmes manipulant non pas des bits d'informations comme le font les machines d'Alan Turing mais des qubits d’informations. Dans certains cas, on a pu montrer que ces algorithmes quantiques permettraient en théorie de résoudre très rapidement des problèmes qui pourraient prendre des siècles de calculs à des ordinateurs classiques. Par contre, il est possible et cela s'est même déjà produit, que l'on trouve finalement des algorithmes classiques nouveaux qui fassent aussi bien que des algorithmes donnant la suprématie quantique sur les ordinateurs actuels.
Rappelons aussi que les ordinateurs ou simulateurs quantiques ont besoin de résoudre ce qui est appelé le problème de la décohérence. Une image permet d'appréhender ce problème.
Pour réaliser un ordinateur quantique surpassant un ordinateur classique, il faut en effet disposer d'un grand nombre de qubitsqubits. On peut se les représenter comme les éléments d'un château de cartes. Plus il prend de la hauteur, plus il est instable. Quand il atteint quelques étages, un minuscule courant d'airair ou une petite vibrationvibration de la table suffit pour que tout le château s'écroule. De façon générale donc, plus le château est grand, plus il a de risques de s'effondrer vite, à moins de le placer dans une chambre sous vide ou sur une table l'isolant des vibrations du sol par exemple.
Le problème est similaire avec des qubits. Il faut généralement refroidir presque au zéro absoluzéro absolu les systèmes quantiques constitués des quelques atomesatomes seulement qui portent ces qubits pour les isoler suffisamment longtemps du bruit de fond ambiant, souvent thermique, généré par le reste de l'universunivers. Même ainsi, on dispose d'un temps trop court pour pouvoir effectuer autre chose que quelques timides calculs quantiques.
Il faut donc trouver un moyen de protéger autant que possible les calculs quantiques de ces perturbations et/ou utiliser des codes correcteurs quantiques cousins de ceux des ordinateurs classiques pour lutter contre les erreurs de calcul produites par la décohérence.
Une présentation plus poussée du concept d'ordinateur et d'algorithme quantique. © CEA Recherche
Un algorithme pour casser le chiffrement RSA des cartes bancaires
Parmi les problèmes qui font phosphorer les physiciens et les ingénieurs travaillant sur les ordinateurs quantiques, il y a celui de savoir si l'on pourra un jour concrétiser l'algorithme de Peter Shor sur une machine. Dans le précédent article ci-dessous, Futura avait expliqué que cet algorithme permettrait de casser le secret des cartes bancaires (voir aussi la première vidéo du CEA à ce sujet) en rapport avec le chiffrement RSA très utilisé dans le commerce électronique. Il lui suffirait de quelques heures alors qu'en théorie c'est une tâche impossible à effectuer en un temps raisonnable même pour des superordinateurssuperordinateurs classiques.
Il y a tout de même un bémol, il faudrait pour cela au moins 20 millions de qubits dans un seul état quantique, ce qui bien évidemment semble insurmontable à réaliser du fait de la décohérence.
Toutefois, des physiciens théoriciens du CEA à l'Institut de physique théorique (CEA/CNRS/Université Paris-Saclay) viennent de publier un article dans le journal réputé Physical Review Letters dans lequel ils annoncent qu'ils ont découvert qu'il faudrait en réalité au moins 1.000 fois moins de qubits, comme on peut le constater en consultant l'article en accès libre sur arXiv.
L'idée centrale qui permettrait d'implémenterimplémenter nettement plus efficacement l'algorithme de Shor est celle d'avoir deux systèmes quantiques séparés, l'un servant de mémoire et l'autre d'ordinateur quantique proprement dit. On tomberait déjà à 200.000 qubits. En bonus, comme l'explique un communiqué du CEA, en utilisant des codes correcteurs d'erreurs astucieux on tomberait alors à environ 13.000 qubits, soit au total le gain d'un facteur 1.000 annoncé.
Par contre, si l'obstacle de la décohérence est bien rendu plus faible avec 1.000 fois moins de qubits portés par un système d'un volumevolume plus faible et plus facile à isoler et à refroidir, le temps de calcul passe, lui, de quelques heures à quelques mois car l'effet de parallélisme des ordinateurs quantiques fonctionnant de cette façon avec une mémoire quantique externe est réduit.
Le laboratoire de physique fondamentale du groupe d'électronique quantique (quantronique) du CEA invente, conçoit, fabrique et caractérise des circuits et composants quantiques. Les circuits électriques quantiques peuvent se trouver globalement dans deux états électriques à la fois, alors que ces deux états sont normalement incompatibles. Découvrez ces différentes étapes en vidéo. © CEA Recherche
Le secret bancaire résistera-t-il à un algorithme quantique ?
Article de Laurent SaccoLaurent Sacco publié le 09/03/2016
Découvert en 1994, l'algorithme de Shor permettrait de casser les clés utilisées pour les transactions bancaires. Il suppose l'existence d'un calculateur quantiquecalculateur quantique avec un grand nombre de qubits. Une équipe de chercheurs a fait un pas de plus en direction de la création d'une telle machine.
On sait, au moins depuis EuclideEuclide, qu'il est possible de décomposer les entiers en produits de nombres premiersnombres premiers (par exemple 15 = 3 × 5). La décomposition est à chaque fois unique et des algorithmes permettent de la trouver. Cependant, ces derniers deviennent rapidement prohibitifs en temps de calcul lorsque l'entier considéré devient de plus en plus grand.
Certains de ces algorithmes sont plus efficaces que d'autres mais, même avec des superordinateurs, trouver la décomposition de certains entiers en un produit de deux nombres premiers pourrait prendre des dizaines d'années. Ce simple fait autorise des techniques de codage efficaces qui assurent le secret des transactions bancaires, le fameux chiffrement RSA.
Toutefois, en 1994, un chercheur en mathématiques appliquées du Massachusetts Institute of Technology (MIT), Peter Shor, a fait exploser une petite bombe. Il s'intéressait au tout jeune domaine du calcul théorique avec des ordinateurs quantiques, domaine de recherche ouvert dans les années 1980 par des pionniers comme Richard Feynman et David Deutsch. Il démontra que le calcul quantique avec des qubits permettait l'existence d'un algorithme capable de factoriser en un temps record un entier en un produit de deux nombres premiers. En théorie - en pratique c'est une autre histoire -, il était donc possible de casser les codes secrets non seulement des banques mais aussi des États et des armées en utilisant l'algorithme de Shor.
Malheureusement, ou heureusement, un ordinateur quantique, ou simplement un calculateur quantique spécialement dédié à l'implémentation de cet algorithme pose de redoutables problèmes.
Cryptologie quantique et décohérence
Au cœur de l'efficacité de cet algorithme, se trouve le fameux principe de superposition des états en physique quantique. Les qubits, qui sont des généralisations des bits classiques, sont portées par des variables de systèmes physiques, comme des spinsspins d'électronsélectrons, de photonsphotons ou des moments orbitaux dans des atomes. Ils peuvent prendre deux états, 0 ou 1, mais en quelque sorte simultanément, du fait du principe de superposition des états.
On peut montrer qu'en utilisant un nombre suffisant de qubits, tout se passe comme si on pouvait faire un très grand nombre de calculs en parallèle, en faisant évoluer physiquement l'état des systèmes quantiques portant ces qubits. Sauf que l'état de superposition de ces systèmes est très fragile. Il l'est d'autant plus que le nombre de qubits est grand. Si on prend l'analogieanalogie d'un château de cartes, plus le nombre de cartes est élevé, plus le château risque de s'effondrer avant que l'on puisse faire quoi que ce soit. C'est, dans le cas des calculs quantiques, ce que les physiciens appellent le problème de la « décohérence ».
Pour contourner ce problème, qui se décompose en deux parties, il faut déjà trouver le moyen de réaliser un calcul avec un petit nombre de qubits, mais de sorte qu'il soit possible de montrer que la méthode soit, en théorie du moins, facilement utilisable sur un système de taille plus grande. Ensuite, il faut que l'on puisse également échapper au problème de la décohérence proprement dit.
Des pièges à ions pour l'algorithme de Shor
Un groupe de chercheurs vient de publier dans Science un article disponible sur arXiv dans lequel ils annoncent qu'ils ont réussi à résoudre la première partie du problème pour pouvoir un jour effectuer l'algorithme de Shor avec un grand nombre de qubits.
Cet algorithme avait déjà été mis en pratique mais les systèmes utilisés jusqu'à présent n'avaient permis de faire que des factorisations avec un petit nombre entier (n'importe quel collégien peut facilement les réaliser). En l'occurrence, rien n'a encore changé à ce niveau puisque les chercheurs ont simplement produit une factorisation du nombre 15. Cependant, la nouveauté réside dans le fait qu'ils ont réussi à le faire en n'utilisant que 5 qubits et avec des pièges à ionsions.
À l'origine, l'algorithme de Shor supposait que le nombre minimum requis était 12 qubits pour effectuer cette factorisation. Pourtant, en 1995, Alexei Kitaev avait montré qu'en modifiant cet algorithme il était possible de descendre à 5 qubits. C'est cette forme modifiée qui est utilisée avec des ions de calciumcalcium 40 dans des pièges de Paul séparés de 5 micronsmicrons et que l'on peut manipuler en utilisant un faisceau laser.
En théorie, il ne devrait pas y avoir de problème pour augmenter la taille de ce système avec un plus grand nombre de pièges à ions et de lasers. De plus, les calculs quantiques effectués avec de tels systèmes sont plus faciles à protéger des effets de la décohérence. C'est pourquoi ils sont intensément étudiés dans l'espoir de permettre d'obtenir un jour de véritables ordinateurs quantiques performants.
Il ne faut pas oublier cependant que fabriquer un calculateur quantique, par exemple pour effectuer l'algorithme de Shor, n'est pas la même chose que fabriquer un ordinateur quantique programmable pour effectuer, en principe, n'importe quel algorithme. Il faut garder à l'esprit également que ces ordinateurs ne sont pas systématiquement supérieurs aux ordinateurs classiques. Cela n'est vrai que pour résoudre certains problèmes et avec certains algorithmes.
