Une IA de recherche affirme avoir démontré une conjecture de 2008

Physical Superintelligence a annoncé le 6 novembre 2026 qu’un système de recherche interne, exécuté sur sa propre infrastructure et reposant sur des instances d’un modèle Anthropic non public, avait trouvé une preuve de la conjecture d’Aaronson-Ambainis, un problème de calcul quantique ouvert depuis 2008. La preuve complète a émergé au troisième jour d’exécution, puis l’assistant de preuve Lean l’a acceptée. L’enjeu est lourd: cette conjecture touche à la question de savoir quand un ordinateur quantique peut vraiment dépasser un classique, et dans quels cas le gain reste limité.

Un résultat quantique qui regarde autant la théorie que la machine

La conjecture d’Aaronson-Ambainis porte sur les speedups quantiques, c’est-à-dire les gains de vitesse qu’un ordinateur quantique peut obtenir face à une machine classique. Dans le cas d’un problème structuré, comme la factorisation exploitée par l’algorithme de Shor en 1994, le calcul quantique peut tirer parti d’un motif répétitif. Ici, le terrain est différent: le résultat vise des entrées aléatoires ou non structurées, où ce type de raccourci disparaît souvent.

Dans le modèle de requêtes, un algorithme classique lit un bit à chaque requête, alors qu’une requête quantique peut être répartie en superposition sur plusieurs positions d’entrée. PSI relie ce cadre à des polynômes: après T requêtes quantiques, la probabilité de répondre “oui” devient un polynôme borné de degré au plus 2T. Simuler l’algorithme revient alors à estimer ce polynôme sans lire une quantité exponentielle de données. Le genre de détail qui fait aimer les maths à 2h du matin, ou les fuir pour de bon.

Ce que la conjecture promettait, et ce que la preuve prétend maintenant tenir

Dans leur travail original, Scott Aaronson et Andris Ambainis avaient formulé l’idée suivante: tout polynôme borné de faible degré possède une variable fortement influente. Ils montraient que, si cette conjecture est vraie, tout algorithme quantique à T requêtes peut être simulé, sur la plupart des entrées, par un algorithme classique utilisant un nombre de requêtes polynomial en T. La conséquence est claire: pour une erreur d’approximation donnée et une fraction fixée d’entrées exclues, la croissance reste polynomiale plutôt qu’exponentielle. Cela ne ferme pas la porte aux avantages quantiques, mais les cantonne aux problèmes où la structure compte vraiment.

Le dépôt de PSI formalise cet énoncé ainsi: pour un polynôme réel p de degré au plus d, dont les valeurs sur le cube discret restent entre 0 et 1, si sa variance sur une entrée uniforme est au moins ε, alors une coordonnée possède une influence d’au moins (8√15 / (125π⁴)) · ε^(5/2) / d⁶, et donc au moins (ε/d)⁷. L’influence désigne l’espérance du changement au carré de p quand on inverse le bit de cette coordonnée.

Une preuve construite par morceaux, puis vérifiée dans Lean

Selon le dépôt, l’argument suit un plan proposé par Shachar Lovett et Jiapeng Zhang, fondé sur des certificats fractionnaires et des ensembles de niveaux, mais remplace une inégalité laissée conjecturale par une nouvelle inégalité “all-pairs”. Une borne de type déterminant construit une mise en correspondance bijective des configurations d’entrée. PSI soutient que cette correspondance va plus loin que le lemme du papillon de David Reimer, car elle limite aussi la fréquence avec laquelle les paires concordent sur chaque coordonnée.

Le développement formel est découpé en quatre étapes: dériver l’inégalité all-pairs à partir du déterminant et de la bijection, l’intégrer sur les ensembles de niveaux, moyenner sur les coordonnées, puis établir une borne de lignes avec une borne de sensibilité ponctuelle. L’ensemble conduit à la borne explicite sur l’influence.

La vérification formelle revendiquée est robuste, mais pas magique. Le dépôt indique qu’il ne contient ni trou de preuve ni axiome ajouté. Ses déclarations ont été rejouées par le noyau de Lean et par lean4lean, une implémentation indépendante du vérificateur de types de Lean. Lors d’une exécution en bac à sable, un comparateur utilisant les noyaux nanoda et Lean a accepté les quatre théorèmes finaux; sur une seconde machine, il a accepté une petite solution correcte et rejeté quatre solutions volontairement fausses.

Des garanties formelles, mais pas un blanc-seing total

Ces vérifications ont leurs limites. Un lecteur doit encore confirmer que l’énoncé formel correspond bien à la conjecture imprimée. L’article en langage naturel n’est pas lui-même contrôlé par machine, tandis que le noyau de Lean, le compilateur, les définitions de Mathlib et les machines utilisées pour la vérification restent dans la base de confiance. Autrement dit, l’IA a bien aidé à faire tourner la mécanique, mais elle n’a pas supprimé le besoin de lecture humaine.

Physical Superintelligence précise aussi les rôles humains. David Turturean, membre de l’équipe technique, a développé et exécuté le système, cadré le problème, demandé au modèle de produire une première version, relu ce brouillon et porte la responsabilité de l’exactitude de l’article. Le dépôt indique que les modèles d’IA ont produit les énoncés mathématiques, la première ébauche et la formalisation Lean. Jim Halverson a audité la preuve, et Phiala Shanahan a commenté la formalisation.

L’annonce intervient après un papier soumis le 19 août 2026 par Guy Blanc, Jordan Docter, Carmen Strassle et Li-Yang Tan, qui avaient déjà réglé une conséquence liée à la simulation classique des algorithmes quantiques parallèles. PSI rapporte que les quatre auteurs ont lu l’intégralité de la preuve, ont envoyé des commentaires et préparent une version plus courte à destination des spécialistes. Le vrai test, désormais, sera moins spectaculaire que le communiqué: faire confirmer par des experts que l’énoncé formel colle bien à la conjecture d’Aaronson-Ambainis et que les parties hors Lean tiennent elles aussi la route.