Enfin, il y avait un problème que seuls les ordinateurs quantiques peuvent résoudre

Depuis des années, les informaticiens recherchent des tâches d'un certain type que seul un ordinateur quantique serait capable de résoudre, mais pas un ordinateur classique, même des générations futures. Et ils ont donc trouvé l'un d'eux.

Aux premiers stades de l'étude des ordinateurs quantiques, les informaticiens ont posé une question à laquelle, à leur avis, était censée révéler une vérité profonde sur les capacités de ces machines futuristes. 25 ans plus tard, une réponse a été trouvée. Dans un article publié en mai 2018, les informaticiens Ren Rez et Avishai Tal ont fourni des preuves convaincantes que la puissance de calcul des ordinateurs quantiques dépasse tout ce que les ordinateurs classiques peuvent réaliser.

Rez, professeur à l'Université de Princeton et au Wiseman Institute of Science, ainsi que Tal, postdoctorant de l'Université de Stanford, ont identifié un type particulier de problème informatique. Ils ont prouvé, avec une mise en garde, que les ordinateurs quantiques pouvaient résoudre efficacement le problème, et les ordinateurs traditionnels seraient bloqués pour toujours, essayant de le faire. Les informaticiens recherchent un tel problème depuis 1993, lorsqu'ils ont identifié pour la première fois la classe de tâches BQP , qui comprend toutes les tâches qu'un ordinateur quantique peut résoudre.

Depuis lors, ils espéraient opposer la classe de tâches BQP connue sous le nom de PH, qui comprend toutes les tâches qui peuvent être effectuées sur n'importe quel ordinateur classique, même celle incroyablement avancée développée par une civilisation du futur. La possibilité d'un tel contraste dépendait de la découverte d'un problème qui appartenait à la classe BQP, mais pas à la classe PH. Et maintenant, Rez et Tal l'ont fait.

Ce résultat ne rend pas les ordinateurs quantiques meilleurs que les classiques d'un point de vue pratique. Premièrement, les informaticiens théoriques savent déjà que les ordinateurs quantiques sont capables de résoudre toutes les tâches dont les classiques sont capables. Et les ingénieurs ont du mal à résoudre le problème de la création d'une machine quantique utile. Mais les travaux de Reza et Tal démontrent la différence dans les catégories dans lesquelles se trouvent les ordinateurs quantiques et classiques - et que même dans un monde où les ordinateurs classiques ont dépassé les limites de tous les rêves, les ordinateurs quantiques peuvent toujours les devancer.

Classes quantiques

La tâche fondamentale de l'informatique théorique est de diviser les tâches en classes de complexité. La classe de complexité contient toutes les tâches qui peuvent être résolues avec une ressource spécifique, comme le temps ou la mémoire.

Les scientifiques, par exemple, ont découvert un algorithme efficace qui vérifie si un nombre est premier. Cependant, ils n'ont pas pu trouver d'algorithme efficace pour trouver des facteurs premiers de grands nombres. Par conséquent, ils croient (bien qu'ils n'aient pas pu le prouver) que ces deux problèmes appartiennent à différentes classes de complexité.

Deux classes de difficulté célèbres sont P et NP. P représente toutes les tâches qu'un ordinateur classique peut résoudre rapidement. (Le problème «est le nombre premier?» Appartient à P). NP comprend toutes les tâches qu'un ordinateur classique ne résout pas nécessairement rapidement, mais l'exactitude de la solution existante, qu'il peut vérifier rapidement. («Quels sont les facteurs premiers d'un nombre?» Appartient à NP). Les scientifiques pensent que les classes P et NP sont différentes, mais la tâche de prouver cette différence est le plus difficile et le plus important des problèmes ouverts dans ce domaine.


Un PH contient un NP qui contient P. Le BQP est-il une classe distincte du PH?

En 1993, les informaticiens Ethan Bernstein et Umesh Wazirani ont défini une nouvelle classe de complexité, qu'ils ont appelée BQP, ou «temps polynomique quantique avec limitation de la probabilité d'erreur». Ils ont défini la classe comme contenant toutes les tâches de prise de décision - tâches avec la réponse «oui» ou «non» - que les ordinateurs quantiques sont capables de résoudre efficacement. Vers la même époque, ils ont prouvé que les ordinateurs quantiques sont capables de résoudre toutes les tâches dont les classiques sont capables. Autrement dit, BQP contient toutes les tâches contenues dans P.

Un autre exemple de classes de tâches individuelles. Le problème du vendeur demande si un chemin passant par certaines villes est plus court qu'une distance donnée. Une telle tâche est en NP. Une tâche plus difficile demande si cette distance est le chemin le plus court à travers ces villes. Une telle tâche est en PH.

Cependant, ils n'ont pas pu déterminer si le BQP contient des tâches qui ne font pas partie d'une autre classe de tâches importante, appelée PH ou «hiérarchie polynomiale». PH est une généralisation de NP. Il contient toutes les tâches qui peuvent être obtenues en commençant par une tâche de NP, et en la compliquant, en ajoutant des déclarations de clarification comme «si» et «pour tout le monde». Les ordinateurs classiques ne peuvent toujours pas résoudre la plupart des problèmes de PH, mais cette classe peut être considérée comme une classe de problèmes que les ordinateurs classiques pourraient résoudre s'il s'avérait que P est équivalent à NP. En d'autres termes, pour comparer BQP et PH, il est nécessaire de déterminer si les ordinateurs quantiques ont un avantage sur les ordinateurs classiques, qui restera même si les ordinateurs classiques apprennent soudainement à résoudre beaucoup plus de problèmes qu'ils ne peuvent en résoudre aujourd'hui.

«Le PH est l'une des classes de complexité les plus simples qui existe», a déclaré Scott Aaronson , spécialiste informatique à l'Université du Texas à Austin. "Nous voulons donc en quelque sorte connaître la place de l'informatique quantique dans un monde de complexité classique."

La meilleure façon de séparer les deux classes de difficulté est de trouver un problème dont on peut prouver qu'il est inclus dans l'une d'entre elles et non inclus dans l'autre. Cependant, en raison d'une combinaison d'obstacles fondamentaux et techniques, une telle tâche était très difficile à trouver.

Pour trouver une tâche qui appartient à BQP, mais pas à PH, vous devez définir quelque chose auquel "un ordinateur classique, par définition, ne pourrait même pas vérifier efficacement la réponse, sans parler de la trouver", a déclaré Aaronson. «Cela élimine les nombreuses tâches avec lesquelles nous travaillons en informatique.»

Ask oracle

Défi. Supposons que nous ayons deux générateurs de nombres aléatoires, chacun produisant une séquence de chiffres. Question à l'ordinateur: ces deux séquences sont-elles complètement indépendantes l'une de l'autre, ou sont-elles en quelque sorte imperceptiblement connectées (par exemple, une séquence est-elle obtenue par la transformée de Fourier de l' autre)? Aaronson a introduit cette tâche de «furrelation» en 2009 et a prouvé qu'elle appartient à BQP. La deuxième étape, plus difficile, reste celle de prouver que la furrelation n'est pas incluse dans le PH.


Ran rez

Dans un sens, c'est exactement ce qu'a fait Resu et Talu. Leur travail sépare BQP et PH avec l'aide de la soi-disant " oracle " ou "boîte noire". Il s'agit d'un résultat courant en informatique, auquel les chercheurs ont recours lorsque ce qu'ils veulent prouver ne leur est en aucun cas donné.

La meilleure façon de séparer les classes de complexité BQP et PH est de mesurer le temps de calcul nécessaire pour résoudre les problèmes de chaque classe. Mais l'informatique n'a pas «une connaissance approfondie du temps réel de calcul ou la capacité de le mesurer», a déclaré Henry Youn, informaticien à l'Université de Toronto.

Au lieu de cela, quelque chose d'autre est mesuré en informatique, qui est censé fournir une compréhension du temps de calcul qui ne peut pas être mesurée directement. Les scientifiques calculent le nombre d'appels informatiques à «l'oracle» pour répondre à la question. L'oracle semble donner des indices. Nous ne savons pas comment il les reçoit, mais nous savons qu'ils sont fiables.

Si votre tâche est de savoir s'il existe une connexion secrète entre deux générateurs de nombres aléatoires, vous pouvez poser des questions oracle comme «quel sera le sixième nombre de chaque générateur?» Ensuite, vous devez comparer la puissance de calcul en fonction du nombre d'invites nécessaires à chaque ordinateur pour résoudre le problème. Un ordinateur qui a besoin de plus d'indications s'exécute plus lentement.

«Dans un sens, nous comprenons beaucoup mieux ce modèle. Elle parle plus d'informations que d'informatique », a expliqué Tal.


Avishai Tal

Les nouveaux travaux de Reza et Tal prouvent qu'un ordinateur quantique aura besoin de beaucoup moins d'indices pour résoudre un problème de furrelation qu'un problème classique. De plus, un ordinateur quantique n'a besoin que d'un indice, malgré le fait que PH ne dispose pas d'un algorithme pour résoudre un tel problème, même avec un nombre illimité d'indices. "Cela signifie qu'il existe un algorithme quantique extrêmement efficace qui résout un tel problème", a déclaré Rez. "Mais si nous ne considérons que les algorithmes classiques, alors même si nous arrivons aux classes supérieures des algorithmes classiques, ils ne pourront pas y faire face." Cela prouve qu'avec l'oracle, la furrelation fait référence aux tâches appartenant au BQP, mais pas au PH.

Rez et Tal ont presque atteint ce résultat il y a environ quatre ans, mais n'ont pas pu franchir une étape dans l'épreuve du futur. Et puis, juste un mois avant la publication, Tal a entendu parler d'un nouveau travail sur les générateurs de nombres pseudo-aléatoires, et a réalisé que les technologies de cet article donnaient juste ce dont lui et Rez avaient besoin pour terminer le leur. "C'était une pièce manquante", a expliqué Tal.

La nouvelle de la séparation des classes BQP et PH s'est rapidement répandue. «Le monde de la complexité quantique est en effervescence», a écrit Lance Fortnau, spécialiste informatique à l’Université de technologie de Géorgie le lendemain de la publication de l’ouvrage.

Le travail donne une confiance irréfutable que les ordinateurs quantiques existent dans un monde informatique distinct des ordinateurs classiques (au moins par définition avec l'oracle). Même dans un monde où P est équivalent à NP - où résoudre le problème du voyageur de commerce est aussi simple que de trouver la ligne la plus appropriée dans la feuille de calcul - la preuve de Reza et Tal montre qu'il existe des problèmes que seul un ordinateur quantique peut résoudre.

"Même si P était équivalent à NP, même avec une hypothèse aussi forte", a déclaré Fortnau, "les ordinateurs quantiques ne rattraperont toujours pas."