L'avantage quantique a-t-il été atteint ? Ce que signifie l'affirmation

Dernière révision: · Rédaction de Qiaoyu

L'essentiel

  • L'avantage quantique (appelé d'abord suprématie quantique) désigne un ordinateur quantique programmable qui résout un problème qu'aucun ordinateur classique ne peut résoudre en un temps raisonnable, que le problème soit utile ou non.
  • John Preskill a introduit le terme lors d'un exposé de 2011, publié sous forme d'article arXiv en 2012.
  • Les tâches candidates sont l'échantillonnage de circuits aléatoires et l'échantillonnage de bosons ; leur difficulté repose sur la théorie de la complexité, non sur une démonstration.
  • L'expérience Sycamore de Google, en 2019, annonçait 200 secondes contre 10 000 ans, et IBM a répondu qu'une machine classique pouvait le faire en quelques jours.
  • Toute affirmation peut être provisoire, car les algorithmes classiques ne cessent de s'améliorer.
Un IBM Quantum System One au ThinkLab du centre de recherche IBM Thomas J. Watson à Yorktown Heights, dans l'État de New York
Image : OJB Quantum, CC BY 4.0, via Wikimedia Commons

L’avantage quantique est la démonstration qu’un ordinateur quantique programmable peut résoudre un problème qu’aucun ordinateur classique ne peut résoudre en un temps raisonnable, que ce problème soit utile ou non. L’ancien nom est la suprématie quantique. Plusieurs expériences depuis 2019 l’ont revendiqué, et plusieurs de ces revendications ont été contestées par des simulations classiques plus rapides. Cette note définit le terme, explique les tâches employées pour le tester et l’argument de théorie de la complexité qui les sous-tend, puis expose pourquoi une telle affirmation est difficile à trancher. Les expériences elles-mêmes sont examinées dans la deuxième partie, les preuves. Elle fait partie des notes de science.

La définition

Wikipédia en anglais décrit la suprématie quantique comme l’objectif de montrer qu’un ordinateur quantique programmable résout un problème qu’aucun ordinateur classique ne peut résoudre en un temps raisonnable, indépendamment de l’utilité du problème. C’est un objectif scientifique, non commercial. L’expérience peut être réalisée avec des dispositifs à court terme, car elle ne requiert aucune correction d’erreurs, seulement un circuit assez grand et assez propre pour que sa simulation classique devienne irréalisable.

Le terme vient de John Preskill. Son article arXiv 1203.5813, Quantum computing and the entanglement frontier, était un exposé de rapporteur à la 25e conférence Solvay, tenue du 19 au 22 octobre 2011, et a été mis en ligne en mars 2012. Son résumé emploie l’expression « quantum supremacy », entre guillemets, pour désigner le moment où un ordinateur quantique peut exécuter un algorithme qui résout un problème avec une accélération super-polynomiale par rapport aux ordinateurs classiques. Preskill a écrit plus tard l’hommage à un collègue cité dans la note sur Mark Wise.

L’expression « avantage quantique » est désormais largement employée pour le même jalon. Cette note traite les deux termes comme des synonymes.

Quelles tâches peuvent le montrer

Une tâche de test doit remplir trois conditions : un dispositif quantique peut l’exécuter, un ordinateur classique doit la trouver difficile, et le résultat doit pouvoir être vérifié. Les tâches proposées jusqu’ici favorisent les deux premières conditions.

Tâche Principe Origine de la difficulté
Échantillonnage de circuits aléatoires Exécuter une séquence aléatoire de portes quantiques sur de nombreux qubits et échantillonner les chaînes de bits en sortie Simuler l’état quantique complet de n qubits requiert une mémoire et un temps qui croissent exponentiellement avec n
Échantillonnage de bosons Envoyer des photons identiques dans un réseau de séparateurs de faisceau et enregistrer où ils ressortent Les probabilités de sortie font intervenir des permanents de matrices complexes, dont le calcul est #P-difficile
Échantillonnage IQP Échantillonner dans une famille restreinte de circuits quantiques Arguments de théorie de la complexité semblables aux précédents

L’échantillonnage de bosons a été introduit par Aaronson et Arkhipov, après des travaux antérieurs de Troyansky et Tishby. C’est un modèle non universel : il ne requiert que des sources de photons uniques, un interféromètre linéaire et des détecteurs, et non un ordinateur quantique complet. Wikipédia note qu’un échantillonnage de bosons avec suffisamment de pertes et de bruit peut être simulé efficacement, ce qui explique que les expériences visent un grand nombre de photons et de faibles pertes. La variante gaussienne employée par les expériences ultérieures est traitée dans la deuxième partie.

L’argument de complexité

Pourquoi ces tâches devraient-elles être difficiles pour les machines classiques ? Wikipédia résume l’argument principal. Si un algorithme classique pouvait échantillonner efficacement la sortie de circuits quantiques arbitraires, la hiérarchie polynomiale, une tour de classes de complexité, s’effondrerait à son troisième niveau. La plupart des théoriciens de la complexité jugent cet effondrement improbable, de sorte qu’un échantillonnage classique efficace est lui aussi tenu pour improbable.

C’est un indice, pas une preuve. L’argument couvre un échantillonnage exact ou quasi exact, alors que les dispositifs réels sont bruités et produisent des échantillons approchés. Pour l’échantillonnage de circuits aléatoires, Bouland, Fefferman, Nirkhe et Vazirani ont apporté en 2018 des indices supplémentaires de difficulté. Wikipédia note aussi que la factorisation par l’algorithme de Shor pose le problème inverse : la réponse est facile à vérifier classiquement, mais son exécution pour de grands nombres dépasse les machines actuelles.

Le problème de la vérification

Une expérience d’échantillonnage renvoie une longue liste de chaînes de bits d’apparence aléatoire. La vérifier est en soi coûteux. Dans l’expérience de Google, l’équipe ne pouvait pas simuler le circuit complet en un temps raisonnable ; elle s’est donc appuyée sur un étalon qui compare les échantillons mesurés à la distribution idéale. Wikipédia décrit l’échantillonnage de circuits aléatoires comme employé en tant qu’étalon de performance d’un dispositif quantique à l’échelle du système.

Cela crée une asymétrie inconfortable. Plus la tâche est difficile, plus il est difficile de confirmer que le dispositif l’a correctement accomplie. La deuxième partie décrit comment cet étalon a ensuite été utilisé par des simulateurs classiques comme cible à battre.

L’expérience de 2019 comme premier cas

En 2019, une équipe de Google a publié dans Nature une expérience menée sur un processeur supraconducteur de 53 qubits, Sycamore. Le titre de l’article emploie le mot suprématie. Il rapporte que l’espace des états du processeur est d’environ 2 puissance 53, soit à peu près 10 puissance 16, qu’un million d’échantillons ont pris environ 200 secondes, et que l’équipe estimait que la même tâche prendrait environ 10 000 ans sur le meilleur supercalculateur classique.

IBM a contesté cette estimation. Sa contre-affirmation, dans le résumé de Wikipédia, était que le circuit pouvait être simulé sur le supercalculateur Summit en environ 2,5 jours grâce à un stockage sur disque. Que 2,5 jours soit « raisonnable » fait partie du désaccord. Si c’est le cas, l’affirmation échoue au sens strict de la définition. Sinon, elle tient, mais avec une marge bien plus faible que 10 000 ans. La suite de l’histoire, dont une simulation classique de 2022, est traitée dans la deuxième partie.

Pourquoi une affirmation peut être provisoire

Wikipédia indique que la suprématie quantique peut être temporaire, car les algorithmes classiques s’améliorent. Une affirmation compare un dispositif quantique à la meilleure méthode classique connue le jour même. Quand une meilleure méthode classique apparaît, la marge se réduit, et dans certains cas elle disparaît. Wikipédia donne un exemple récent : une affirmation de 2024 de D-Wave sur la suprématie pour la dynamique de systèmes de spins a été remise en question par des études ultérieures sur les réseaux de tenseurs.

Une affirmation doit donc se lire à l’aide de cinq questions :

  • Quelle était exactement la tâche, et le résultat a-t-il été vérifié ?
  • Comment le coût classique a-t-il été estimé, et par qui ?
  • Une simulation classique a-t-elle depuis réduit ce coût ?
  • La tâche a-t-elle une utilité au-delà de l’étalon ?
  • Le matériel est-il assez bruité pour que le résultat soit presque classique de toute façon ?

La différence avec l’utilité

Rien de tout cela ne dit qu’un ordinateur quantique résout plus vite un problème pratique. Une démonstration d’avantage sur de l’échantillonnage montre que la machine fait quelque chose de difficile à imiter, ce qui est une condition préalable à une informatique quantique utile, et non sa réalisation. Les technologies quantiques comprennent aussi des capteurs qui fonctionnent déjà sur le terrain, traités dans la cartographie quantique. La physique statistique du bruit et de l’information est le sujet de l’entropie et de la flèche du temps.

À propos de l’image

L’image montre un IBM Quantum System One au ThinkLab du centre de recherche Thomas J. Watson d’IBM à Yorktown Heights, dans l’État de New York. L’équipe d’IBM est celle qui a contesté l’estimation du temps classique de 2019 pour Sycamore, comme décrit plus haut, et la photographie illustre le type de machine supraconductrice concerné par ces débats.

Questions fréquentes

Qu'est-ce que l'avantage quantique ?

C'est la démonstration qu'un ordinateur quantique peut effectuer une tâche qu'aucun ordinateur classique ne peut effectuer en un temps raisonnable. La tâche n'a pas besoin d'être utile. L'ancien nom du même jalon est la suprématie quantique.

Qui a inventé le terme suprématie quantique ?

John Preskill, lors d'un exposé de rapporteur à la 25e conférence Solvay en 2011, publié sur arXiv en 2012 sous le titre Quantum computing and the entanglement frontier. Il l'a employé pour désigner le moment où un ordinateur quantique résout un problème avec une accélération super-polynomiale par rapport aux ordinateurs classiques.

L'avantage quantique signifie-t-il que les ordinateurs quantiques sont utiles dès maintenant ?

Non. Les tâches utilisées jusqu'ici, comme l'échantillonnage de circuits aléatoires, ont été choisies parce qu'elles sont difficiles pour les machines classiques et adaptées à un dispositif à court terme, et non parce que leur résultat résout un problème pratique.

Pourquoi l'avantage quantique est-il difficile à prouver ?

Les tâches d'échantillonnage sont difficiles à vérifier, car la réponse est une liste de résultats d'apparence aléatoire. De plus, une affirmation sur ce que les ordinateurs classiques ne peuvent pas faire reste ouverte à un meilleur algorithme classique : un résultat peut donc être affaibli après publication.

Sources et données ouvertes

  1. Quantum computing and the entanglement frontier, arXiv
  2. Quantum supremacy using a programmable superconducting processor, Nature
  3. Quantum supremacy, English Wikipedia
  4. Boson sampling, English Wikipedia
  5. Sycamore processor, English Wikipedia