Pendant vingt ans, les informaticiens se sont affrontés sur une question d’une simplicité trompeuse : 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, il s’avère, est oui, et la preuve fait 96 pages.
Une équipe de quatre chercheurs, John Bostanci (Simons Institute / Columbia), Jonas Haferkamp (Université de la Ruhr à Bochum), Chinmay Nirkhe (Université de 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 au STOC 2026, la conférence phare en informatique théorique.
« C’est un résultat magnifique », a déclaré Anand Natarajan, théoricien de l’information quantique au MIT qui n’a pas participé aux travaux. « Il en émerge un tas d’idées neuves et originales. »
Ce que la preuve dé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 pour résoudre un problème évoluent à mesure que celui-ci grandit. Au cœur se trouvent les classes QMA (Quantum Merlin-Arthur) et QCMA (Quantum-Classical Merlin-Arthur).
Pour le comprendre : imaginez un étudiant (Merlin) tentant 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 forrelation spectrale pour lequel un témoin quantique fonctionne mais un témoin classique échoue. 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 directement la relation entre les deux ensembles de données ; 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. Puis ils ont montré qu’une telle preuve serait réutilisable, c’est-à-dire que l’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 de devinette difficile qui est prouvablement impossible. La contradiction signifie que l’hypothèse initiale était fausse : aucune preuve classique ne peut exister.
« C’est un peu par hasard que j’ai commencé à y penser », a confié Zhandry au magazine Quanta. Son travail en 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, « Cela a vraiment dominé mon année. Je n’ai pratiquement rien fait d’autre », a déclaré Bostanci, ils ont produit la preuve complète.
Une seconde preuve indépendante
Fait 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 offre également la première séparation entre les classes BQP/qpoly et BQP/poly, un domaine connexe concernant les conseils quantiques.
Avoir deux preuves indépendantes, l’ingué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 relativement à une fonction boîte noire (un oracle) que l’ordinateur peut interroger mais dont il ne peut voir le fonctionnement interne. Une preuve inconditionnelle, sans oracle, nécessiterait des avancées révolutionnaires en théorie de la complexité, équivalant à 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 classes majeures 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 relativement à 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 du calcul 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 forrelation 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 grandes questions ouvertes de la 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).