OpenAI affirme avoir brisé une hypothèse clé de l'informatique : des experts vérifient

Le 16 octobre, un modèle interne d'OpenAI a produit une preuve qui, si elle tient, fait tomber un pilier de l'informatique théorique. Dix jours plus tard, l'entreprise l'a rendue publique. Pour la vérifier, elle a fait appel aux deux chercheurs qui avaient formulé cette hypothèse il y a plus d'un quart de siècle.

Ce pilier s'appelle l'hypothèse du temps exponentiel, ou ETH (pour Exponential Time Hypothesis). Elle fixe une limite à la vitesse à laquelle un ordinateur classique peut résoudre certains casse-tête logiques.

Sa chute intéresserait bien au-delà des mathématiciens : les promesses de l'informatique quantique reposent en partie sur ce que les ordinateurs classiques sont censés ne pas savoir faire.

Cet article porte sur cette annonce en informatique et sur ce qu'elle change pour l'avantage quantique. Le même jour, OpenAI a publié deux autres résultats, l'un en mathématiques, l'autre en physique, que nous évoquons plus brièvement. Un point domine tout le reste : pour l'instant, rien n'a été validé par des spécialistes indépendants.

Dans cet article :

• OpenAI dit avoir fissuré le « mur » qui ralentit les ordinateurs
• Les pères de l'hypothèse vont juger la preuve qui la contredit
• Pourquoi le monde de la recherche quantique retient son souffle
• Ce qu'il faut surveiller dans les prochains mois

OpenAI dit avoir fissuré le « mur » qui ralentit les ordinateurs

Pour comprendre l'enjeu, imaginez un casse-tête de planning : au moins une personne parmi plusieurs doit assister à une réunion, certaines combinaisons sont interdites, d'autres obligatoires. Vérifier un planning proposé est facile. En trouver un valable devient beaucoup plus dur à mesure que les contraintes s'accumulent.

Les informaticiens appellent ce genre de problème 3-SAT (pour satisfiabilité : trouver une combinaison de valeurs vrai/faux qui respecte une liste de conditions logiques). Avec n variables, il existe 2 puissance n combinaisons possibles. L'ETH affirme qu'aucun programme, aussi malin soit-il, ne peut éviter une explosion exponentielle du temps de calcul quand n grandit.

Cette hypothèse n'a jamais été démontrée, mais elle était largement considérée comme véridique. Selon OpenAI, des centaines d'articles s'en sont servis pour établir que d'autres problèmes ne peuvent pas être résolus rapidement.

Son modèle aurait trouvé la réfutation le 16 octobre, puis l'aurait vérifiée dans Lean le lendemain (Lean est un logiciel qui contrôle chaque étape d'une démonstration) [1].

Le manuscrit, publié sur GitHub, décrit un algorithme qui compte exactement toutes les solutions d'un tel casse-tête en temps « sous-exponentiel » : la durée grimpe toujours très vite, mais moins rapidement que n'importe quelle exponentielle.

Le gain reste modeste, car l'exposant ne baisse que d'un facteur lié à la racine carrée du logarithme du nombre de variables [2]. N'espérez toutefois pas un super-solveur pour demain. Un calcul en 2 puissance racine de n, pourtant sous-exponentiel, demanderait environ mille milliards d'étapes pour un problème de 1 600 variables [3].

La réfutation ne règle pas non plus la question « P contre NP » (savoir si tout problème facile à vérifier est aussi facile à résoudre).

Les pères de l'hypothèse vont juger la preuve qui la contredit

OpenAI n'a pas choisi ses examinateurs au hasard. Le groupe chargé de vérifier et d'expliquer la preuve est mené par Russell Impagliazzo et Ramamohan Paturi, de l'université de Californie à San Diego, coauteurs de l'hypothèse avec Francis Zane et Ryan Williams, du MIT.

Dans une lettre ouverte à leurs collègues, les trois chercheurs préviennent : « Our involvement should not be taken as certification of the claim » (notre participation ne vaut pas certification). Selon Williams, ils n'ont signé aucun accord de confidentialité et ne sont pas payés. OpenAI a accepté de publier ses données brutes et de financer une conférence [4].

Reste la question de Lean. Le logiciel vérifie que chaque étape découle logiquement de la précédente, ce qui offre plus de garanties qu'une explication d'IA qui a simplement l'air convaincante. Mais il ne contrôle que l'énoncé qu'on lui fournit : à lui seul, il ne garantit pas que cet énoncé formel correspond à l'hypothèse telle que les experts la comprennent [5].

Le risque est bien réel. En tentant de formaliser une autre réfutation produite par OpenAI, des chercheurs ont vu leur outil automatique remplacer une théorie mathématique manquante par des valeurs factices. Le code passait les vérifications, sans rien prouver de réel [6].

La prudence s'impose d'autant plus qu'OpenAI a déjà dû faire marche arrière sur des annonces trop rapides, comme nous le racontions dans notre article sur les mathématiciens qui contre-attaquent. En septembre, l'entreprise a aussi renoncé à réclamer le prix de l'Institut Clay pour sa preuve sur les équations de Navier-Stokes.

Autre rebondissement : juste après l'annonce, Anthropic, concurrent direct d'OpenAI, a mis en ligne sa propre prépublication (un article diffusé avant relecture par des pairs).

Son modèle Claude aurait trouvé, lui aussi, le 16 octobre, un algorithme sous-exponentiel pour 3-SAT, avec 14 millions de jetons de sortie (les unités de texte produites par l'IA) et sans intervention humaine [7].

Deux trouvailles indépendantes ne remplacent pas une vérification humaine, mais elles rendent moins probable une simple erreur d'un seul modèle. Pour mesurer le saut, le texte d'Anthropic situe le meilleur algorithme déterministe connu jusqu'ici à environ 1,328 puissance n étapes : une exponentielle pure, que les deux IA disent avoir battue [8].

Pourquoi le monde de la recherche quantique retient son souffle

On parle d'avantage quantique quand une machine quantique accomplit une tâche qu'aucun ordinateur classique ne peut réaliser en un temps raisonnable. Pour l'affirmer, il faut prouver un négatif : montrer ce que les ordinateurs ordinaires ne savent pas faire. C'est là que des hypothèses comme l'ETH entrent en jeu.

En 2018, Cupjin Huang, Michael Newman et Mario Szegedy ont étudié la simulation de circuits quantiques sur ordinateur classique. Pour la plupart des techniques connues, ils ont prouvé une limite qui ne dépend d'aucune hypothèse.

Puis, en supposant vraie la SETH (une version renforcée de l'ETH), ils en ont tiré une limite plus générale : tout simulateur universel prendrait un temps quasi exponentiel [9].

Or, l'ETH n'est qu'une version affaiblie de la SETH [10]. Si la première tombe, la seconde tombe avec elle. Les conclusions bâties sur la SETH devront trouver une autre base, tandis que les résultats démontrés sans hypothèse tiennent toujours.

Ces paris servent aussi à chiffrer l'avantage quantique. Dans leur synthèse sur la suprématie quantique, Aram Harrow (MIT) et Ashley Montanaro évoquaient une variante de l'ETH selon laquelle environ 1 700 qubits (les bits quantiques) suffiraient pour un calcul qu'un superordinateur à 10 puissance 17 opérations par seconde ne pourrait pas simuler en moins d'une journée [11].

En 2020, dans la revue Quantum, une étude d'Alexander Dalzell, d'Aram Harrow et de deux collègues a repris ce calcul à partir de conjectures de la même famille que la SETH.

Selon elle, 208 qubits suffiraient pour que des circuits IQP (des circuits quantiques simplifiés) deviennent impossibles à simuler avec les machines actuelles. Il en faudrait 420 pour des circuits QAOA (un algorithme d'optimisation) [12].

Attention : ces conjectures portent sur d'autres problèmes que 3-SAT, et la preuve d'OpenAI ne les réfute pas directement. Mais elles font le même genre de pari sur la lenteur des ordinateurs classiques.

Comme le résume The Quantum Insider, le travail consiste désormais à séparer les comparaisons qui reposent sur des hypothèses contestées de celles qui reposent sur des mesures.

L'histoire récente invite à l'humilité. En 2019, Google affirmait que sa puce Sycamore avait accompli en 200 secondes une tâche qui aurait pris 10 000 ans au superordinateur Summit. IBM a répondu en quelques semaines qu'une meilleure méthode classique y parviendrait en environ deux jours et demi [13].

La preuve d'OpenAI pose le même problème, mais à l'envers. Perdre l'argument qui garantissait qu'un calcul est difficile ne donne pas pour autant un moyen rapide de le faire.

L'avantage quantique tient toujours : tout dépend de qui construit, en pratique, le meilleur algorithme classique. Côté matériel, la course continue, comme le montre le grand défi quantique de la DARPA.

Ce qu'il faut surveiller dans les prochains mois

Rien ne se décidera en quelques jours. Trois questions diront si le 16 octobre restera une date historique ou un communiqué de plus.

Le verdict des trois examinateurs

Le premier signal viendra du groupe Impagliazzo, Paturi et Williams. La preuve et sa version Lean sont publiques : de ces dossiers, c'est donc le plus rapide à examiner. Une erreur dans la traduction formelle de l'hypothèse suffirait à tout remettre en cause. Une validation ajouterait l'ETH à la liste des conjectures renversées par une IA.

Les trois chercheurs soulèvent aussi la question du crédit. Ils craignent que la reconnaissance aille à ceux qui publient vite ou qui ont les outils les plus puissants, plutôt qu'à ceux qui vérifient et expliquent. OpenAI dit ne réclamer aucun crédit académique et a versé 5 millions de dollars à la Fondation Simons pour financer des ateliers sur ces résultats.

La facture pour l'avantage quantique

Pour les acteurs du quantique, la question pratique devient la suivante : quelles démonstrations reposent sur des mesures et lesquelles sur des paris théoriques ? Une revue récente des expériences d'IBM, D-Wave et Google le rappelle : toute revendication d'avantage quantique dépend des meilleurs algorithmes classiques du moment, qui ne cessent de progresser [14].

Les annonces les plus solides comparent donc des temps mesurés. En 2025, Google a affirmé que son algorithme Quantum Echoes, sur sa puce Willow, allait environ 13 000 fois plus vite que le superordinateur Frontier. Ce chiffre ne vaut toutefois que pour ce test précis et pour l'algorithme classique choisi comme point de comparaison [15].

Le bon réflexe, face à la prochaine annonce : chercher à quoi la machine quantique est comparée et vérifier si la performance classique annoncée repose sur une hypothèse ou sur un programme réellement exécuté. Une hypothèse peut tomber du jour au lendemain, un chronomètre beaucoup plus difficilement.

La preuve à l'ère des machines

Le volet physique suit une autre méthode. Pour sa preuve d'existence mathématique de la chromodynamique quantique (la théorie des quarks et des gluons, qui composent les protons), OpenAI a confié l'examen au prix Nobel David Gross. Son groupe a choisi de garder les documents de l'IA sous clé et de rédiger lui-même son compte rendu.

Cette preuve inclut la théorie de Yang-Mills, liée à l'un des problèmes du Millénaire de l'Institut Clay. Mais pour résoudre ce problème, il faut aussi établir un « gap de masse » (montrer que la particule la plus légère de la théorie a une masse strictement positive), ce que l'annonce ne fait pas : parler de prix décroché serait faux [3].

OpenAI avait déjà réuni des sommités pour valider ses travaux, comme avec son conseil de mathématiciens. Cette fois, chaque résultat est confié à un groupe extérieur. Un schéma se met en place : l'IA trouve, les humains certifient et la science avance désormais au rythme des vérificateurs.

Pour le lecteur, la bonne attitude consiste à prendre au sérieux une preuve vérifiée par une machine sans la tenir pour acquise. Si les trois examinateurs confirment, une barrière vieille d'un quart de siècle aura cédé. Pour revendiquer l'avantage quantique, il faudra alors s'appuyer sur des chronomètres plutôt que sur des conjectures.

Sources principales :

1. FourWeekMBA – OpenAI Says Its AI Refuted the Exponential Time Hypothesis
   Selon OpenAI, l'ETH a servi dans des centaines d'articles. La réfutation a été trouvée le 16 octobre 2026 et formalisée dans Lean le lendemain. (fourweekmba.com)
2. Pasquale Pillitteri – OpenAI announces proof that the Exponential Time Hypothesis is false
   Un gain modeste : l'exposant ne baisse que d'un facteur lié à la racine carrée du logarithme de n. Texte et preuve Lean publiés dans le dépôt GitHub openai/math. (pasqualepillitteri.it)
3. The Quantum Insider – OpenAI Computing Claim Faces Review, Raising Questions About Quantum Advantage
   Un calcul en 2 puissance racine de n représente environ mille milliards d'étapes pour 1 600 variables. Une preuve d'existence de Yang-Mills ne règle pas le problème du Millénaire complet. (thequantuminsider.com)
4. The Next Web – OpenAI says its AI model has disproved the Exponential Time Hypothesis
   Lettre ouverte d'Impagliazzo, Paturi et Williams, pas d'accord de confidentialité ni de rémunération, 5 millions de dollars versés à la Fondation Simons. (thenextweb.com)
5. Tech Insider – OpenAI's 3 Science Claims: ETH, Kakeya, QCD
   Une vérification Lean ne prouve pas, à elle seule, que l'énoncé formel correspond à l'énoncé tel que le lit un expert. (tech-insider.org)
6. arXiv – LeanMarathon: Toward Reliable AI Co-Mathematicians through Long-Horizon Lean Autoformalization
   Un cas d'échec : une formalisation passe les vérifications automatiques tout en ne prouvant rien de réel. (arxiv.org)
7. Hexagon (Anthropic) – A 2^o(n) Time Algorithm for 3-SAT
   Prépublication attribuée à Claude : algorithme trouvé le 16 octobre avec 14 millions de jetons de sortie, sans intervention humaine. (hexagonmath.org)
8. FourWeekMBA – Anthropic Says Claude Also Refuted ETH, Using 14M Tokens
   Le précédent record d'algorithme déterministe pour 3-SAT était d'environ 1,328 puissance n étapes. (fourweekmba.com)
9. arXiv (Huang, Newman, Szegedy) – Explicit lower bounds on strong quantum simulation
   Une borne sans hypothèse pour la plupart des simulateurs, et une limite plus générale si l'on suppose la SETH vraie. (arxiv.org)
10. arXiv – On the Fine-Grained Hardness of Inverting Generative Models
    Rappelle que l'ETH est une conjecture légèrement plus faible que la SETH. (arxiv.org)
11. Aram W. Harrow et Ashley Montanaro – Quantum Computational Supremacy
    Selon une variante de l'ETH, environ 1 700 qubits suffiraient pour dépasser une journée de calcul d'un superordinateur. (people.maths.bris.ac.uk)
12. Quantum (Dalzell, Harrow, Koh, La Placa) – How many qubits are needed for quantum computational supremacy?
    Estimations : 208 qubits pour les circuits IQP, 420 pour les circuits QAOA, 98 photons pour l'échantillonnage de bosons. (quantum-journal.org)
13. Quantum Zeitgeist – Quantum Supremacy: Complete 2026 Guide To The Milestone
    Sycamore : 200 secondes contre 10 000 ans estimés sur Summit, puis environ 2,5 jours selon IBM. (quantumzeitgeist.com)
14. arXiv – Revue des expériences d'avantage quantique d'IBM, D-Wave et Google face aux simulations par réseaux de tenseurs
    Les revendications d'avantage quantique dépendent de l'état des algorithmes classiques, qui évolue sans cesse. (arxiv.org)
15. iTechGuides – Google Quantum Echoes: What Willow's Verifiable Quantum Advantage Means
    L'avantage d'environ 13 000 fois ne vaut que pour ce test et pour l'algorithme classique utilisé comme comparaison. (itechguides.com)