La preuve théorique de la capacité des calculateurs quantiques à surpasser leurs homologues classiques n’est plus à faire. Plusieurs dizaines d’algorithmes quantiques ont déjà été découverts présentant une accélération plus ou moins importante sur leurs équivalents classiques. Dans certains cas ce « speedup » peut être exponentiel dans la taille du problème traité, rendant théoriquement possibles des calculs impossibles à effectuer en des temps « humainement acceptables » sur les ordinateurs classiques les plus puissants.

L’étendue des applications qui pourraient bénéficier d’un tel « avantage quantique » est cependant aujourd’hui encore difficile à préciser, ceci d’autant plus que la compétition entre moyens de calcul quantiques et classiques stimule la recherche sur les seconds. Ces dernières années, des techniques sophistiquées d’optimisation algorithmique classique ont ainsi conduit à relativiser plusieurs preuves supposées de la fameuse « suprématie quantique » attendue.

Si la supériorité théorique des calculateurs quantiques pour certaines classes de problèmes est considérée comme acquise, la possibilité de leur mise au point pratique continue en revanche de faire débat. Certains physiciens considèrent qu’il sera extrêmement difficile de maintenir en conditions opérationnelles ces calculateurs car leurs propriétés fondamentales, sur lesquelles repose leur puissance de calcul (superposition d’états, intrication), sont extrêmement sensibles à leur environnement (vibrations, variations de température, champs électromagnétiques…). D’autres sont au contraire plus confiants, s’appuyant sur les progrès constants réalisés ces dernières années dans la réalisation et la manipulation de qubits de plus en plus robustes aux erreurs.

À côté du calcul proprement dit, d’autres applications de la « seconde révolution quantique » sont également attendues. Même si la cryptographie et les télécommunications quantiques nécessiteront encore du temps avant de pouvoir être mises en œuvre en pratique, fondamentalement pour les mêmes raisons que celles évoquées ci-dessus pour ce qui concerne les ordinateurs, ces techniques pourraient, si elles voient le jour, bouleverser profondément les technologies de l’information. Les États et les entreprises s’y préparent déjà en anticipant les futures attaques sur la cybersécurité rendues possibles par la puissance de calcul des ordinateurs quantiques et en s’en protégeant par de nouvelles méthodes de cryptographie classiques dites « post-quantiques », c’est-à-dire capables de résister à ces attaques, à la différence notable du chiffrement RSA. La métrologie quantique, quant à elle, progresse continûment depuis ces dernières années et a déjà atteint un degré de maturité bien supérieur à celui des ordinateurs quantiques, avec de nombreuses applications industrielles à la clé.

Enfin, il se pourrait que l’« avantage quantique » attendu se manifeste également sur le plan énergétique et pas seulement sur celui de la puissance de calcul. Les ordinateurs quantiques sont en effet susceptibles de consommer beaucoup moins d’énergie que leurs homologues classiques, même si beaucoup de travail reste à faire pour maîtriser et évaluer concrètement la consommation énergétique de futurs calculateurs quantiques opérationnels.

Définir une stratégie de R&D et d’investissement dans un contexte aussi incertain n’est pas chose facile, ceci tout d’abord parce que plusieurs technologies sont aujourd’hui en concurrence pour la réalisation des qubits sans qu’il soit possible à cette étape d’identifier avec certitude celles qui finiront par s’imposer (supraconducteurs, atomes froids, photons, silicium…). Sur ce domaine particulier, la France dispose probablement d’une avance remarquable dans certaines de ces technologies (atomes froids et photonique en particulier), en témoigne les nombreuses spin-off issues de nos laboratoires de physique dont l’excellence scientifique dans le domaine est reconnue internationalement.

Une stratégie d’investissement public devrait être conséquente compte tenu des enjeux tout en restant prudente compte tenu des fortes incertitudes techniques qui subsistent, et qui pourraient conduire à un « hiver du quantique » comme l’IA en a connu un à la fin des années 1980, avant de rebondir avec le succès que l’on sait. Elle devra éviter un saupoudrage inefficace pour se concentrer sur les domaines d’excellence français, en particulier sur celui cité ci-dessus des technologies à la base des qubits. Elle devra s’appuyer sur les grands organismes de recherche impliqués dans le domaine (Universités, CNRS, INRIA, CEA) et mobiliser les industriels pour définir les cas d’usage et expérimenter les technologies disponibles. Enfin elle devra bien sûr reposer sur des coopérations internationales, en particulier européennes.

Marc Porcheron

Temps de lecture : 16 minutes

Au début du 20ᵉ siècle, une poignée de physiciens de génie transformèrent notre compréhension du monde en mettant à jour les propriétés étranges de la matière à l’échelle atomique. De cette « première révolution quantique » sont nées de nombreuses applications qui font partie aujourd’hui de notre quotidien : transistors, lasers, IRM… Nous sommes aujourd’hui à l’aube d’une « seconde révolution quantique », rendue possible par les progrès réalisés ces dernières années dans la manipulation d’objet microscopiques uniques et l’exploitation de leurs propriétés, et dont l’une des applications majeures pourrait être l’ordinateur quantique. Quels usages peut-on imaginer pour ces calculateurs ? Quels avantages sur leurs homologues classiques peut-on espérer ? Quelles difficultés devront être surmontées pour les rendre opérationnels ? Quelle stratégie d’investissement public leur consacrer ? Autant de questions complexes sur lesquelles cette note propose un éclairage, sans prétendre épuiser le débat.

La preuve théorique d’un avantage quantique n’est plus à faire

Deux usages principaux des calculateurs quantiques sont envisagés :

1. Comme simulateur, c’est-à-dire comme machine capable de simuler l’évolution d’un système physique selon les lois de la physique quantique ;
2. Comme ordinateur proprement dit, c’est-à-dire comme machine de Turing capable de résoudre n’importe quel problème décidable au sens de la théorie de la calculabilité[i].

Sur ces deux usages, la preuve théorique d’un « avantage » des calculateurs quantiques sur leurs homologues classiques n’est plus à faire.

Sur le premier usage, il paraît difficile de contester l’affirmation de Richard Feynman selon laquelle simuler en toute généralité la réalité physique au niveau quantique en des temps de calcul « raisonnables » est hors de portée d’un ordinateur classique, en raison du caractère intrinsèquement exponentiel dans le nombre de particules de cette simulation. Son célèbre article de 1982 sur le sujet est d’ailleurs considéré comme l’acte de naissance du Quantum Computing[1].

Sur le second usage, l’algorithme quantique de Peter Shor, qui date déjà de 1994, fournit un exemple d’accélération (speedup) exponentielle sur un problème pour lequel on soupçonne qu’il n’existe pas d’algorithme classique polynomial, la factorisation des entiers[2]. La sécurité des communications sur internet dans le monde étant aujourd’hui assurée en grande partie par le chiffrement RSA[3] qui repose précisément sur la difficulté à factoriser des entiers de grande taille sur un ordinateur classique, on comprend que la découverte de cet algorithme ait sorti le Quantum Computing des laboratoires de recherche fondamentale et provoqué le développement impressionnant du domaine qu’on connaît aujourd’hui. Au-delà, il existe déjà plusieurs dizaines d’algorithmes quantiques présentant des speedups prouvés plus ou moins importants par rapport à leurs équivalents classiques[4].

À noter cependant que les classes précises de problèmes sur lesquelles l’algorithmique quantique pourrait fournir des speedups significatifs par rapport à l’algorithmique classique ne sont pas encore complètement établies[ii].

Il est d’ailleurs remarquable de constater que les avancées dans le champ de l’algorithmique quantique stimulent les recherches dans celui de l’algorithmique classique, rendant l’issue de la compétition entre les deux moyens de calcul sur des problèmes spécifiques d’autant plus hasardeuse. Plusieurs annonces de preuves expérimentales d’avantage ou de « suprématie » quantique ‑ c’est-à-dire dire de preuves qu’un calcul réalisé par des moyens quantiques ne pouvait être effectué en des temps « humainement acceptables » par des moyens classiques ‑, ont été ainsi battues en brèche ces dernières années, les speedups annoncés ayant dû finalement être sévèrement revus à la baisse, après que les problèmes adressés ont été résolus par des moyens de calcul classiques spécifiquement optimisés, ou que des algorithmes classiques efficaces « inspirés du quantique » (quantum inspired) aient été découverts pour résoudre les mêmes problèmes[iii].

En résumé, si des calculateurs/simulateurs quantiques voyaient le jour, leur avènement constituerait un « saut » scientifique et technologique sans doute majeur pour certains usages hors de portée des ordinateurs classiques, mais l’étendue de leurs applications reste encore à préciser.

La preuve pratique de la réalisabilité de l’ordinateur quantique reste à faire

La mise au point opérationnelle de tels calculateurs pose des problèmes pratiques et théoriques énormes, à ce stade non résolus.

La puissance attendue des calculateurs quantiques repose fondamentalement sur la propriété de superposition d’états qui permet à un qubit d’être à un instant donné dans une combinaison de l’état « 0 » et l’état « 1 », là où son homologue classique occupe l’un de ces deux états à l’exclusion de l’autre.

Conséquence, une mémoire quantique de n qubits stocke à un instant donné une combinaison des 2ⁿ mots codables sur n bits classiques. De plus, chaque opérateur implémenté par une porte quantique transforme globalement cette superposition d’états, réalisant une forme de parallélisme inaccessible à un calculateur classique[iv].

Exploiter toute la puissance d’un calculateur quantique nécessite donc d’être capable de maintenir un système de qubits dans un tel état de superposition, le temps du calcul ou de la simulation d’intérêt. Or, ces états de superposition, majoritairement intriqués[v], sont extrêmement fragiles et sensibles aux interactions du système avec son environnement (vibrations, variations de température, champs électromagnétiques…). Celles-ci, assimilables à un bruit, sont susceptibles de provoquer l’effondrement de la fonction d’onde du système, projetant celui-ci dans un état classique non désiré en faisant disparaître la superposition (décohérence). Un exemple typique d’une telle interaction est la mesure, mais celle-ci est contrôlée et effectuée en fin de calcul pour observer, avec une certaine probabilité, l’état final déterministe du système censé fournir la solution du problème traité.

En pratique, pour limiter la décohérence, le système doit être isolé au maximum de toute interaction non-contrôlée avec son environnement, un défi majeur à la fois de physique fondamentale et d’ingénierie, qui se pose différemment suivant les technologies de qubits utilisées. Par exemple, toutes les technologies à base de supraconducteurs doivent pour cette raison fonctionner à des températures proches du zéro absolu, ce qui nécessite le développement de système complexes de cryogénie.

Sur un plan plus fondamental, cette question de la limite du nombre de qubits possiblement maintenus dans un état intriqué renvoie à celle, vertigineuse, de la frontière entre le monde quantique et le monde classique (le nôtre) où ces propriétés étranges que l’on cherche ici à exploiter pour le calcul disparaissent.

Sur cette question essentielle de la réalisabilité de ce que Serge Haroche appelle dans sa leçon inaugurale au Collège de France de 2001 un « gigantesque chat de Schrödinger calculateur », deux visions s’opposent chez les physiciens, respectivement incarnées par deux de nos prix Nobel : celle du même Serge Haroche, qui ne croit pas que cela soit possible, en tout cas pas avant des décennies ;  celle d’Alain Aspect, qui pense au contraire qu’on pourra à moyen terme arriver à des calculateurs de taille certes encore limitée (de l’ordre de quelques centaines de qubits) mais déjà utiles, sur la base des indiscutables progrès réalisés ces dernières années dans la maîtrise de certaines technologies à la base des qubits, en particulier celle des atomes froids que promeut son laboratoire, l’Institut d’Optique, via sa spin-off Pasqal.

Il semble impossible de trancher entre ces deux points de vue, à cette étape.

À noter que ce défi théorique et technologique est naturellement mené de pair avec celui visant à développer des techniques de correction d’erreurs permettant de rendre les calculateurs quantiques plus robustes au phénomène de décohérence. Ces techniques nécessitent l’adjonction d’un grand nombre de qubits « physiques » à un qubit « logique » afin de robustifier celui-ci et le rendre exploitable comme unité de calcul. On estimait par exemple en 2019 à 20 millions le nombre de qubits bruités nécessaire pour implémenter l’algorithme de Shor sur un calculateur quantique capable de casser les clés RSA de 2048 bits en 8 heures[5], alors que la même performance serait atteinte avec de l’ordre de 20 000 qubits « parfaits ». Mais des progrès constants sont réalisés dans ce domaine. Par exemple, la start-up française Alice & Bob développe une technique prometteuse pour les qubits supraconducteurs, permettant, selon elle, de réduire d’un facteur 60 le nombre de qubits auxiliaires requis pour fiabiliser un qubit logique.

Des domaines et des applications connexes importants

Au-delà des deux usages fondamentaux mentionnés jusqu’ici, il faut noter d’autres champs applicatifs ou d’intérêts connexes des technologies quantiques, eux aussi très importants.

La cryptographie est un champ sur lequel l’impact des technologies quantiques est déjà, et pourrait-être encore plus à l’avenir, fondamental compte tenu des enjeux économiques et géopolitique de ce domaine. D’une part, des techniques classiques de chiffrement dites « post-quantiques », c’est-à-dire capables de résister à des attaques futures comme celle de l’algorithme de Shor sur le chiffrement RSA, sont déjà mises au point et vont se diffuser dans l’industrie dans les années à venir ; d’autre part, l’utilisation de techniques quantiques pour crypter les communications, en théorie de manière inviolable, pourrait bouleverser ce domaine, même s’il reste encore beaucoup d’incertitudes techniques sur le sujet.

Un autre point, potentiellement crucial, concerne la consommation énergétique des calculateurs[6]. Et sur ce point également il faut distinguer le potentiel théorique du calcul quantique de la réalité pratique. En théorie, en raison de sa réversibilité, le calcul quantique pourrait ne pas consommer d’énergie du tout. Plus pragmatiquement, le simple fait d’accélérer des calculs requérant aujourd’hui des temps très long sur des architectures classiques massivement parallèle pourrait conférer naturellement un avantage énergétique du calcul quantique sur le calcul classique.

En pratique, il parait compliqué de garantir cet avantage compte tenu de la consommation des systèmes auxiliaires requis pour faire fonctionner de manière opérationnelle ces calculateurs. Cette question se pose différemment suivant les technologies mises en œuvre pour implémenter les qubits. Par exemple, comme noté plus haut, toutes les technologies à base de supraconducteurs nécessitent des systèmes auxiliaires énergivores de cryogénie pour maintenir une température proche du zéro absolu ; à l’inverse la technologie des atomes froids requiert en théorie une consommation moindre, essentiellement réduite à celles des lasers utilisés pour manipuler les atomes ; les technologies photoniques, quant à elles, devraient pouvoir fonctionner « quasiment » à température ambiante.

Enfin, il ne faudrait pas négliger le domaine de la métrologie quantique (gravimètres quantiques…), en plein développement et avec de nombreuses applications industrielles, et qui se trouve à un niveau de maturité bien plus avancé que celui des calculateurs.

Quelle stratégie d’investissement en France ?

Quelques éléments pour éclairer cette question délicate :

• La France et l’Europe possèdent des compétences de premier plan dans le domaine quantique, en particulier en physique fondamentale, mais aussi en cryptographie et en métrologie ;
• En témoigne l’émergence de quelques « pépites » remarquables : Pasqal, Quandela, C12, Alice & Bob, Quobly (ex Siquance issue du CEA-Leiti), Welinq (communications quantiques)… ;
• Il est impossible de dire aujourd’hui quelle technologie s’imposera (ou quelles technologies s’imposeront) pour la réalisation des qubits ;
• Il est impossible de prédire précisément à quelle échéance nous sortirons de la période dite des Noizy Intermediate Scale Quantum Computers (NISQ), c’est-à-dire des calculateurs encore bruités et possédant un nombre limité de qubits, pour entrer dans celle dite des Large Scale Quantum Computers (LSQ), c’est-à-dire des calculateurs robustes aux erreurs, possédant un grand nombre de qubits, capables par exemple d’implémenter l’algorithme de Shor ; sachant qu’il existe un risque estimé comme très important par certains physiciens qu’on n’y parvienne jamais ;
• Le quantique n’est pas à l’abri d’un « hiver » comme en a connu l’IA à la fin des années 1980 ; on peut penser qu’il se trouve plus ou moins au sommet de la bosse de la courbe de Gartner, soit au moment critique où les promesses de retour sur investissement tardent à se concrétiser en raison de difficultés techniques non surmontées, et ou les investissements s’effondrent, avant de repartir lentement à la hausse pour se concentrer sur les technologies confirmées. Cette tendance à la baisse semble s’être confirmé en 2022-2023. C’est le cas en particulier aux États-Unis où on peut également noter que les investissements dans le domaine quantique, bien que non-négligeables, restent très inférieurs à ceux effectués dans l’IA ;
• En plus des enjeux sur le hardware quantique, il existe également des enjeux autour du software quantique qui risque lui aussi d’être dominé par des acteurs américains (environnements de développement, OS spécifiques…);
• Dans tous les cas, il paraît difficile pour l’Europe, et à fortiori pour la France, de rivaliser avec la capacité d’investissement des Etats-Unis (GAFAM, IBM, INTEL, NVIDIA…) et de la Chine.

Pour conclure, et tenter de répondre concrètement à la question, les points ci-dessus devraient conduire à une stratégie d’investissement public conséquente compte tenu des enjeux mais prudente compte tenu des incertitudes techniques, et axée sur des cibles précises en bannissant un « saupoudrage » trop large et inefficace.

Une telle stratégie devrait être guidée par les objectifs suivants :

• Ne surtout pas s’engager à cette étape de manière exclusive dans une filière spécifique de réalisation des qubits ;
• Soutenir en priorité et protéger de la concurrence étrangère les domaines où la France et l’Europe sont déjà en pointe, en particulier celui du hardware quantique, via les startups citées plus haut et qui pourraient jouer dans le futur des rôles clés en fonction des technologies finalement dominantes ;
• Mobiliser les industriels dans des projets collaboratifs conséquents avec les laboratoires académiques et les start-ups, afin de spécifier les cas d’usage et d’expérimenter les technologies disponibles ;
• Soutenir des projets de R&D interdisciplinaires sur des questions fondamentales non encore maîtrisées, comme la définition précise de la complexité algorithmique quantique et de ses avantages sur l’algorithmique classique, le génie logiciel quantique, l’estimation la consommation énergétique des calculateurs. Ce soutien devrait évidemment s’appuyer sur des collaborations internationales, en particulier celles financées par les projets européens du Quantum FlagShip;
• À supposer qu’une ou des filières technologiques de fabrication des qubits actuellement développées par les startups françaises s’imposent, la question de structurer une filière industrielle complète du hard jusqu’au soft associée à ces technologies devrait se poser. À côté des collaborations européennes à définir, les grands organismes de recherche impliqués dans le domaine, le CNRS, l’INRIA et le CEA, devraient jouer un rôle clé comme acteurs publics dans une telle filière, même si ce n’est finalement pas les technologies d’implémentation des qubits qu’ils promeuvent aujourd’hui qui s’imposent finalement (silicium pour le CEA).

Marc Porcheron

******

[1]     Feynman, R.P. Simulating physics with computers. Int J Theor Phys 21, 467–488 (1982).

[2]     Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. quant-ph/9508027

[3]     Du nom de ses concepteurs : Ronald Rivest, Adi Shamir et Leonard Adleman.

[4]     Cf. https://quantumalgorithmzoo.org/

[5]     Craig Gidney, Martin Ekerå,  How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits https://arxiv.org/abs/1905.09749v3

[6]     Pour une introduction à la question et aux enjeux associés par une spécialiste française du sujet voir : Alexia Auffèves, Optimiser la consommation énergétique des calculateurs quantiques : un défi interdisciplinaire https://www.refletsdelaphysique.fr/articles/refdp/pdf/2021/02/refdp202169p16.pdf

[i]       La théorie de la complexité et de la calculabilité s’intéresse aux ressources en temps et en espace mémoire nécessaires à la résolution de problèmes et au calcul de fonctions par un processus « mécanisable », typiquement un algorithme. La thèse de Church-Turing, affirme que « toute fonction calculable sur les entiers est calculable par une machine de Turing », ces dernières constituant le modèle le plus utilisé pour formaliser le processus de calcul effectué par un ordinateur, auxquels tous les autres modèles universels sont équivalents (lambda calcul de Church, modèles de Post…). Il importe de garder à l’esprit que, contrairement à ce que la communication et la (mauvaise) vulgarisation scientifique sur les ordinateurs quantiques peuvent parfois laisser croire, ceux-ci, à supposer qu’ils voient le jour, ne permettront pas de résoudre des problèmes impossibles à résoudre sur un ordinateur classique ; et il en existe une infinité : décider si un programme informatique s’arrête ou pas, calculer exactement un nombre omega de Chaitin, déterminer la complexité de Kolmogorov d’une chaîne de caractères… On attend donc « seulement » des ordinateurs quantiques qu’ils permettent de résoudre plus efficacement que leurs homologues classiques certains problèmes, c’est-à-dire en consommant moins de temps de calcul et/ou de mémoire. À noter cependant qu’on peut quand même distinguer entre calculabilités théorique et pratique : un problème décidable ou une fonction calculable par un ordinateur classique disons en un siècle, peut être considéré comme pratiquement insoluble par une telle machine, et sa résolution par un ordinateur quantique en un temps « humainement acceptable » pourrait être considérée comme la résolution pratique d’un problème impossible à résoudre classiquement.

[ii]      La classe NP est la classe des problèmes qu’on ne sait pas résoudre en temps polynomial, mais dont on peut vérifier une solution en temps polynomial. Par exemple, on ne connaît pas d’algorithme polynomial permettant de déterminer si oui ou non un graphe comporte un chemin Hamiltonien, c’est-à-dire passant par tous ses sommets une et une seule fois ; les meilleurs algorithmes connus pour le faire sont exponentiels dans la taille du graphe. Par contre, un chemin étant donné, on peut vérifier en temps polynomial si oui ou non celui-ci est bien un chemin Hamiltonien du graphe en question. En raison de ce caractère polynomial quant à la vérification des solutions, la classe NP apparaît comme intermédiaire entre la classe P des problèmes polynomiaux, considérés « faciles » ou résolubles (tractable) sur un ordinateur, quel qu’il soit, et la classe EXP des problèmes exponentiels, considérés « difficiles » ou insolubles (intractable). On appelle NP-Difficile un problème au moins aussi difficile que tous les problèmes dans NP. En pratique, cela signifie que tout problème dans NP peut lui être réduit en temps polynomial. La classe NP-Complet, est la classe des problèmes qui sont à la fois NP-Difficiles et dans NP. Par exemple, le problème introduit ci-dessus : « Étant donné un graphe, celui-ci possède-t-il un chemin hamiltonien ? » est prouvé NP-Complet. Sa version « optimisation » : « Trouver, s’il existe, le chemin hamiltonien le plus court dans un graphe », à supposer que les arcs portent une valuation, est NP-Difficile. C’est exactement le problème dit du « Voyageur de commerce » (Traveling Salesman Problem, TSP).
À ce stade on soupçonne que les problèmes NP-Complets ne seront pas à la portée des ordinateurs quantiques, et il en va donc de même a fortiori pour les problèmes NP-Difficiles.
On ne sait pas aujourd’hui si P est égal à NP, et c’est là un des grands problèmes mathématiques ouverts. La très grande majorité des chercheurs du domaine pense que P ≠ NP. Si c’est bien le cas, alors on montre qu’il existe une classe de problème dits NP-Intermédiaires, qui sont dans NP sans être ni dans P ni NP-Complets ; c’est-à-dire de problèmes qui, sans être polynomiaux, ne sont pas aussi difficiles que les problèmes les plus difficiles de NP.
Le problème de la factorisation des entiers est soupçonné d’appartenir à cette classe (à supposer donc que P ≠ NP), ceci parce qu’on n’est pas arrivé jusqu’ici à démontrer qu’il soit NP-Complet. Or ce problème est résoluble en temps polynomial quantique par l’algorithme de Peter Shor. C’est ce qui peut laisser penser que cette classe de problèmes NP-Intermédiaires (toujours à supposer que P ≠ NP), soit inclue dans la classe BQP (Bounded-error Quantum Polynomial) des problèmes résolubles en temps polynomial par un ordinateur quantique. Mais il s’agit juste d’une potentialité, sans preuve à cette étape.
Enfin, il faut garder à l’esprit que l’appartenance d’un problème à une classe de complexité est sujette à évolution. Par exemple, on a cru pendant des décennies que le problème PRIME : « Étant donné un entier, celui-ci est-il premier ? » n’était pas dans P, jusqu’à ce qu’en 2002, un algorithme polynomial soit trouvé pour le résoudre (Agrawal Manindra, Neeraj Kayal & Nitin Saxena, PRIMES is in P, Annals of Mathematics 160(2): 781–93).

[iii]     En 2019, Google annonce avoir atteint la suprématie quantique en proposant un circuit de 53 qubits, baptisé Sycamore, capable de produire en quelques centaines de secondes une distribution particulière de nombres aléatoires, dont la génération sur l’ordinateur Summit le plus puissant d’IBM prendrait de l’ordre de 10 000 ans… Quelques semaines plus tard, une équipe d’IBM montrait qu’on pouvait reproduire le même calcul en 2,5 jours, en utilisant des techniques avancées de stockage sur disque des calculs intermédiaires, évitant ainsi l’encombrement de la RAM. (Cf. https://www.technologyreview.com/2019/10/22/132519/quantum-supremacy-from-google-not-so-fast-says-ibm/)
En 2016, Iordanis Kerenidis et Anupam Prakash proposent un algorithme quantique pour traiter le problème dit des « recommandations » ; il s’agit d’inférer les futures préférences d’agents sur la base de leurs choix précédents, un problème au cœur des mécanismes des propositions de produits faites aux clients des plateformes du type Netflix ou Amazon. Ce problème est formalisable en algèbre linéaire et résoluble en temps polynomial dans la dimension de la matrice représentant les préférences. Iordanis Kerenidis et Anupam Prakash adaptent un algorithme quantique de résolution de système linéaire, HHL (du nom de ses auteurs : Adam Harrow, Avinatan Hassidim, et Seth Lloyd), qui, sous certaines conditions, permet de résoudre un système linaire en temps polynomial dans le logarithme du nombre de variables. On a donc bien un speedup exponentiel entre l’approche quantique et l’approche classique, celle-ci, bien que polynomiale, se révélant en pratique intractable pour de très grandes matrices. Mais en 2018, Erwin Tang, une jeune étudiante de Scott Aaronson, un spécialiste américain du calcul quantique, propose un algorithme classique inspiré de l’algorithme quantique résolvant le problème avec la même complexité polylogarithmique. (cf. András Gilyén, Seth Lloyd et Ewin Tang, Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimensions, https://arxiv.org/abs/1811.04909)
En 2020, un chercheur du CEA et ses collègues, montrent qu’un ordinateur quantique « imparfait » c’est-à-dire bruité et soumis au phénomène de décohérence comme le sont tous les prototypes actuels, peut être efficacement simulé sur un ordinateur classique de la puissance d’un laptop standard. La méthode repose sur une technique de « compression d’états quantiques » qui permet d’accélérer la simulation classique d’un facteur exponentiel au prix d’une perte d’information comparable à celle de toute façon induite par la décohérence. Ces travaux suggèrent qu’en vue d’atteindre la fameuse suprématie quantique, il est sans doute plus important d’améliorer la fidélité des qubits que leur nombre. (Cf. Yiqing Zhou, E. Miles Stoudenmire, and Xavier Waintal, What Limits the Simulation of Quantum Computers? Phys. Rev. X 10, 041038, Nov. 2020)

[iv]    Le parallélisme quantique opère directement sur l’ensemble des paramètres de la superposition des 2ⁿ « états de base » présente en mémoire, chacun d’eux encodant un mot de n bits ; réaliser la même opération en parallélisme classique nécessiterait 2ⁿ processeurs synchronisés.

[v]     Les états intriqués sont des états de superposition particuliers « non-séparables », dans lesquels il existe des corrélations entre les résultats des mesures effectuées sur les composants du système, même si ceux-ci se trouvent à des distances aussi grandes que voulues les uns des autres.
Le fait que ces corrélations ne puissent pas s’expliquer par l’existence de « variables cachées » mais sont bien l’expression d’une forme de dépendance « non-locale » persistant dans l’espace-temps entre particules ayant interagi à un moment donné, a fait l’objet d’une controverse célèbre entre Niels Bohr et Albert Einstein, initiée par ce dernier et ses collègues Boris Podolsky et Nathan Rosen dans l’article de 1935 : « Can Quantum-Mechanical Description of Physical Reality Be Considered Complete ? ».
Ce fait a été définitivement établi par Alain Aspect et son équipe au début des années 1980 par leurs expériences fondées sur les travaux du physicien irlandais John Bell. Ces travaux, donnant finalement raison à Bohr et tort à Einstein sur ce point spécifique, ont valu à Alain Aspect le prix Nobel de physique en 2022.
Des applications importantes de l’intrication dans le cadre des communications quantiques ont déjà été identifiées et expérimentées en laboratoire (téléportation d’états, cryptographie inviolable) ; dans le cadre du calcul quantique proprement dit, la compréhension du rôle de l’intrication dans l’obtention de speedups significatifs sur l’algorithmique classique fait encore l’objet de travaux de recherche fondamentale (Cf. Richard Jozsa, Noah Linden, On the role of entanglement in quantum computational speed-up, https://arxiv.org/abs/quant-ph/0201143v2).
Ce qui est certain, c’est que la majorité des états quantiques étant intriqués, la suprématie quantique qui repose fondamentalement sur la nature exponentielle de la mémoire dans le nombre de qubits, ne pourra être atteinte sans la capacité à exploiter ces états intriqués dans les calculateurs.