Un calculateur quantique avec un grand nombre de qubits est nécessaire à l'algorithme de Shor. Ce dernier permettrait de casser les clés utilisées pour les transactions bancaires… © Titima Ongkantong, Shutterstock

Sciences

Le secret bancaire résistera-t-il à un algorithme quantique ?

ActualitéClassé sous :ordinateur quantique , qubit , algorithme de shor

Laurent Sacco, Futura-Sciences

-

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 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.

Interview : en quoi un ordinateur quantique est-il différent ?  Le monde quantique est fascinant : à cette échelle, par exemple, les objets peuvent se trouver simultanément dans plusieurs états. Exploitant ce principe, un ordinateur quantique aurait des possibilités bien plus vastes qu’un modèle classique. Dans le cadre de sa série de vidéos Questions d’experts, sur la physique et l’astrophysique, l’éditeur De Boeck a interrogé Claude Aslangul, professeur à l’UPMC, afin qu'il nous explique le fonctionnement de cette étrange machine. 

On sait, au moins depuis Euclide, qu'il est possible de décomposer les entiers en produits de nombres 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.

Cette image illustre bien le problème de la factorisation des entiers en un produit de deux nombres premiers. La solution est simple pour des nombres comme 15 (15 = 3 × 5) et 91 (91 = 7 × 13) mais défie les ordinateurs pour des nombres de plusieurs centaines de chiffres. © Jose-Luis Olivares, MIT

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 spins d'électrons, de photons 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'analogie 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.

Le mathématicien Peter Shor, en pleine explication de son algorithme quantique pour factoriser des nombres entiers. © Physics World, YouTube

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 à ions.

À 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 calcium 40 dans des pièges de Paul séparés de 5 microns 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.

  Les commentaires ne sont pas disponibles pour le moment.