Les progrès majeurs de l’informatique quantique rendus obsolètes par un adolescent

Ewin Tang, 18 ans, a prouvé que les ordinateurs classiques peuvent résoudre le « problème de recommandation » presque aussi vite que les ordinateurs quantiques. Le résultat élimine l’un des meilleurs exemples d’accélération quantique.

Un adolescent du Texas a réduit d’un cran l’utilisation de l’informatique quantique. Dans un article publié en ligne au début du mois, Ewin Tang, 18 ans, a prouvé que les ordinateurs ordinaires peuvent résoudre un problème informatique important avec des performances potentiellement comparables à celles d’un ordinateur quantique.

Dans sa forme la plus pratique, le « problème de recommandation » concerne la manière dont des services comme Amazon et Netflix déterminent les produits que vous pourriez essayer. Les informaticiens l’avaient considéré comme l’un des meilleurs exemples d’un problème qui est exponentiellement plus rapide à résoudre sur les ordinateurs quantiques – ce qui en fait une validation importante de la puissance de ces machines futuristes. Maintenant, Tang a retiré cette validation.

« Ce fut l’un des exemples les plus probants d’accélération quantique, et ce n’est plus le cas « , a déclaré M. Tang, qui a obtenu son diplôme de l’Université du Texas, à Austin, au printemps et qui commencera un doctorat à l’Université de Washington à l’automne.

En 2014, à l’âge de 14 ans et après avoir sauté la quatrième à la sixième année, Tang s’est inscrit à l’UT Austin et s’est spécialisé en mathématiques et en informatique. Au printemps 2017, Tang a suivi un cours sur l’information quantique donné par Scott Aaronson, un éminent chercheur en informatique quantique. Aaronson a reconnu Tang comme un étudiant exceptionnellement talentueux et s’est offert comme conseiller sur un projet de recherche indépendant. Aaronson a donné à Tang une poignée de problèmes à choisir, y compris le problème de la recommandation. Tang l’a choisi à contrecœur.

« J’hésitais parce que cela me paraissait un problème difficile quand je l’ai regardé, mais c’était le plus facile des problèmes qu’il m’a donnés, » dit Tang.

Le problème de recommandation est conçu pour donner une recommandation pour les produits que les utilisateurs aimeront. Prenons le cas de Netflix. Il sait quels films vous avez regardés. Il sait ce que tous ses autres millions d’utilisateurs ont regardé. Compte tenu de cette information, qu’est-ce que vous voudrez probablement regarder par la suite ?

Vous pouvez considérer ces données comme étant disposées dans une grille géante, ou matrice, avec des films listés en haut, des utilisateurs listés sur le côté et des valeurs aux points de la grille qui quantifient si, ou dans quelle mesure, chaque utilisateur aime chaque film. Un bon algorithme produirait des recommandations en reconnaissant rapidement et précisément les similitudes entre les films et les utilisateurs et en remplissant les blancs dans la matrice.

En 2016, les informaticiens Iordanis Kerenidis et Anupam Prakash ont publié un algorithme quantique qui a résolu le problème de la recommandation exponentiellement plus rapidement que tout algorithme classique connu. Au lieu de remplir toute la matrice et d’identifier le meilleur produit à recommander, ils ont développé une façon de classer les utilisateurs dans un petit nombre de catégories – aiment-ils les blockbusters ou les films indépendants ? – et l’échantillonnage des données existantes afin de générer une recommandation qui était tout simplement assez bonne.

À l’époque des travaux de Kerenidis et Prakash, il n’y avait que quelques exemples de problèmes que les ordinateurs quantiques semblaient capables de résoudre exponentiellement plus rapidement que les ordinateurs classiques. La plupart de ces exemples étaient spécialisés – il s’agissait de problèmes étroits conçus pour jouer sur les points forts des ordinateurs quantiques (parmi lesquels le problème de « forrelation » dont a parlé Quanta plus tôt cette année). Le résultat de Kerenidis et Prakash a été passionnant parce qu’il a fourni un problème du monde réel que les gens se souciaient de savoir où les ordinateurs quantiques surpassaient les ordinateurs classiques.

« À mon sens, c’était l’un des premiers exemples d’apprentissage machine et de grandes données où nous avons montré que les ordinateurs quantiques peuvent faire quelque chose que nous ne savons toujours pas faire de manière classique « , explique Kerenidis, informaticien à l’Institut de recherche sur les fondements de l’informatique à Paris.

Kerenidis et Prakash ont prouvé qu’un ordinateur quantique pouvait résoudre le problème de recommandation exponentiellement plus rapidement que n’importe quel algorithme connu, mais ils n’ont pas prouvé qu’un algorithme classique rapide ne pouvait exister. Ainsi, quand Aaronson a commencé à travailler avec Tang en 2017, c’est la question qu’il a posée – prouver qu’il n’y a pas d’algorithme de recommandation classique rapide, et ainsi confirmer Kerenidis et l’accélération quantique de Prakash est réelle.

Cela m’a semblé être un  » t  » important à franchir pour compléter cette histoire « , a déclaré M. Aaronson, qui croyait à l’époque qu’aucun algorithme classique rapide n’existait.

Tang s’est mis au travail à l’automne 2017, dans l’intention que le problème de la recommandation serve de thèse principale. Pendant plusieurs mois, Tang a lutté pour prouver qu’un algorithme classique rapide était impossible. Au fil du temps, Tang a commencé à penser qu’un tel algorithme était peut-être possible après tout.

« J’ai commencé à croire qu’il existe un algorithme classique rapide, mais je ne pouvais pas vraiment le prouver à moi-même parce que Scott semblait penser qu’il n’y en avait pas, et qu’il était l’autorité, » dit Tang.

Enfin, alors que la date limite de dépôt de la thèse approchait, Tang a écrit à Aaronson et a admis une suspicion croissante : « Tang m’a écrit en disant, en fait, ‘je pense qu’il y a un algorithme classique rapide' », a dit Aaronson.

Tout au long du printemps, Tang a rédigé les résultats et a travaillé avec Aaronson pour clarifier certaines étapes de l’épreuve. L’algorithme classique rapide trouvé par Tang s’inspire directement de l’algorithme quantique rapide que Kerenidis et Prakash avaient trouvé deux ans auparavant. Tang a montré que le type de techniques d’échantillonnage quantique qu’ils utilisaient dans leur algorithme pouvait être reproduit dans un environnement classique. Comme Kerenidis et l’algorithme de Prakash, l’algorithme de Tang fonctionnait en temps polylogarithmique – c’est-à-dire le temps de calcul mis à l’échelle avec le logarithme de caractéristiques comme le nombre d’utilisateurs et de produits dans l’ensemble de données – et était exponentiellement plus rapide que tout algorithme classique connu précédemment.

Une fois l’algorithme terminé, Aaronson voulait s’assurer qu’il était correct avant de le rendre public. « J’avais encore peur qu’une fois que Tang aurait mis le journal en ligne, si c’était mal, le premier gros journal de la carrière de[Tang] ferait un carton « , a dit Aaronson.

M. Aaronson prévoyait assister à un atelier d’informatique quantique à l’Université de Californie, à Berkeley, en juin. Beaucoup des plus grands noms du domaine y étaient présents, dont Kerenidis et Prakash. Aaronson a invité Tang à venir à Berkeley pour présenter de manière informelle l’algorithme dans les jours qui ont suivi la conférence officielle.

Le matin des 18 et 19 juin, Tang a donné deux conférences tout en répondant aux questions de l’auditoire. Au bout de quatre heures, un consensus s’est dégagé : L’algorithme classique de Tang semblait correct. Ce que beaucoup de personnes présentes dans la salle n’ont pas réalisé, cependant, c’est à quel point l’orateur était jeune. « Je ne savais pas qu’Ewin avait 18 ans, et ce n’est certainement pas ce qu’on m’a dit. Pour moi [Ewin], c’était quelqu’un qui donnait une conférence très mûre « , a dit Kerenidis. L’algorithme fait maintenant l’objet d’un examen formel par les pairs avant publication.

Pour l’informatique quantique, le résultat de Tang est un échec. Ou pas. Tang a éliminé l’un des meilleurs exemples d’avantage quantique. Dans le même temps, l’article de Tang est une preuve supplémentaire de l’interaction fructueuse entre l’étude des algorithmes quantiques et classiques.

« Tang est en train de tuer l’accélération quantique[de Kerenidis et Prakash], mais dans un autre sens, Tang donne une grande amélioration et construit sur ce qu’ils ont fait. Tang n’aurait jamais pu trouver cet algorithme classique sans leur algorithme quantique, » dit Aaronson.

Via Quanta

1 commentaire sur “Les progrès majeurs de l’informatique quantique rendus obsolètes par un adolescent”

Laisser un commentaire

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.