A brief history of quantum vs classical computational advantage

Cet article de revue résume de manière exhaustive toutes les expériences revendiquant une suprématie quantique, examine de manière critique leurs défis et réfutations, discute des avantages théoriques dans des problèmes spécifiques et met en lumière les progrès récents en matière de correction d'erreurs quantiques en tant qu'étape clé vers la réalisation d'un avantage dans l'algorithme de Shor.

L'essentiel

La Grande Image : La Grande Course

Imaginez une course entre deux coureurs : les Ordinateurs Classiques (les coureurs de marathon ultra-rapides et fiables que nous utilisons aujourd'hui) et les Ordinateurs Quantiques (les sprinteurs mystérieux et fulgurants qui fonctionnent selon les règles étranges de la physique quantique).

L'objectif de ce document est de tenir un tableau d'accumulation des points à chaque fois que le Sprinteur Quantique déclare : « Je peux résoudre cette énigme spécifique plus vite que le Coureur Classique ! » L'auteur, Ryan LaRose, agit comme un historien du sport, révisant chaque course, chaque protestation et chaque disqualification pour nous dire exactement où en est la course aujourd'hui.

Le document définit « l'avantage » simplement : Qui termine la tâche en premier ? Peu importe si la tâche est utile (comme guérir une maladie) ou juste une énigme futile ; la seule question est la vitesse.

---

Partie 1 : Les Courses « Énigmes Futiles » (Avantage Expérimental)

Jusqu'à présent, les Sprinteurs Quantiques ont tenté de gagner trois types spécifiques de courses « futiles ». Elles ne servent pas encore à construire des ponts ou à rédiger des courriels ; elles sont conçues spécifiquement pour être difficiles pour les ordinateurs classiques mais faciles pour les ordinateurs quantiques.

1. La Course d'Échantillonnage de Circuits Aléatoires (Le « Chaos du Lancer de Pièce »)

• La Tâche : Imaginez une machine qui lance 53 pièces de monnaie simultanément de manière totalement aléatoire et chaotique. L'ordinateur quantique le fait et enregistre le motif des faces et des piles. L'ordinateur classique doit deviner quel serait ce motif.
• La Première Victoire (Google, 2019) : L'ordinateur « Sycamore » de Google a réalisé cela en 200 secondes. Ils ont affirmé qu'un supercalculateur classique mettrait 10 000 ans pour faire les mêmes calculs.
• La Contre-Attaque : Les coureurs classiques n'ont pas abandonné. Ils ont inventé de nouvelles façons plus intelligentes de résoudre l'énigme.
  • Analogie : Imaginez que le coureur classique réalise qu'il n'avait pas besoin de parcourir toute la piste ; il pouvait prendre un raccourci à travers un tunnel qu'il avait trouvé.
  • Le Résultat : Avec le temps, les ordinateurs classiques sont devenus plus rapides. En 2024, un supercalculateur classique a réussi à accomplir la même tâche en 86 secondes, battant l'ordinateur quantique.
• Le Verdict : La première victoire de Google a été « réfutée ». Le coureur classique a rattrapé et dépassé le sprinteur. Cependant, Google a réessayé avec des énigmes plus grandes et plus difficiles (plus de pièces, plus de lancers), et ces courses plus récentes sont toujours non réfutées.

2. La Course d'Échantillonnage de Bosons Gaussiens (Le « Flipper de Photons »)

• La Tâche : Au lieu de pièces, cette course utilise des particules de lumière (photons) rebondissant dans un labyrinthe de miroirs. L'ordinateur quantique les envoie, et ils atterrissent à des endroits spécifiques. L'ordinateur classique doit calculer où ils sont tombés.
• Les Concurrents : Des équipes de Chine (USTC) et du Canada (Xanadu) ont construit ces coureurs à base de lumière.
• La Contre-Attaque : Tout comme la course aux pièces, les ordinateurs classiques ont trouvé des « échappatoires ». Ils ont réalisé que si les particules de lumière n'étaient pas parfaites (ce qui n'est jamais le cas), les mathématiques devenaient plus faciles. Ils ont construit de nouveaux algorithmes pour simuler le labyrinthe de lumière beaucoup plus vite que prévu.
• Le Verdict : La plupart de ces affirmations ont été « faiblement réfutées ». Cela signifie que les ordinateurs classiques n'ont pas encore battu les ordinateurs quantiques sur les plus grandes énigmes, mais ils sont assez proches pour qu'un ordinateur classique légèrement meilleur dans un avenir proche puisse probablement le faire.

3. La Course de Simulation Quantique (La « Prévision Météorologique »)

• La Tâche : Simuler comment un système complexe (comme un matériau magnétique) évolue au fil du temps.
• Les Concurrents : IBM et D-Wave.
• La Contre-Attaque : IBM a affirmé avoir simulé un système magnétique plus vite qu'un ordinateur classique. Mais en l'espace de deux semaines, des chercheurs classiques ont montré qu'ils pouvaient le simuler sur un ordinateur portable en quelques minutes.
• Le Verdict : L'affirmation d'IBM a été rapidement « réfutée ». Le coureur classique a trouvé un itinéraire beaucoup plus rapide. La tentative récente de D-Wave est toujours surveillée, mais elle risque de faire face à des défis similaires.

---

Partie 2 : Les Courses « Théoriques » (Les Preuves Mathématiques)

Parfois, les mathématiciens disent : « Si nous construisons un ordinateur quantique parfait, il devrait gagner cette course. » Mais l'histoire montre que les mathématiciens classiques sont très doués pour trouver de nouveaux tours.

• La Course du Système de Recommandation : Un algorithme quantique a été proposé pour recommander des films plus vite que n'importe quel ordinateur classique.
  • La Surprise : Un mathématicien classique (Ewin Tang) a réalisé : « Hé, si nous donnons à l'ordinateur classique la même structure de données spéciale que celle utilisée par l'ordinateur quantique, il peut résoudre le problème tout aussi vite ! »
  • Le Résultat : L'avantage quantique a disparu. Cela s'appelle la « déquantification ».
• La Course d'Optimisation : Des histoires similaires se sont produites avec des algorithmes conçus pour résoudre des problèmes complexes de planification. L'avantage quantique a été revendiqué, puis un algorithme classique a été trouvé qui était tout aussi bon.

---

Partie 3 : La Dernière Frontière (Correction d'Erreurs)

Voici la conclusion la plus importante du document : Les ordinateurs quantiques sont fragiles.

• L'Analogie : Imaginez que le Sprinteur Quantique est un coureur en verre. Il est incroyablement rapide, mais s'il trébuche sur un petit caillou (bruit), il se brise. Pour courir un marathon (comme factoriser de grands nombres pour casser un cryptage), ils doivent porter une armure.
• L'Armure : Cette armure s'appelle la Correction d'Erreurs Quantiques. Elle utilise de nombreux « qubits » physiques en « verre » pour créer un seul « qubit logique » robuste.
• La Situation Actuelle : Nous commençons tout juste à construire cette armure.
  • En 2024, Google a annoncé une nouvelle puce (Willow) où le « qubit logique » (celui blindé) a duré plus longtemps que les « qubits physiques » individuels (ceux en verre).
  • C'est le moment du « Saint Graal ». Cela prouve que l'ajout de pièces pour corriger les erreurs rend en fait le système meilleur, et non pire.
• L'Avenir : Tant que nous n'aurons pas cette armure, nous ne pouvons pas courir les courses « utiles » (comme casser des codes ou simuler de nouveaux médicaments). Le document soutient que la Correction d'Erreurs est la dernière frontière avant que les ordinateurs quantiques ne puissent vraiment battre les ordinateurs classiques sur des problèmes du monde réel.

Résumé : Où en sommes-nous ?

Le document conclut que la course est une corde à sauter.

1. Les ordinateurs quantiques font un grand bond en avant.
2. Les ordinateurs classiques deviennent plus intelligents, trouvent des raccourcis et rattrapent (ou dépassent) le retard.
3. Les ordinateurs quantiques construisent un meilleur matériel et réessayent.

Pour l'instant, nous sommes à la frontière. Nous avons vu les ordinateurs quantiques gagner sur des énigmes spécifiques et inutiles, mais les ordinateurs classiques ont trouvé des moyens de les battre sur presque toutes d'entre elles. Le document suggère que pour que les ordinateurs quantiques gagnent une course utile, ils doivent d'abord maîtriser l'art de la Correction d'Erreurs. Jusque-là, l'avance continuera de changer de mains.

Résumé technique

Titre : Une brève histoire de l'avantage computationnel quantique par rapport à l'avantage classique
Auteurs : Ryan LaRose
Source : Quantum (Accepté le 14 mai 2026)

Énoncé du problème

L'article traite du paysage évolutif de « l'avantage computationnel quantique » (également appelé suprématie quantique ou computation au-delà du classique). Le problème central réside dans la définition et le suivi de la frontière mouvante entre ce qui est computationnellement réalisable pour les ordinateurs classiques par rapport aux ordinateurs quantiques. Les auteurs définissent l'avantage computationnel spécifiquement comme une réduction du temps de résolution pour un problème donné, indépendamment de l'utilité pratique du problème. La revue vise à recenser toutes les affirmations expérimentales d'avantage quantique à ce jour, ainsi que les défis classiques subséquents, les réfutations et les développements théoriques qui ont modifié le statut de ces affirmations.

Méthodologie

L'article emploie une méthodologie de revue exhaustive, synthétisant des données historiques issues de la physique expérimentale, de l'informatique et de la théorie de la complexité.

1. Catalogage chronologique : Les auteurs établissent une chronologie de toutes les expériences revendiquant un avantage quantique, les catégorisant par type de problème : Échantillonnage de circuits aléatoires (RCS), Échantillonnage de bosons gaussiens (GBS) et Simulation quantique (QSim).
2. Classification du statut : Chaque expérience se voit attribuer un statut basé sur la littérature subséquente :
   • Non réfuté : Aucun algorithme classique n'a encore simulé l'expérience plus rapidement.
   • Mis en défi : Des algorithmes classiques ont amélioré les temps de simulation ou remis en question des aspects spécifiques de l'expérience.
   • Faiblement réfuté : Un algorithme classique existe qui pourrait probablement simuler l'expérience sur du matériel classique proche du futur.
   • Réfuté : Un ordinateur classique a simulé avec succès l'expérience plus rapidement que le dispositif quantique.
3. Analyse théorique : La revue examine l'avantage théorique dans des domaines spécifiques (optimisation approximative, systèmes de recommandation, chimie quantique) pour mettre en évidence comment la « déquantification » (le développement d'algorithmes classiques inspirés par les algorithmes quantiques) peut éroder les accélérations théoriques.
4. Revue de la correction d'erreurs : L'article retrace l'histoire des expériences de correction d'erreurs quantiques (QEC), les identifiant comme la « dernière frontière » nécessaire pour atteindre un avantage dans des algorithmes comme celui de Shor, qui nécessitent une tolérance aux pannes.

Contributions clés

• Tableau exhaustif des statuts : L'article fournit le Tableau 1, une liste chronologique de toutes les affirmations d'avantage quantique (de Sycamore de Google en 2019 à la simulation de D-Wave en 2024) et leur statut actuel concernant la réfutation classique.
• Narration détaillée des défis : Il documente la « course aux armements » entre les expériences quantiques et la simulation classique. Les contributions notables incluent le suivi des optimisations de contraction de réseaux de tenseurs (par exemple, les algorithmes « big head », la partition d'hypergraphes) et des stratégies d'exploitation du bruit qui ont réduit les temps d'exécution classiques estimés de milliers d'années à quelques heures ou secondes pour des expériences spécifiques.
• Clarification des métriques : La revue analyse de manière critique la fidélité du benchmark de l'entropie croisée (XEB), discutant des failles où des algorithmes classiques peuvent « falsifier » de fortes valeurs XEB sans simuler le circuit complet, et distinguant entre les réfutations faibles et fortes.
• Déquantification théorique : L'article détaille comment les avantages théoriques dans l'optimisation Max-E3LIN2 et les systèmes de recommandation ont été perdus lorsque des algorithmes classiques (par exemple, ceux de Barak et al. et d'Ewin Tang) ont égalé ou dépassé les performances quantiques sous des hypothèses d'entrée similaires.
• Progrès de la QEC : Le Tableau 2 et la section 4 résument la progression rapide des expériences de correction d'erreurs, notant la transition des codes de répétition simples vers des codes de surface avec des distances allant jusqu'à 7, et la récente étape franchie par l'expérience de Google en 2024 où les taux d'erreurs logiques sont tombés en dessous du seuil des taux d'erreurs physiques.

Résultats

• Volatilité expérimentale : La revue constate que presque toutes les grandes affirmations expérimentales d'avantage quantique ont fait face à des défis significatifs.
  • RCS de Google (2019, 53 qubits) : Initialement revendiquant un temps d'exécution classique de 10 000 ans. Cela a été contesté par des optimisations de réseaux de tenseurs et finalement fortement réfuté en 2024 (Zhao et al.) utilisant 1 432 GPU pour simuler l'expérience en 86,4 secondes.
  • GBS de l'USTC (Jiuzhang 1.0, 2.0, 3.0) : Les affirmations d'avantage ont été faiblement réfutées par Oh et al. (2023), qui ont utilisé des réseaux de tenseurs pour simuler ces expériences bien plus rapidement que les dispositifs quantiques, bien que les expériences restent non réfutées au sens « fort » pour les plus grandes instances.
  • QSim d'IBM (2023) : Une affirmation d'avantage dans la simulation du modèle d'Ising en champ transversal a été réfutée en quelques semaines par plusieurs approches classiques (réseaux de tenseurs, propagation de croyance, théorie des perturbations de Clifford) s'exécutant sur des ordinateurs portables ou des GPU uniques.
  • D-Wave (2024) : Une récente affirmation d'avantage dans la simulation quantique reste non réfutée au moment de la rédaction, bien que les auteurs notent qu'elle est probablement une cible pour de futurs défis classiques.
• Changements théoriques : L'article démontre que l'avantage théorique n'est pas statique. Les algorithmes pour les systèmes de recommandation et l'optimisation approximative (QAOA) ont vu leurs avantages quantiques érodés par des algorithmes classiques « déquantifiés » qui utilisent des structures de données ou des techniques d'approximation similaires.
• Étapes clés de la correction d'erreurs : Bien que l'informatique quantique tolérante aux pannes ne soit pas encore réalisée, la revue souligne que les qubits logiques atteignent désormais des durées de vie plus longues que leurs composants physiques et que les taux d'erreurs s'approchent du seuil requis pour une tolérance aux pannes évolutive.

Signification et affirmations

L'article affirme que l'histoire de l'avantage quantique est une cible dynamique et mouvante plutôt qu'une réalisation statique.

• Cible mouvante : Les auteurs soulignent que l'avantage computationnel est défini par rapport aux algorithmes et au matériel classiques les mieux connus à un moment donné. À mesure que les algorithmes classiques s'améliorent (souvent inspirés par des insights quantiques), la frontière de l'avantage se déplace à nouveau vers les ordinateurs classiques.
• Crise de la vérification : Une partie importante de l'article met en évidence la difficulté de vérifier l'avantage quantique. De nombreuses expériences actuelles (comme le RCS) sont difficiles à vérifier classiquement, créant un paradoxe où l'affirmation d'avantage repose sur des calculs classiques qui sont eux-mêmes intraitables. L'article pointe vers l'« échantillonnage de circuits à pic » et l'« échantillonnage de codes cachés » comme des orientations futures proposées pour un avantage vérifiable de manière efficace.
• Rôle de la correction d'erreurs : La revue postule que pour les algorithmes avec des accélérations exponentielles prouvées (comme l'algorithme de Shor), la « dernière frontière » n'est pas seulement le nombre de qubits, mais la correction d'erreurs quantiques. Sans tolérance aux pannes, la surcharge de la correction d'erreurs peut annuler toute accélération théorique.
• Perspective modeste : Les auteurs concluent que si l'avantage quantique est probable pour des problèmes spécifiques, le domaine se trouve actuellement à la « frontière » entre la domination quantique et classique. Ils mettent en garde contre l'hypothèse d'un avantage permanent, notant que le statut continuera probablement à évoluer à mesure que les technologies classiques et quantiques évolueront. L'article sert de registre historique pour propulser les chercheurs vers de nouvelles formulations de problèmes qui sont classiquement difficiles, quantiquement faciles, efficacement vérifiables et scientifiquement utiles.