Yuvin Tan, 18 ans, a prouvé que les ordinateurs classiques peuvent résoudre le «problème de recommandation» presque aussi rapidement que les ordinateurs quantiques. Ce résultat invalide l'un des meilleurs exemples d'accélération quantique des calculs.
Un adolescent du Texas a assiégé le développement de l'informatique quantique. Dans un article publié ce mois-ci sur Internet
, Yuvin Tan
, 18 ans, a prouvé que les ordinateurs ordinaires peuvent résoudre un problème informatique important à une vitesse
potentiellement comparable aux ordinateurs quantiques.
Dans sa forme la plus pratique, le problème des recommandations est lié à la façon dont des services comme Amazon et Netflix déterminent les produits que vous aimerez. Les informaticiens le considéraient comme l'
un des meilleurs exemples de tâches qui seraient résolues de façon exponentielle plus rapidement sur les ordinateurs quantiques - ce qui soulignait les
capacités potentielles
de ces machines futuristes. Et maintenant, Tan a réfuté cette opinion.
«C'était l'un des exemples déterminants de l'accélération quantique - et maintenant elle a disparu», explique Tang, qui est diplômé de l'Université du Texas à Austin au printemps et commence ses études de doctorat d'automne à l'Université de Washington.
En 2014, à l'âge de 14 ans, Tang a franchi les 4e, 5e et 6e années et est entré à l'Université du Texas, où il est diplômé en mathématiques et en informatique. Au printemps 2017, Tan a suivi un cours sur l'information quantique, dispensé par
Scott Aaronson , un chercheur bien connu dans le domaine de l'informatique quantique. Aaronson a reconnu un étudiant au talent inhabituel à Tan et l'a invité à devenir son conseiller dans un projet de recherche indépendant. Aaronson a donné à Tan plusieurs tâches à choisir, y compris la question des recommandations. Tan l'a choisie à contrecœur.
"J'ai hésité parce que cela semblait plutôt compliqué, mais c'était la plus simple de toutes les tâches qu'il m'a proposées", a déclaré Tan.
L'objectif des recommandations est de fournir des recommandations sur les produits que l'utilisateur peut aimer. Considérez Netflix. Il sait quels films vous avez regardés. Il sait ce que des millions de ses utilisateurs ont regardé. Avec ces informations, est-il possible de savoir ce que vous voulez chercher plus loin?
Ces données peuvent être représentées sous la forme d'une immense grille, ou matrice, au-dessus de laquelle tous les films sont répertoriés, sur le côté tous les utilisateurs, et à l'intérieur il y a des valeurs qui mesurent à quel point chacun des utilisateurs a aimé chaque film. Un bon algorithme produira une liste de recommandations, détectant rapidement et précisément les similitudes entre les films et les utilisateurs, et remplissant les cellules vides de la matrice.
En 2016, les informaticiens
Iordanis Kerenidis et
Anupam Prakash ont publié un
algorithme quantique qui a résolu le problème de recommandation de manière exponentielle plus rapidement que n'importe lequel des algorithmes classiques connus. Ils ont reçu une telle accélération quantique, en particulier, en raison de la simplification du problème. Au lieu de remplir toute la matrice et de déterminer le seul meilleur produit à recommander, ils ont trouvé un moyen de diviser les utilisateurs en un petit nombre de catégories - aiment-ils les superproductions ou le cinéma indépendant? - et traiter les données existantes de manière à formuler une recommandation qui serait tout simplement assez bonne.
Au moment où les travaux de Kerenidis et Prakash sont apparus, il y avait très peu d'exemples de problèmes que les ordinateurs quantiques étaient censés résoudre de manière exponentielle plus rapidement que les classiques. Pour la plupart, ces tâches étaient spécialisées - des problèmes étroits spécifiquement conçus pour tirer parti des atouts des ordinateurs quantiques (y compris le problème de la «
corrélation » dont nous avons déjà parlé). Le travail de Kerenidis et Prakash était intéressant car il mettait en évidence un vrai problème, important pour les gens, dans lequel les ordinateurs quantiques dépassaient les classiques.
"De mon point de vue, ce fut l'un des premiers exemples d'apprentissage automatique et de traitement des mégadonnées, dans lequel nous avons montré que les ordinateurs quantiques peuvent faire quelque chose que nous ne savons pas encore faire en utilisant des méthodes classiques", a déclaré Kerenidis, spécialiste en l'informatique de l'Institut de Recherche en Informatique de Paris.
Kerenidis et Prakash ont prouvé qu'un ordinateur quantique peut résoudre le problème des recommandations de manière exponentielle plus rapidement que n'importe lequel des algorithmes connus, mais ils n'ont pas prouvé qu'il n'y a pas d'algorithme classique rapide. Par conséquent, quand Aaronson a commencé à travailler avec Tan en 2017, il a posé exactement une telle tâche - prouver l'absence d'un algorithme classique rapide, confirmant l'accélération quantique de Kerenidis et Prakash.
"Il me semblait que ce serait un point important que nous allons mettre en place pour terminer cette histoire", a déclaré Aaronson, qui à l'époque croyait qu'il n'existait pas d'algorithme classique rapide.
Tang a commencé à travailler cet automne 2017, espérant que la tâche des recommandations ferait l'objet de sa thèse. Pendant plusieurs mois, Tan a tenté de prouver l'impossibilité de l'existence d'un algorithme classique. Le temps a passé et Tan a commencé à penser qu'un tel algorithme existait peut-être.
"J'ai commencé à croire à l'existence de l'algorithme classique, mais je n'ai pas pu m'en convaincre, car Scott pensait qu'il n'existait pas et il était une autorité pour moi", a déclaré Tan.
Enfin, alors que la date limite pour la dissertation était déjà expirée, Tan a écrit une lettre à Aaronson, où il a avoué ses soupçons croissants. "Tan m'a essentiellement écrit ce qui suit: je pense qu'il existe un algorithme classique rapide", a déclaré Aaronson.
Tout au long du printemps, Tang a noté les résultats et a travaillé avec Aaronson pour clarifier certaines étapes de la preuve. Découvert par Tan, l'algorithme classique rapide a été inspiré par l'algorithme quantique rapide trouvé par Kerenidis et Prakash deux ans auparavant. Tan a démontré que l'échantillonnage quantique utilisé dans leur algorithme peut être reproduit dans des conditions classiques. L'algorithme Tan, comme l'algorithme Kerenidis et Prakash, a été exécuté en temps polylogarithmique - c'est-à-dire que le temps de calcul a été estimé par le logarithme de paramètres tels que le nombre d'utilisateurs et de produits - et a été exponentiellement plus rapide que tout autre algorithme classique précédemment connu.
Après l'achèvement de l'algorithme par Tan, Aaronson a voulu s'assurer qu'il était correct avant la publication. "J'étais toujours inquiet du fait que si après la publication de l'œuvre de Tan il s'avérait incorrect, alors le premier gros travail de la carrière de Tan se révélerait être un zilch", a déclaré Aaronson.
Aaronson prévoyait d'assister à un atelier d'informatique quantique à l'Université de Californie à Berkeley en juin. Les sommités de cette région devaient s'y rassembler, notamment Kerenidis et Prakash. Aaronson a invité Than avec lui à Berkeley afin de présenter de manière informelle son algorithme après la partie officielle de la conférence.
Le matin du 18 et le matin du 19 juin, Tan a donné deux conférences, répondant aux questions du public. Au bout de quatre heures, un consensus a été atteint: l'algorithme de Tan classique ressemble au bon. Ce que beaucoup de personnes présentes ne comprenaient pas, c'était la jeunesse de Tan. "Je ne savais pas que Yuvin avait 18 ans, et cela ne m'a certainement pas semblé vrai d'après les résultats des conversations. Il me semblait que Juvin avait une conversation en tant qu'homme adulte », a déclaré Kerenidis. Désormais, l'algorithme fera l'objet d'un examen formel par les pairs avant sa publication.
Pour l'informatique quantique, le résultat Tan est un pas en arrière. Ou pas. Tang a éliminé l'un des exemples les plus compréhensibles et les meilleurs d'avantages quantiques. Dans le même temps, le travail de Tan est une autre preuve de l'existence d'une
interaction fructueuse entre les études des algorithmes classiques et quantiques.
«Tang élimine l'accélération quantique de Kerenidis et Prakash, mais dans un autre sens, Tang contribue à une grande amélioration et est basé sur leur travail. Tang n'aurait jamais trouvé son algorithme classique s'ils n'avaient pas publié leur quantum », a déclaré Aaronson.