Un système de recherche développé par la startup Physical Superintelligence, utilisant des instances d'un modèle anthropique non public, a produit une preuve complète de la conjecture d'Aaronson-Ambainis, un problème mathématique resté ouvert depuis 2008 et qui concerne le moment où les ordinateurs quantiques peuvent obtenir des avantages exponentiels par rapport aux machines classiques. La preuve a été acceptée par l'assistant de preuve Lean, selon un article publié publiquement par l'entreprise.

Le résultat, rapporté pour la première fois par The Quantum Insider et couvert par Business Insider, est décrit par des chercheurs indépendants comme un jalon pour les mathématiques assistées par l'IA – et l'un des résultats les plus conséquents jamais attribués à un modèle frontière qui n'a jamais été rendu public. Pour plus de contexte sur cette histoire, consultez notre couverture de l'industrie de l'IA.

Ce que dit la conjecture

Scott Aaronson et Andris Ambainis ont posé la question dans un travail remontant à une conférence d'Aaronson en 2008 : un algorithme quantique peut-il encore obtenir un avantage exponentiel lorsque l'entrée qu'il reçoit n'a aucune structure à exploiter ? Les accélérations quantiques les plus connues, comme l'algorithme de factorisation de Peter Shor de 1994, fonctionnent parce que leurs entrées comportent des motifs répétitifs que l'algorithme peut exploiter. La question Aaronson-Ambainis aborde le cas opposé : des entrées uniformément aléatoires et non structurées où de tels modèles sont absents.

Pour étudier la question, les chercheurs utilisent le modèle de requête, qui compte la fréquence à laquelle un algorithme accède à ses entrées plutôt que chaque opération qu'il effectue. Un algorithme classique lit un bit par requête, tandis qu'une requête quantique peut agir sur une superposition de plusieurs positions d'entrée à la fois. Aaronson et Ambainis ont émis l'hypothèse que chaque polynôme borné de bas degré – l'objet mathématique qui décrit la probabilité de sortie d'un algorithme quantique après un nombre donné de requêtes – devait avoir une variable très influente.

Si cela est vrai, la conjecture implique qu’un algorithme quantique effectuant T requêtes peut être simulé par un algorithme classique effectuant uniquement un nombre polynomial de requêtes sur la plupart des entrées, excluant ainsi les accélérations exponentielles pour les problèmes non structurés. La conjecture a été prouvée en supposant une déclaration formelle sur les polynômes, mais la déclaration elle-même a résisté à la preuve pendant 18 ans.

Comment la preuve a été trouvée

Selon le blog du PSI et l'article qui l'accompagne, le système de recherche a produit une preuve complète au cours du troisième jour d'exécution sur la propre infrastructure du PSI. Le théorème principal et sa formulation de la conjecture originale ont été formalisés dans Lean 4, et le noyau de Lean — le composant logiciel qui vérifie mécaniquement chaque étape logique — a accepté la preuve. Le PSI a ensuite assigné au système les problèmes ouverts liés, ce qui l'a amené à renforcer le résultat à deux reprises avant que la version finale ne soit acceptée.

L'audit enregistré du référentiel indique que le développement formel ne contient aucun espace réservé à la preuve ni aucun axiome ajouté. Les déclarations ont été rejouées via le noyau de Lean et via lean4lean, une implémentation indépendante du vérificateur de types de Lean, et un comparateur utilisant les deux noyaux a accepté les quatre théorèmes finaux. Lors d’un test de contrôle sur une deuxième machine, le comparateur a accepté une petite solution correcte et en a rejeté quatre délibérément fausses.

La preuve suit une stratégie exposée par les mathématiciens Shachar Lovett et Jiapeng Zhang, basée sur des certificats fractionnaires et des ensembles de niveaux, mais remplace une inégalité que leur plan avait laissée comme conjecture par une nouvelle inégalité toutes paires construite sur une paire de paramètres d'entrée générée par un déterminant - une construction qui, selon le PSI, va au-delà du précédent lemme du papillon de David Reimer.

Surveillance humaine et limites vérifiées

David Turturean, membre de l'équipe technique du PSI, a développé et dirigé le système de recherche, a défini le problème, a incité le modèle à élaborer une première ébauche et a révisé cette ébauche ; le référentiel le désigne comme responsable de l'exactitude du document. Jim Halverson a audité la preuve et Phiala Shanahan a commenté la formalisation. Le référentiel révèle que les modèles d'IA ont produit les déclarations mathématiques, la première ébauche et la formalisation Lean.

La vérification a également des limites explicites, ce que reconnaît le document du PSI. Un lecteur humain doit toujours confirmer que la déclaration formelle du Lean correspond à la conjecture imprimée, et le papier lisible par l'homme n'est pas lui-même vérifié par une machine. Le noyau Lean, les définitions de la bibliothèque Mathlib et les machines utilisées pour la vérification font toujours partie de la base de confiance.

Réaction d'experts

L'annonce fait suite à un article d'août 2026 rédigé par Guy Blanc, Jordan Docter, Carmen Strassle et Li-Yang Tan, qui définissait les conséquences de la simulation classique pour les algorithmes quantiques parallèles – un résultat partiel qui ne correspondait pas à la conjecture complète. Selon le PSI, les quatre chercheurs ont lu la preuve complète, ont fourni des commentaires et préparent un exposé plus court destiné aux experts.

Dans leur évaluation publiée au PSI, les chercheurs ont écrit: "Il s'agit d'un résultat énorme. Il résout une conjecture vieille de plusieurs décennies avec des implications importantes pour la nature des problèmes qui admettent des accélérations quantiques. La preuve s'appuie et étend plusieurs lignes de travail dans l'analyse des fonctions booléennes et de la combinatoire probabiliste. Tout est réuni d'une manière plutôt magique."

Ce que cela signifie pour l'informatique quantique

Pour la recherche en informatique quantique, le théorème accentue la frontière entre les problèmes pour lesquels les machines quantiques peuvent aider et les problèmes pour lesquels elles ne le peuvent pas. Il oriente les concepteurs d'algorithmes vers des problèmes dont la structure mathématique ou physique offre de réels avantages, plutôt que de rechercher des accélérations sur des entrées génériques. Le résultat ne détermine cependant pas quelles applications du monde réel fourniront des accélérations utiles, et le modèle de requête ne prend pas en compte tout le travail nécessaire au traitement des données. Il n'établit donc aucune limite générale sur le temps de calcul total ou sur la valeur commerciale des machines quantiques.

Le manuscrit et sa formalisation Lean 4 sont publics sur GitHub, où la communauté peut désormais tenter de vérifier la correspondance entre la déclaration formelle et la conjecture originale – l'étape restante qui sépare une preuve vérifiée automatiquement d'une preuve entièrement certifiée.

Pour Anthropic, l'épisode offre un aperçu de fonctionnalités qui n'ont été publiées sur aucune API : le modèle qui a produit les états mathématiques reste non public et la société n'a pas annoncé quand ni si il sera livré.

---

Restez à la Pointe de l'IA

Les dernières actualités, analyses et percées en IA — au même endroit.

Lire plus d'actualités IA →