Algorithmes quantiques : quand la physique quantique défie la thèse de Church-Turing

Algorithmes quantiques :
quand la physique quantique
défie la thèse de Church-Turing

Frédéric Magniez

Le texte original de Frédéric Magniez est paru sur le site du Collège de France [1] en prévision de la leçon inaugurale de la chaire annuelle Informatique et sciences numériques du Collège de France qu'il a prononcée le 1er avril 2021.

Une prouesse inutile ?

L'année 2021 sera sans aucun doute quantique ! Il y a à peine plus d'un an, Google réalisait un calcul sur un prototype de circuit quantique programmable. D'un point de vue technologique, la prouesse était encore inimaginable il y a seulement quelques années. D'un point de vue de la puissance de calcul, la tâche demandée est certes très spécifique, mais nécessiterait plusieurs milliers d'années de calcul sur toute autre machine existante, aussi puissante soit-elle ! Un vrai tournant venait donc d'être engagé. Cette année, un consortium européen va lancer une plate-forme de simulation et de programmation quantique rassemblant chercheurs et industriels issus de la physique et de l'informatique. Cette plate-forme utilisera une technologie quantique fournie par la start-up française Pasqal [2]. Enfin, l'État a annoncé en janvier 2021 un plan national quantique qui va voir la création de plusieurs centres dédiés à la recherche sur les technologies quantiques, dont l'informatique.

Le calcul effectué par Google fin 2019 revenait à lancer un gigantesque dé truqué ou faussé. Le calcul des probabilités de chaque face du dé est lié au circuit quantique programmé dans la machine de Google. La simulation d'un circuit quantique, même de petite taille (53 bits dans l'expérience de Google), est d'une telle complexité pour nos ordinateurs actuels qu'elle ne peut être réalisée en moins de plusieurs millénaires par ces derniers. En revanche, le lancer de ce dé est quasiment instantané sur le prototype quantique de Google, puisque ce dernier implémente directement ledit circuit quantique, et ce avec une précision satisfaisante, c'est-à-dire pour vérifier que le bon dé avait été lancé. Cette réalisation, même imparfaite, semble pour le moment impossible à réaliser autrement que quantiquement.

Cette prouesse semble loin de toute application pratique. Néanmoins, elle valide un courant de pensée remontant aux années 1980, en particulier aux propos du physicien Richard Feynman [3], affirmant que notre interprétation et compréhension de ce qui est calculable [4] devait évoluer. Elle remet en cause les fondements du calcul remontant à la thèse de Church-Turing [5]. Cette thèse, qui a évolué au fil des années, tendait à affirmer que tout progrès technologique ne remettrait jamais en cause le modèle mathématique du calcul défini par Church et Turing en 1936. Ce modèle permet de discerner ce qui est calculable [6] par une machine de ce qui ne l'est pas. Quelques décennies après, cette thèse avait été reformulée ainsi : tout modèle de calcul raisonnable peut être simulé efficacement par une machine de Turing probabiliste (c'est-à-dire ayant accès à une source d'aléa). La notion de complexité [7] y avait donc été ajoutée, rendant la thèse plus ambitieuse mais aussi plus fragile

Les fondations : Enigma bis ?

Cette thèse étendue de Church-Turing a donc été remise en question au tout début de l'informatique quantique, lorsque le physicien David Deutsch [8] définit en 1985 la notion de machine de Turing quantique, avec son lot de premiers algorithmes exponentiellement plus rapides que leurs équivalents déterministes (mais pas encore probabilistes). D'abord perçu comme curiosité, ce modèle de calcul finit par susciter intérêt et questionnements dans la communauté scientifique. Finalement en 1993, Bernstein et Vazirani construisent mathématiquement une machine universelle quantique efficace, c'est-à-dire le premier compilateur quantique (l'existence d'une machine programmable) qui valide mathématiquement le modèle de calcul (mais pas sa réalisation physique). En même temps arrive l'évidence qu'un ordinateur quantique peut être exponentiellement plus rapide qu'un ordinateur classique, c'est-à-dire qu'une machine de Turing probabiliste. Cependant, les problèmes résolus sont tous artificiels et semblent encore bien loin de toute application concrète.

C'est Simon puis Shor qui arrivent avec la première application algorithmique, et pas des moindres, en 1994, soit seulement une année après l'acceptation par la communauté du concept même de calcul quantique. En effet, cette application permettait de déchiffrer la plupart des messages cryptés par les mécanismes dits à clé publique, et de réduire à néant les procédés cryptographiques les utilisant (monnaie électronique, CB, vote électronique, authentification...). Heureusement, l'ordinateur quantique n'existe pas (encore) ! Pourtant cette découverte n'est pas sans rappeler les découvertes de Turing et la construction de la machine qui a permis de déchiffrer les messages allemands eux-mêmes chiffrés par la machine Enigma durant la deuxième guerre mondiale...

Les algorithmes quantiques : une nouvelle façon de penser

Néanmoins, deux décennies plus tard, alors que la possibilité d'une construction future d'un ordinateur quantique commençait à être prise au sérieux, une compétition scientifique internationale a été lancée en 2016 afin de définir les nouveaux standards de chiffrement postquantique [9], ouvrant la voie à une longue recherche puis standardisation toujours en cours. Une autre alternative repose pourtant dans l'utilisation relativement simple de fibre optique afin de communiquer en encodant l'information directement sur des photons. Il s'agit du protocole quantique d'échange de clé proposé par Bennett et Brassard en 1984, soit 10 années avant la découverte de l'algorithme de Shor [10]. En quelque sorte l'attaque et la parade reposent sur la même technologie, à ceci près que le protocole en question a déjà été construit et testé sur de grandes distances, un satellite dédié a même été envoyé par la Chine en 2016. L'Europe n'est pas en reste avec des projets d'infrastructure de grande envergure dédiés au déploiement de solutions quantiques de chiffrement. Cependant, ces solutions quantiques nécessitent des technologies spécifiques, alors que les solutions algorithmiques dites postquantiques pourraient être déployées sur les structures et ordinateurs actuels.

Depuis 1994, les applications (calcul scientifique, optimisation, recherche opérationnelle [11], simulation, apprentissage automatique, IA...) foisonnent dans tous les domaines où l'informatique joue un rôle crucial, et pour des tâches où nos ordinateurs actuels ne sont pas assez puissants. Mais surtout, les outils développés (transformée de Fourier quantique, estimation de phase, amplification d'amplitude, estimateur quantique, marche quantique, etc.) progressent continuellement, en impactant toutes les thématiques de l'informatique, en en créant de nouvelles (information quantique, complexité hamiltonienne, simulation quantique...), ou encore en tissant de nouveaux liens de l'informatique vers d'autres disciplines dont la physique, la chimie et les mathématiques.

Mais avant tout l'informatique quantique a introduit une nouvelle façon d'analyser, raisonner et démontrer. Les outils existants précédemment n'étant plus adaptés, il a fallu en créer de nouveaux. Apportant un nouveau regard mathématique à des questions anciennes, ces nouveaux outils ont permis de progresser sur des questions ouvertes depuis de nombreuses années. Cette démarche a été baptisée preuve ou méthode quantique. Une preuve quantique est un peu l'analogue des nombres complexes pour la trigonométrie ou encore l'électricité : un outil très puissant permettant de mener facilement des calculs difficiles, ou encore d'établir des preuves inaccessibles jusque-là, y compris dans des domaines pour lesquels ils n'ont pas été construits initialement. La dernière démonstration en date est la réfutation d'une célèbre conjecture en mathématiques (conjecture de Connes [12]) à l'aide d'un résultat en théorie de la complexité quantique.

Vision et formations nécessaires

Une fois tous ces algorithmes quantiques découverts, dont l'utilisation de certains serait à n'en pas douter révolutionnaire, la question de la possibilité de construire un ordinateur les exécutant fut donc de plus en plus pressante. L'importance d'un plan d'envergure a d'abord émané de tous les acteurs concernés, scientifiques comme industriels, avec une feuille de route et des jalons intermédiaires appropriés, puis fut largement soutenue par les politiques. Plusieurs plans ont vu le jour, dont un au niveau européen à travers le quantum flagship [13] en 2018, et celui national en 2021. L'avantage industriel que pourrait procurer la construction d'un ordinateur quantique [14], même imparfait, a créé une frénésie stimulante qui touche tous les secteurs stratégiques (finance, industrie, santé, sécurité...). Les progrès technologiques de grands groupes industriels, tels que Google et IBM par exemple, ont été de véritables locomotives, laissant apparaître rapidement que le plus grand défi serait de trouver une application à ces premiers prototypes, certes révolutionnaires, mais très éloignés des machines nécessaires aux applications précédemment découvertes en algorithmique quantique. En effet, non seulement ces machines sont petites, mais elles ont un taux d'erreur encore trop grand. Pourtant elles sont capables d'effectuer des calculs impossibles à réaliser classiquement, mais des calculs sans impact industriel actuellement.

Un véritable travail de fourmi s'est donc enclenché, mais, pour l'instant, avec une communauté encore trop petite. Les mêmes personnes ont actuellement en charge de comprendre et de maîtriser toutes les facettes du calcul quantique, de la modélisation à la réalisation expérimentale en passant par la solution algorithmique, son analyse, sa programmation et sa vérification, là où la chaîne de production constitue habituellement un véritable écosystème de l'informatique. Il nous faut donc nouer de multiples partenariats, construire et enseigner dans de nouvelles formations, afin de saisir cet unique défi que pourrait constituer ce nouveau tournant technologique.

C'est dans un tel contexte que l'opportunité d'occuper la chaire annuelle Informatique et sciences numériques 2020-2021 du Collège de France s'est présentée, avec l'idée de donner dans ce cadre un cours sur les algorithmes quantiques. L'objectif de ce cours ? Répondre à une demande croissante d'information et de formation de nombreux publics. Le public ciblé va des esprits curieux de saisir les possibilités et les limites du calcul quantique, aux acteurs des sciences informatiques au sens large : informaticiens, mathématiciens du numérique et physiciens des technologies quantiques, qu'ils soient étudiants, chercheurs, développeurs, entrepreneurs ou encore futurs utilisateurs des algorithmes quantiques.

En guise de conclusion, il convient de rappeler que c'est en France, en 1980, qu'a débuté la révolution quantique expérimentale lorsque l'expérience du groupe d'Alain Aspect (CNRS) a validé à Orsay les prédictions de la physique quantique, qui ne pouvaient s'expliquer par la physique classique seule. Puis le prix Nobel a été décerné en 2012 à Serge Haroche (Collège de France) pour ses travaux sur la manipulation de systèmes quantiques. Le versant informatique de cette révolution a, lui, débuté en 1994 conjointement aux travaux outre-Atlantique, grâce à la vision de Miklos Santha (directeur de recherche CNRS) dont l'équipe de recherche était basée aussi à Orsay. Rapidement, Miklos a su constituer un groupe qui essaime, fait des émules en France et attire des talents internationaux. À l'époque, le pari pouvait sembler risqué, mais dans les années 2000, les possibilités de recrutement au CNRS et à l'Université sont plus nombreuses, et plusieurs chercheurs sont recrutés afin de mieux comprendre les liens que tisse le traitement de l'information quantique entre informatique, mathématiques et physique.

Frédéric Magniez
Directeur de recherche CNRS,
directeur de l'IRIF et
professeur au Collège de France.

Paru le 1er avril 2021 sur )i( Interstices.
https://interstices.info/algorithmes-quantiques-quand-la-physique-quantique-defie-la-these-de-church-turing/

Cet article est sous licence Creative Commons (selon la juridiction française = Paternité - Pas de Modification). http://creativecommons.org/licenses/by-nd/2.0/fr/

NOTES

[1] https://www.college-de-france.fr/site/frederic-magniez/course-2020-2021.htm

[2] https://pasqal.io/

[3] https://fr.wikipedia.org/wiki/Richard_Feynman

[4] https://interstices.info/calculer-differemment/

[5] https://interstices.info/glossaire/these-de-church-turing/

[6] https://interstices.info/alan-turing-du-calculable-a-lindecidable/

[7] https://interstices.info/la-theorie-de-la-complexite-algorithmique/

[8] https://fr.wikipedia.org/wiki/David_Deutsch

[9] https://interstices.info/la-fragilite-inattendue-du-chiffrement-symetrique-dans-le-monde-post-quantique/

[10] https://interstices.info/lalgorithme-quantique-de-shor/

[11] https://interstices.info/a-propos-de-la-recherche-operationnelle/