L'écosystème de l'informatique quantique est en train de naître

Frédéric Magniez est professeur invité sur la chaire annuelle Informatique et sciences numériques du Collège de France, 2020-2021.

En 2019, Google annonçait avoir atteint ce que le physicien américain John Preskill a baptisé la « suprématie quantique ». Avec son processeur quantique Sycamore, le géant américain est en effet parvenu à résoudre un problème qu’aucun ordinateur classique n’aurait pu résoudre en un temps raisonnable. Même si ce problème n’avait a priori aucune application réelle, cette avancée technologique a fait forte impression dans la communauté des physiciens et des informaticiens. Pour autant, ce prototype est encore loin d’être suffisamment puissant pour être considéré comme un ordinateur quantique. Cela n’empêche pas les informaticiens théoriciens d’anticiper ce qui pourrait survenir avec l’arrivée d’une telle machine en imaginant de nouvelles idées algorithmiques. En France, Frédéric Magniez est un leader de cette recherche. Diplômé de l’ENS Cachan, agrégé de mathématiques et docteur en informatique théorique, il dirige depuis 2018 l’Institut de recherche en informatique fondamentale (IRIF). Ses travaux portent sur la conception et l’analyse d'algorithmes probabilistes pour le traitement des grandes masses de données, ainsi que sur le développement de l'informatique quantique et plus particulièrement la cryptographie et ses interactions avec la physique. Il occupe la chaire annuelle Informatique et sciences numériques du Collège de France, dédiée cette année aux algorithmes quantiques.

Dans la chaire d’informatique que vous occupez cette année au Collège de France, vos cours portent sur l’informatique quantique. Pouvez-vous nous expliquer en quoi consiste ce champ de recherche ?

Frédéric Magniez : Lorsque de nouvelles architectures informatiques font leur apparition – par exemple un supercalculateur – un nouveau modèle de calcul émerge et la communauté des informaticiens théoriciens, dont je fais partie, essaie d’en comprendre les implications. Notamment nous nous demandons si l’on peut programmer ces machines, si l’on peut mettre au point des algorithmes qui tirent parti des spécificités de cette nouvelle architecture. Mais l’on se demande aussi ce que cela change en termes de complexité et de ressources. Par exemple, est-ce qu’un problème auparavant difficile peut devenir simple ? Le calcul peut-il être accéléré ? Dans le cas de l’informatique quantique, on se pose toutes ces questions avec une architecture bien particulière : un ordinateur quantique.

Qu’est-ce qu’un ordinateur quantique exactement ?

Il s’agit d’une machine qui repose sur les lois de la mécanique quantique pour stocker et manipuler de l’information. Contrairement à un ordinateur classique qui manipule des bits d’information (des 0 ou des 1), un ordinateur quantique manipule ce que l’on appelle des bits quantiques – ou qubits. Ces derniers peuvent être dans l’état 0 ou 1 mais aussi dans une superposition de ces états. Pour certains types de problèmes, cette propriété de la mécanique quantique permet d’accélérer significativement la vitesse de calcul. C’est le cas par exemple pour la factorisation, l’opération inverse de la multiplication. S’il est très simple de multiplier deux nombres entiers très grands, la factorisation, qui consiste à décomposer un très grand nombre en le produit de ses facteurs, est beaucoup plus complexe. Tellement complexe en fait que nos ordinateurs classiques sont incapables d’exécuter ce calcul en un temps raisonnable. Or, avec un ordinateur quantique, ce calcul serait exponentiellement plus rapide. Et donc possible, en théorie.

En théorie ?

Oui, car l’ordinateur quantique universel n’existe pas encore. Seuls des prototypes de calculateurs quantiques ont été mis au point, notamment par Google et IBM. Pour donner un ordre de grandeur, un ordinateur classique est doté de processeurs de plusieurs milliards de bits (0 ou 1) quand les prototypes quantiques manipulent moins d’une centaine de qubits. Le prototype Sycamore de Google, par exemple, possède seulement 53 qubits. Par ailleurs, ces prototypes sont sujets à des erreurs de calculs, ce qui rend impossible l’exécution d’algorithmes quantiques vraiment utiles.

Qu’est-ce qu’un algorithme quantique ?

Pour un ordinateur classique, écrire un algorithme revient à créer un circuit logique avec ce qu’on appelle des portes logiques ^[1]. Ces portes logiques exécutent des opérations élémentaires. Elles reçoivent un ou plusieurs bits d’information en entrée (0 et 1), et en fonction de leur valeur, calculent une sortie : 0 ou 1. Il existe toute une variété de portes logiques qui réalisent différents types d’opérations élémentaires. De façon similaire, les algorithmes quantiques reposent sur des circuits quantiques composés de plusieurs portes logiques quantiques. La différence étant que la sortie n’est pas dans l’état 0 ou 1, mais dans une superposition de ces deux états.

Qu’est-ce que cela implique ?

Mathématiquement, une superposition quantique est une somme de vecteurs dont les coefficients, appelés amplitudes, peuvent être négatifs, ce qui est impossible avec les vecteurs de probabilités dans le cas classique. Les mathématiques qui en découlent sont donc complètement différentes puisque les probabilités sont négatives. D’une certaine façon, la superposition courbe l’espace des probabilités avec une métrique différente. Et cette géométrie particulière permet de résoudre des problèmes plus rapidement, simplement parce qu’on les regarde dans un espace différent.

Par exemple ?

Un bon exemple est la transformée de Fourier, très connue des physiciens et des ingénieurs. Sans rentrer dans le détail, la transformée de Fourier est un outil mathématique qui permet de regarder les signaux autrement. Elle est utilisée dans de nombreuses applications de traitement du signal, notamment pour faire de la compression audio, de la reconnaissance vocale ou des transmissions numériques. Si vous vous souvenez des oscilloscopes, au lycée, ils sont équipés d’une touche qui permet d’afficher la transformée de Fourier d’un signal. Cela paraît automatique à première vue, mais en réalité il y a beaucoup de calculs derrière. Or, en informatique quantique, il existe une porte logique – la porte de Hadamard – qui permet, lorsqu’elle est appliquée sur plusieurs bits quantiques, de calculer la transformée de Fourier quasi instantanément. Et cela uniquement parce que l’on travaille dans un espace géométrique où elle est naturellement présente. Résultat : le gain obtenu pour calculer la transformée de Fourier avec un ordinateur quantique est exponentiel par rapport à un ordinateur classique.

L’ordinateur quantique n’existe pas encore. Pourtant, vous travaillez sur des algorithmes quantiques. Comment est-ce possible ?   

Il faut bien comprendre que la recherche en informatique théorique consiste à se poser des questions sur des problèmes qu’on ne sait pas encore résoudre, et d’anticiper ceux qui pourraient survenir. À cet égard, les recherches que je mène sont très en amont. Concernant les algorithmes quantiques, le modèle de calcul de l’informatique quantique existe depuis les années 1980 (lire encadré). On peut donc tout à fait imaginer de nouveaux algorithmes qui pourraient tirer profit d’un ordinateur quantique, même si celui-ci n’existe pas. Dès 1995, le physicien Peter Shor a ainsi eu le génie d’établir un lien entre le problème de la factorisation, que j’ai évoqué plus haut, et la transformée de Fourier quantique. Ce sera l’objet d’un de mes cours au Collège de France. De cette idée est né le célèbre algorithme de Shor qui permettrait de casser la plupart des protocoles de chiffrement que nous utilisons aujourd’hui.

Lesquels ?

En cryptographie, il existe deux types de chiffrement : celui à clé secrète et celui à clé publique. Dans le premier, chacun possède un code secret qui a été échangé lors d’une rencontre préalable et qui permet de déchiffrer un message. En pratique, cela peut être une clé USB ou un disque dur par exemple. Cette cryptographie à clé secrète peut être affaiblie par les algorithmes quantiques, mais elle reste globalement sûre. C’est la seconde famille – la cryptographie à clé publique – qui s’effondre avec les algorithmes quantiques. En effet, les principaux protocoles de chiffrement, tels que le chiffrement RSA utilisé notamment dans les communications numériques, les transactions bancaires ou l’authentification en ligne, reposent sur la factorisation de très grands nombres en leurs facteurs premiers. Or, comme nous l’avons déjà évoqué, l’algorithme de Shor permettrait à un ordinateur quantique de faire cette opération.

Les enjeux sont donc très concrets...

Oui. L’algorithme de Shor a été la première application spectaculaire de l’algorithmique quantique, car il permettrait de gagner un temps potentiellement exponentiel pour la factorisation. Je précise « potentiellement » parce que, au fond, la sécurité n’est jamais prouvée ! Rien ne dit qu’un jour quelqu’un ne découvre pas un moyen de casser le chiffrement RSA par un moyen classique. On suppose que c’est très difficile à faire avec un ordinateur classique et on a raison jusqu’à preuve du contraire. Toujours est-il que l’existence d’un ordinateur quantique pourrait menacer la sécurité informatique. C’est la raison pour laquelle l’Institut national américain des normes et de la technologie (NIST) a lancé en 2016 un programme dédié à la cryptographie dite « post-quantique ».

De quoi s’agit-il ?

C’est un programme lancé pour améliorer les protocoles cryptographiques actuels et en découvrir de nouveaux, de sorte qu’ils résistent aux assauts éventuels d’un ordinateur quantique. Concrètement, les cryptographes ont besoin de savoir à quoi pourrait ressembler la meilleure attaque quantique possible dans les cinquante prochaines années afin d’adapter leurs systèmes de sécurité en conséquence. Ils viennent donc voir des algorithmiciens quantiques comme moi et nous demandent de combien de qubits, d’opérations et de temps de calcul nous avons théoriquement besoin pour casser tel ou tel protocole de sécurité. Nous développons ainsi des outils théoriques qui aident la communauté des cryptographies à imaginer et à dimensionner des systèmes de sécurité classiques qui résisteraient aux attaques d’un ordinateur quantique.

La cryptographie n’est pas le seul problème auquel vous vous intéressez...

Un autre volet de mes recherches consiste à passer en revue tous les concepts algorithmiques qui existent et essayer de les convertir en quantique afin d’en estimer le gain. C’est-à-dire évaluer de quel ordre de grandeur le calcul pourrait être accéléré. C’est un travail titanesque ! Il permet de se rendre compte que le gain n’est pas toujours exponentiel. Pour certains problèmes, un algorithme quantique ne fera pas mieux que son analogue classique. Pour d’autres, le gain peut être polynomial ou quadratique. Dans ce dernier cas, un ordinateur quantique résoudra un problème en dix étapes quand un ordinateur classique en aura besoin de cent.

Pouvez-vous donner un exemple ?

Prenez un annuaire téléphonique, avec des contacts classés par ordre alphabétique. Si l’on cherche le numéro d’une personne dont on connaît le nom, on tombera assez rapidement sur la bonne page. On fait ce que l’on appelle une recherche dichotomique. Le temps de cette recherche augmente de façon logarithmique avec la taille de l’annuaire. Il est intéressant de noter que, pour une telle application, un ordinateur quantique ne ferait pas mieux qu’un ordinateur classique. Il n’y a donc pas de plus-value. En revanche, la démarche inverse serait accélérée. Si j’ai à ma disposition un numéro et que je dois retrouver le nom correspondant, il faut faire des essais au hasard. Cela peut être très long. Avec un ordinateur quantique qui utilise l’algorithme de Grover ^[2], le gain de temps serait quadratique : il faudrait à cette machine √n étapes au lieu de n étapes. Cette procédure est la clé de voûte de nombreuses applications, notamment en optimisation combinatoire.

Une de vos démarches consiste aussi à partir de certains problèmes complexes et imaginer des algorithmes pour les résoudre. Pouvez-vous nous décrire cette démarche ?

La façon dont on avance dans cette recherche de nouvelles idées algorithmiques est la suivante : on identifie d’abord un problème dit « difficile ». Souvent on le simplifie à l’extrême pour qu’il n’en reste que la difficulté première – fondamentale. Cela donne des problèmes d’énoncés assez simplistes a priori, mais pas simples à résoudre pour autant. Je me suis ainsi beaucoup intéressé à la recherche de triangles dans les graphes. Typiquement, il s’agit de trouver un réseau de trois amis sur un réseau social, de sorte que tout le monde se connaisse. Cela paraît simple à première vue. Et pourtant, nous ne savons pas si l’algorithme actuellement connu est le meilleur possible. Dès lors, il faut trouver une nouvelle idée algorithmique. On tourne alors le problème, on essaie d’avoir une intuition. C’est un processus dans lequel on fait des allers-retours entre la recherche d’une meilleure solution et la preuve que l’on ne peut en trouver de meilleures. Si l’on n’en trouve pas, il y a nécessairement une raison propre au problème qu’on essaye de mettre en évidence mathématiquement. Et si l’on ne parvient pas à apporter cette preuve, alors cet échec met souvent en évidence une faille algorithmique du problème qui n’avait pas été exploitée. Ce va-et-vient s’accompagne très souvent de nouvelles idées, méthodes et outils dont l’impact dépasse le problème initialement étudié. Souvent, un tout petit progrès – un algorithme un peu plus rapide par exemple – aura nécessité de développer une nouvelle idée algorithmique, qui elle-même bénéficiera à d’autres applications. C’est vraiment l’identification de ces difficultés qui permet de faire avancer la discipline.

Tout ce travail ne serait-il pas vain si la construction d’un ordinateur quantique s’avérait impossible ?

Plusieurs collègues pensent que si l’on arrive à démontrer qu’il est impossible de construire un ordinateur quantique aussi puissant que l’on voudrait, ce serait un grand résultat scientifique. Cela apporterait une compréhension plus complète de la physique quantique. Dès lors, il faudra modifier le modèle de calcul propre aux ordinateurs quantiques. Des ajustements, comme la réduction de la mémoire quantique ^[3], seront nécessaires. Or, je m’intéresse depuis quelque temps à écrire des algorithmes qui ont besoin de peu de mémoire quantique. Je me suis ainsi aperçu que si une machine quantique dispose de trop peu de mémoire, alors cette accélération du calcul disparaît totalement. C’est important d’étudier cela, car les technologies qui viendront prochainement auront peut-être quelques milliers de qubits mais pas plusieurs milliards. Elles ne pourront donc pas utiliser beaucoup de mémoire. D’autres collègues travaillent sur des sujets connexes et imaginent ce que pourraient être des ordinateurs avec des mémoires partiellement quantiques. On aurait un disque dur classique, mais on pourrait en lire le contenu de façon quantique, avec un algorithme de type Grover. C’est un autre modèle de mémoire, mais qui pourrait inspirer les physiciens pour de futures réalisations.

De grands industriels comme Intel, Microsoft, Google, Atos ou IBM ont investi le champ de l’informatique quantique. Comment voyez-vous leur présence ?

En informatique, il y a toujours eu une longue chaîne de production entre la recherche et le développement de logiciels. Ce n’était pas le cas en informatique quantique où nous étions quelques algorithmiciens théoriciens d’un côté, et physiciens expérimentaux de l’autre qui menaient des expériences sur des prototypes de quelques dizaines de bits quantiques. Ces industriels ont permis d’aller beaucoup plus vite qu’on ne le pensait, et ont contribué à la création d’un écosystème qui permet aujourd’hui de mettre en place cette chaîne de production. C’est important, car ce ne sont pas des gens comme moi qui vont trouver les premières applications concrètes de machines de 100 ou 1 000 bits quantiques. En revanche, sans doute certains de mes travaux donneront-ils des idées à d’autres personnes faisant partie de cet écosystème pour découvrir ces applications attendues.

Quel message souhaiteriez-vous transmettre à des étudiants qui voudraient se lancer dans l’informatique quantique ? 

En termes de débouchés académiques : de nombreuses universités ouvrent des postes partout dans le monde. C’est une discipline où l’on peut facilement trouver une bourse de thèse et un postdoc. Par ailleurs, les compétences que l’on développe en informatique quantique sont utiles dans de nombreux autres domaines. Certains de mes étudiants sont ainsi partis faire des mathématiques financières ou sont partis dans les GAFA (Google, Apple, Facebook et Amazon). Ce n'est pas grave si l’on ne continue pas en informatique quantique : la compétence acquise est utile dans d'autres disciplines allant des mathématiques appliquées à l'informatique. En outre, c’est un milieu très soudé, tolérant, ouvert, paritaire et coopératif. Comme je vous l’expliquais, un écosystème est en train de se créer autour de l’informatique quantique. Il y aura donc des opportunités d'emplois. Et dans cet écosystème chacun peut trouver sa place.

Propos recueillis par Gautier Cariou

Quand Feynman imagine l’ordinateur quantique

En 1981, à la première conférence « Physics and computation », organisée au Massachusetts Institute of Technology (MIT), le prix Nobel de physique américain Richard Feynman se demande si les systèmes quantiques peuvent être simulés par un ordinateur classique. Selon lui, la complexité de ces simulations demanderait des ressources et un temps de calcul exponentiels. Il évoque alors l’idée d’utiliser les propriétés de la physique quantique pour calculer autrement, de façon à réduire cette complexité. Il imagine ainsi le concept d’ordinateur quantique. Quelques années plus tard, en 1985, le physicien israélo-britannique David Deutsch définit la notion de machine de Turing quantique. Au début des années 1990, les physiciens Ethan Bernstein, Umesh Vazirani, Peter Shor et Lov Grover imaginent les premiers algorithmes quantiques. Le développement de l’algorithmique quantique n’a jamais cessé depuis.

Définitions

[1] Une porte logique est une entité informatique qui transforme une information binaire en une autre. Une porte NOT, par exemple, transforme un bit en entrée en son inverse. 1 devient 0 et 0 devient 1. Il existe toute une variété de portes logiques qui permettent aux ordinateurs d’exécuter de nombreuses tâches. Ces portes reposent sur des composants électroniques : les transistors. Les processeurs de nos ordinateurs en possèdent des milliards. Dans les processeurs quantiques actuels, les portes quantiques reposent sur d’autres systèmes physiques : des ions et des atomes piégés ou encore des circuits électriques refroidis à une température proche du zéro absolu.

[2] Imaginé par Lov Grover en 1996, il s’agit d’un algorithme de recherche permettant à un ordinateur quantique de retrouver un ou plusieurs éléments dans une base de données en √n étapes au lieu de n étapes avec une approche classique.

[3] Une mémoire quantique est un des éléments nécessaires à la construction d’un ordinateur quantique. Il s’agit d’un dispositif qui permettrait de stocker l’information quantique.