C'est l'une des grandes questions de l'informatique : les ordinateurs peuvent-ils examiner n'importe quel problème en un temps raisonnable ? Oui, affirme un nouvel article spécialisé, qui suscite un grand enthousiasme.
Le plaisir ne fait que commencer avec P et NP : les informaticiens ont établi une hiérarchie des classes de complexité, des plus simples aux plus sophistiquées. L'ordinateur quantique a apporté un tournant : il permet de nouvelles stratégies lorsqu'il s'agit de vérifier l'exactitude de la solution donnée à un problème.
La longue histoire des classes de complexité
L'interrogatoire de plusieurs suspects
Après ce résultat, le domaine des systèmes de preuve interactifs s'est mis en sommeil. Du moins jusqu'à ce que certains chercheurs se demandent ce qui se passerait si les deux preuves n'étaient pas des ordinateurs classiques, mais des ordinateurs quantiques couplés entre eux par la physique quantique. C'est le phénomène d'intrication, sur lequel Albert Einstein s'était déjà penché, qui rend la chose possible
Il l'appelait "l'action à distance hantée", car si vous mesurez l'état de l'un des deux objets intriqués, vous déterminez également l'état de l'autre, quelle que soit la distance qui les sépare. Au début, cette situation donnait mal au ventre aux physiciens, mais on sait maintenant qu'aucune information ne peut être transportée de cette manière.
Au début, les chercheurs en complexité n'ont pas prêté beaucoup d'attention à la possibilité de prouver l'intrication, car ils pensaient que la classe de complexité associée, MIP*, serait plus petite que MIP ou même IP. Après tout, l'avantage de MIP est que l'on interroge séparément les ordinateurs omniscients. En revanche, lorsqu'ils sont entrelacés, la réponse de l'un affecte l'état de l'autre.
Les ordinateurs quantiques intriqués comme solution
Mais en 2012, la première grande surprise est arrivée : Vidick a démontré avec son collègue Tsuyoshi Ito de l'université de Waterloo que les ordinateurs quantiques intriqués permettent également de vérifier tous les problèmes de MIP en temps polynomial. Par conséquent, les deux classes de complexité sont au moins égales.
Lors de l'essai proprement dit, l'examinateur n'a plus qu'à garantir que les questions sont représentatives et pertinentes et que les réponses n'entraînent pas de contradictions. De cette manière, il peut effectuer le test en un temps raisonnable, le temps de calcul nécessaire augmentant simplement de manière polynomiale avec la longueur.
Un rebondissement inattendu pour les mathématiciens
Contrairement à ce que l'on pense souvent, il n'est pas toujours possible d'approximer un système infini par un système fini avec autant de précision que l'on veut
Spektrum der Wissenschaft
Nous sommes partenaires de Spectre des Sciences et souhaitons vous rendre plus accessible des informations fondées. Suivez Spectre des Sciences si vous aimez ses articles.
Des experts de la science et de la recherche rendent compte des dernières découvertes dans leur domaine – de manière compétente, authentique et compréhensible.
Les scientifiques aiment catégoriser les choses, du moins à un niveau abstrait. Les chimistes, par exemple, classent tous les éléments dans le tableau périodique. Les biologistes classent les êtres vivants de la Terre par familles et par espèces. Et les mathématiciens, au cours de la dernière décennie, après une longue recherche, ont trouvé et listé tous les groupes simples infinis.
Les informaticiens cherchent également à mettre de l'ordre, même si c'est un peu différent : ils classent les problèmes en fonction de leur complexité. Ils ont déjà constaté par le passé que certains problèmes sont très simples à résoudre pour les ordinateurs. Le temps de calcul nécessaire à leur résolution n'augmente que lentement (de manière polynomiale) avec la longueur du problème. Du point de vue des informaticiens, ces problèmes de calcul appartiennent donc à la classe de complexité P.
En revanche, les problèmes faciles à vérifier, même s'ils sont difficiles à résoudre, appartiennent à la classe NP. Un exemple est un sudoku difficile : il est difficile de trouver la bonne solution. Mais une fois qu'on l'a trouvée ou qu'on vous présente une feuille remplie, il est facile de vérifier qu'elle est correcte.
Problème de clique | Le problème de clique décrit la tâche consistant à trouver le nombre maximum de nœuds dans un graphe qui sont directement adjacents. Il appartient à la classe de complexité NP. La figure montre un algorithme de résolution du problème de clique. Dans ce cas, le nombre de clique est de quatre. Source : Thore Husfeldt at English Wikipedia [CC BY-SA (https://creativecommons.org/licenses/by-sa/3.0)]
Une question ouverte de la recherche sur la complexité a toujours été de savoir quelle était la complexité maximale d'un problème pour qu'un ordinateur puisse le vérifier en un temps raisonnable, c'est-à-dire polynomial. Une équipe dirigée par Zhengfeng Ji de l'Université de technologie de Sydney a trouvé une réponse surprenante qui suscite actuellement un grand intérêt parmi les spécialistes. Selon elle, même les problèmes les plus difficiles de l'informatique peuvent, en théorie, être abordés en un temps raisonnable.
"Je ne me souviens pas d'une seule personne qui se serait attendue à cela", écrit Scott Aaronson, informaticien respecté de l'université d'Austin, sur son blog. Si le travail résiste à l'examen d'experts indépendants, il s'agira de l'une des plus grandes surprises de l'informatique théorique de ce siècle.
Depuis les années 1970, les informaticiens tentent de subdiviser de plus en plus finement les classes de complexité. Pour ce faire, ils ont identifié des problèmes toujours plus compliqués que les NP. La vérification de la solution est la principale source de complexité. Dans certains cas, le temps nécessaire à cette tâche n'augmente plus de manière polynomiale avec la longueur du problème, mais de manière exponentielle. C'est donc beaucoup plus difficile qu'une grille de sudoku dont on vous donne la solution.
Pour pouvoir classer de tels problèmes, les informaticiens ont introduit dans les années 1980 des systèmes de preuve interactifs. Ils ont imaginé un ordinateur tout-puissant, le "maître de la preuve". Celui-ci est toujours en mesure de fournir la solution d'un problème, quelle que soit sa complexité. Il peut donc calculer des problèmes bien plus compliqués que des grilles de sudoku. Il dispose d'une capacité de mémoire infinie et peut en principe calculer indéfiniment.
Mais la personne qui apporte la preuve n'est pas digne de confiance, c'est pourquoi il faut en plus un vérificateur qui recalcule le résultat fourni. Dans le cas du sudoku, c'est lui qui s'assure que la solution est correcte. Contrairement à l'auteur de la preuve, l'examinateur est un ordinateur réaliste qui dispose de ressources limitées. Cela signifie que son temps de calcul ne peut dépendre que de manière polynomiale de la taille de la tâche . Comme la solution fournie par l'auteur de la preuve peut être extrêmement longue et compliquée, l'examinateur lui pose différentes questions pour essayer de s'assurer de sa véracité. Prenons l'exemple d'une table dans une pièce plongée dans l'obscurité totale, sur laquelle sont posés plusieurs blocs de bois de forme identique. La tâche consiste à les classer en fonction de leur couleur. L'expert - tout-puissant qu'il est - n'a aucun mal à le faire. Malgré l'obscurité, il divise les blocs en deux piles.
L'examinateur doit maintenant déterminer, en posant des questions, si deux blocs choisis au hasard dans deux piles différentes sont vraiment de couleurs différentes. Dans ce cas, l'auteur de la preuve pourrait dire qu'un des blocs est rouge et l'autre bleu. Mais est-ce vrai ? Ou l'auteur de la preuve ment-il ? Pour le savoir, l'examinateur peut cacher les blocs de bois derrière son dos, les intervertir et demander à l'auteur de la preuve lequel est le rouge. Si l'expérience est répétée suffisamment souvent, l'auteur de la preuve se trompera dans environ la moitié des cas s'il a menti, ou répondra toujours correctement - s'il a dit la vérité.
Les informaticiens ont découvert que seule une telle stratégie de questions permet de vérifier l'exactitude de la solution de certains problèmes. Si l'on tient compte de ces problèmes, la classe de complexité NP s'étend à "IP". Il existe même une possibilité d'aborder des problèmes encore plus complexes : Vous n'autorisez pas seulement un leader de preuve, mais plusieurs. Ils peuvent échanger des informations pendant qu'ils travaillent sur une tâche. Mais dès qu'ils fournissent un résultat et que l'examinateur l'examine, ils sont séparés les uns des autres.
De cette manière, la tâche sur laquelle l'examinateur travaille ensuite avec la stratégie de questions-réponses peut être encore plus compliquée - tout en étant examinée en un temps polynomial. En effet, il est plus facile pour l'examinateur d'interroger deux instances ou plus : De la même manière qu'un inspecteur de police a plus de chances de convaincre des témoins de mensonge s'il procède à plusieurs interrogatoires séparés, il est possible de résoudre des problèmes plus sophistiqués de cette manière. La classe de complexité associée "MIP" est encore plus grande que IP, comme l'ont découvert les informaticiens en 1988 https://dl.acm.org/doi/10.1145/62212.62223.
"La réaction naturelle de tout le monde, moi y compris, a été de donner désormais plus de pouvoir à ceux qui apportent la preuve", s'est souvenu il y a quelque temps l'informaticien Thomas Vidick du California Institute of Technology, coauteur de la nouvelle publication, dans Quanta Magazine. Enfin, les personnes qui apportent des preuves pourraient utiliser l'intrication pour coordonner leurs réponses lorsqu'elles sont interrogées par l'examinateur.
En 2019, un nouveau tournant a été pris. Les physiciens Anand Natarajan du California Institute of Technology et John Wright du Massachusetts Institute of Technology ont découvert que la classe d'ordinateur quantique MIP* est même plus grande que MIP. L'enchevêtrement n'est donc pas forcément un inconvénient, l'examinateur peut même l'utiliser à son avantage - et ainsi contre-vérifier des tâches encore plus complexes que prévu.
L'astuce consiste à utiliser l'entrelacement pour identifier les questions appropriées. En d'autres termes, les responsables de la preuve s'interrogent d'abord eux-mêmes. Cela peut sembler paradoxal à première vue, mais l'imbrication des deux personnes qui fournissent les preuves leur permet de tester plusieurs réponses en même temps et de passer ainsi en revue un plus grand nombre d'étapes de vérification possibles. Ils transmettent ces questions à l'examinateur
Cette stratégie de "questions corrélées" permet donc de vérifier une preuve plus rapidement. Cependant, il faut faire attention à ce que les réponses des personnes qui apportent la preuve ne soient pas elles aussi entrelacées. Cela reviendrait à avoir deux suspects qui se concertent pendant l'interrogatoire. Natarajan et Wright ont résolu le problème en utilisant un autre concept bizarre de la mécanique quantique : l'incertitude inhérente au microcosme, selon laquelle deux propriétés "complémentaires" d'un objet, comme la position et l'impulsion, ne peuvent pas être déterminées simultanément avec une précision arbitraire.
Lorsque l'on mesure la vitesse d'une particule et que l'on détermine ensuite sa position, on ne sait plus à quelle vitesse se trouve l'objet. C'est pourquoi les chercheurs ne peuvent effectuer que des mesures complémentaires, de sorte que leurs réponses ne s'influencent pas mutuellement. Si l'on demande au premier ordinateur quantique une valeur de calcul, cela efface l'information correspondante du deuxième ordinateur quantique.
Problème de clique | Le problème de clique décrit la tâche consistant à trouver le nombre maximum de nœuds dans un graphe qui sont directement adjacents. Il appartient à la classe de complexité NP. La figure montre un algorithme de résolution du problème de clique. Dans ce cas, le nombre de clique est de quatre. Source : Thore Husfeldt at English Wikipedia [CC BY-SA (https://creativecommons.org/licenses/by-sa/3.0)]
Désormais, les informaticiens savaient que MIP* dépassait la complexité de MIP. Mais la taille réelle de la classe n'était pas claire au départ. Dans quelle mesure est-il plus facile de vérifier les solutions en interrogeant des ordinateurs quantiques intriqués ? En fait, il semble que cela augmente la quantité de tâches de manière maximale : Comme Zhengfeng Ji, Natarajan, Vidick, Wright et Henry Yuen de l'Université de Toronto l'ont démontré dans leur article sensationnel , le MIP* contient tous les problèmes calculables de l'informatique.
Selon la preuve, MIP* est identique à la classe de complexité géante RE. Elle comprend tous les problèmes de décision (ceux dont la réponse est oui ou non) auxquels un ordinateur peut répondre par l'affirmative en un temps fini. Il comprend entre autres le fameux problème d'arrêt : Il s'agit de déterminer si un ordinateur s'arrête un jour de calculer une tâche - ou s'il continue de calculer pour toujours.
L'informaticien britannique Alan Turing a certes prouvé en 1936 qu'il n'existait aucun algorithme capable de résoudre le problème d'arrêt de manière générale. Mais cela ne contredit pas sa dernière publication. En effet, le travail de Ji et de ses collègues indique qu'un examinateur ordinaire peut vérifier en un temps polynomial l'affirmation de deux ordinateurs quantiques omniscients entrelacés qui affirment qu'un ordinateur s'arrête pour une tâche donnée.
Le problème d'inclusion porte notamment sur ce que l'on appelle les algèbres d'opérateurs, qui appartiennent au domaine mathématique de l'analyse fonctionnelle, mais qui apparaissent également dans la mécanique quantique. Et en effet, il existe une proposition physique équivalente au problème de Connes : toutes les corrélations autorisées par la mécanique quantique peuvent être approchées aussi bien que l'on veut par un nombre fini de qubits intriqués. Contrairement à ce que la plupart des scientifiques attendaient, le résultat des informaticiens théoriciens montre que cette affirmation est fausse.
Cela a des conséquences dramatiques, par exemple lorsqu'il s'agit de faire la différence entre un système fini et un système infini. Contrairement à ce que l'on pense souvent, il n'est pas toujours possible d'approximer un système infini par un système fini avec une précision arbitraire. Dans leur publication, Ji et ses collègues donnent l'exemple d'une situation dans laquelle deux personnes jouent à un jeu. Si elles sont toutes deux infiniment intriquées, elles ont une chance sur deux de gagner, mais si elles ne sont qu'infiniment intriquées, la probabilité est d'une chance et demie au maximum.
