Pendant vingt ans, les informaticiens se sont interrogés sur une question d’apparence simple : un ordinateur quantique peut-il vérifier des solutions à des problèmes qu’un ordinateur classique ne peut même pas décrire ?
La réponse est oui, et la preuve fait 96 pages.
Une équipe de quatre chercheurs, John Bostanci (Simons Institute / Columbia), Jonas Haferkamp (Ruhr University Bochum), Chinmay Nirkhe (University of Washington) et Mark Zhandry (Stanford), a prouvé que les preuves quantiques sont catégoriquement plus puissantes que les preuves classiques pour au moins un problème computationnel. L’article a remporté le prix du meilleur article à STOC 2026, la conférence de référence en informatique théorique.
« C’est un beau résultat », déclare Anand Natarajan, théoricien de l’information quantique au MIT qui n’a pas participé aux travaux. « Il y a plein d’idées nouvelles et fraîches qui en découlent. »
Ce que la preuve montre réellement
Le problème appartient à une branche de l’informatique théorique appelée théorie de la complexité, qui étudie comment les ressources nécessaires à la résolution d’un problème évoluent lorsque le problème grandit. Au cœur se trouvent les classes QMA (Quantum Merlin-Arthur) et QCMA (Quantum-Classical Merlin-Arthur).
Imaginons la situation : un étudiant (Merlin) tente de convaincre un professeur (Arthur) qu’un certain énoncé mathématique est vrai. Dans le scénario QMA, Merlin peut soumettre un état quantique, une collection fragile de qubits, comme preuve. Dans le scénario QCMA, Merlin ne peut soumettre qu’une chaîne classique de bits. La question, posée pour la première fois par Dorit Aharonov et Tomer Naveh en 2002, était de savoir si la version quantique est strictement plus puissante.
L’équipe a prouvé que oui, en construisant un problème appelé le problème de forrélation spectrale pour lequel un témoin quantique fonctionne mais un témoin classique ne le peut pas. Le problème est une sorte d’énigme médico-légale : étant donnés deux ensembles de données de mesure, déterminer s’ils proviennent du même objet quantique sous-jacent ou de deux objets différents. Un témoin quantique peut encoder la relation entre les deux ensembles de données directement ; un témoin classique ne peut tout simplement pas transporter suffisamment d’informations.
La preuve utilise une stratégie appelée « preuve par contradiction ». Les chercheurs ont d’abord supposé qu’une preuve classique pour le problème existait. Ensuite, ils ont montré qu’une telle preuve serait réutilisable, on pourrait utiliser le même témoin classique pour répondre à de nombreuses requêtes différentes. Mais cette réutilisabilité, ont-ils démontré, permettrait de résoudre une tâche difficile de devinette qui est prouvablement impossible. La contradiction signifie que l’hypothèse de départ était fausse : aucune preuve classique ne peut exister.
« C’est un peu par hasard que j’ai commencé à y penser », raconte Zhandry à Quanta Magazine. Son travail solo en novembre 2024 avait résolu la moitié du problème mais n’avait pas pu le terminer. Les quatre se sont réunis, et après neuf mois de travail intense, « Ça a vraiment dominé mon année. Je n’ai pratiquement pas fait grand-chose d’autre », confie Bostanci, ils ont produit la preuve complète.
Une seconde preuve indépendante
De façon remarquable, une seconde équipe est parvenue indépendamment à la même conclusion en utilisant une méthode complètement différente. Andrew Huang et Vinod Vaikuntanathan du MIT, avec Bostanci, ont produit une seconde séparation d’oracle en février 2026 (arXiv:2602.09385) qui est conceptuellement plus simple et donne également la première séparation entre les classes BQP/qpoly et BQP/poly, un domaine connexe concernant les conseils quantiques.
Le fait de disposer de deux preuves indépendantes, l’une ingénieuse mais complexe, l’autre plus simple et plus extensible, renforce la solidité du résultat.
La réserve de l’oracle
Les deux preuves sont des « séparations d’oracle » : elles montrent que QMA et QCMA diffèrent par rapport à une fonction boîte noire (un oracle) que l’ordinateur peut interroger mais dont il ne peut pas voir le fonctionnement interne. Une preuve inconditionnelle, sans oracle, nécessiterait des avancées révolutionnaires en théorie de la complexité, équivalent à prouver que P n’est pas égal à PSPACE.
Néanmoins, les séparations d’oracle sont considérées comme des preuves très solides. Chaque séparation connue entre les grandes classes de complexité a commencé comme un résultat d’oracle avant d’être affinée. L’histoire du domaine montre que lorsque deux classes diffèrent par rapport à un oracle, elles diffèrent presque toujours dans la réalité.
« Ce que nous avons est la preuve la plus solide à ce jour que la réponse est oui, les preuves quantiques sont plus puissantes », notent les chercheurs dans leur article.
Pourquoi c’est important
Pour le physicien spécialiste de l’informatique quantique, ce résultat pourrait ne pas changer les opérations quotidiennes. Le problème qui sépare les deux classes, le problème de forrélation spectrale, est soigneusement construit et artificiel. Mais les techniques développées dans la preuve, en particulier les méthodes d’oracle compressé par « seconde quantification » qui traitent le problème en termes de bosons, devraient trouver des applications en cryptographie et en conception d’algorithmes quantiques.
Le résultat clôt également l’une des principales questions ouvertes en théorie de la complexité quantique, un domaine qui pose des questions fondamentales sur ce qui peut et ne peut pas être calculé avec des ressources quantiques. Pour les chercheurs qui ont passé deux décennies à s’attaquer au problème QMA contre QCMA, la réponse est enfin là.
Traduit par Lydie
Sources
- Quanta Magazine: « Researchers Reveal the Power of ‘Quantum Proofs’ » (6 juillet 2026). https://www.quantamagazine.org/researchers-reveal-the-power-of-quantum-proofs-20260706/
- Bostanci, J., Haferkamp, J., Nirkhe, C., Zhandry, M. « Separating QMA from QCMA with a Classical Oracle. » arXiv:2511.09551. STOC 2026 Best Paper.
- Bostanci, J., Huang, A., Vaikuntanathan, V. « Separating Quantum and Classical Advice with Good Codes. » arXiv:2602.09385 (février 2026).