Ewin Tang

Dès 2014, Ewin Tang publie ses premiers travaux de recherche dans le domaine de la technologie biomédicale. Ils portent sur l'imagerie in vivo par sondes optiques de macrophages polarisés lors de réactions à des corps étrangers[pub 1], d'infections bactériennes[pub 2] ou de dépôts de fibrine [pub 3], et sur la détection en temps réel de la réponse des neutrophiles[pub 4]. Elle saute les trois dernières classes du lycée et intègre à 14 ans l'Université du Texas à Austin[1]. En 2017, elle est repérée par le professeur Scott Aaronson, spécialiste de l'informatique quantique, qui lui propose de réaliser un projet de recherche sous sa direction en lui laissant le choix du sujet parmi plusieurs problèmes ouverts difficiles.Tang choisit le problème de recommandation.

Avant les résultats d'Ewin Tang, les meilleurs algorithmes classiques connus résolvant certains problèmes d'algèbre linéaire étaient exponentiellement plus lents, sous certaines hypothèses, que le meilleur algorithme quantique pour le même problème. En s'inspirant de la solution quantique basée sur l'algorithme de Harrow, Hassidim et Lloyd (HHL), Tang a découvert[pub 5] - [pub 6] - [pub 7] des algorithmes classiques résolvant ces problèmes en un temps similaire à celui des algorithmes quantiques, sous des hypothèses similaires, les "déquantifiant" ainsi et apportant une amélioration exponentielle par rapport aux meilleurs algorithmes classiques connus.

La première publication d'Ewin Tang en informatique quantique est son mémoire de premier cycle universitaire (en deux disciplines : informatique et mathématiques pures) de 2018 intitulé Un algorithme classique d'inspiration quantique pour les systèmes de recommandation[pub 5], sous la direction de Scott Aaronson. Ce travail détaille un nouvel algorithme qui résout le problème de recommandation ; par exemple, comment Amazon ou Netflix prédisent-ils quels livres ou films un consommateur spécifique appréciera personnellement ? L'algèbre linéaire permet d'appréhender le problème ainsi : étant donné m utilisateurs et n produits, ainsi que des données incomplètes sur les produits que les utilisateurs préfèrent (organisées dans une structure d'arbre binaire) ; en supposant qu'il n'y a pas beaucoup de façons différentes dont les utilisateurs classent leurs préférences (la matrice des préférences est donc de faible rang), quels sont les produits qu'un utilisateur donné peut vouloir acheter? Une stratégie classique d'algébrique linéaire pour résoudre ce problème consiste à reconstruire une approximation de la matrice de préférence complète et à l'utiliser pour prédire le prochain produit préféré. Une telle stratégie nécessite un temps au moins polynomial en la dimension de la matrice. En 2016, Iordanis Kerenidis et Anupam Prakash ont trouvé un algorithme quantique exponentiellement plus rapide ; cet algorithme utilise l'algorithme HHL pour échantillonner le produit directement à partir d'une approximation de la matrice de préférence sans reconstruire la matrice elle-même, évitant ainsi la limite polynomiale mentionnée ci-dessus. L'algorithme classique de Tang, inspiré de l'algorithme quantique rapide de Kerenidis et Prakash, est capable d'effectuer les mêmes calculs mais sur un ordinateur normal sans avoir besoin d'un apprentissage automatique quantique. Les deux approches fonctionnent en temps polylogarithmique, ce qui signifie que le temps de calcul total est seulement de l'ordre d'une puissance du logarithme des variables du problème telles que le nombre total de produits et d'utilisateurs. La différence est que Tang utilise une réplication classique des techniques d'échantillonnage quantique. Avant ce résultat, il était généralement admis qu'aucun algorithme classique rapide n'existait ; Kerenidis et Prakash n'ont pas tenté d'étudier la solution classique, et le travail assigné à Tang par Aaronson à l'origine était de prouver son inexistence[1]. Ewin Tang présente ses travaux les 18 et 19 juin 2018 à un atelier d'informatique quantique où Kerenidis et Prakash sont présents[2]. Après quatre heures de discussion, les chercheurs sont convaincus de la validité de l'algorithme classique de Tang.

La même année, elle commence son doctorat en informatique théorique à l'Université de Washington sous la direction de James Lee[1]. Elle poursuit ses recherches et généralise le résultat ci-dessus, en déquantifiant d'autres problèmes d'apprentissage automatique quantique basés sur l'algorithme HHL : analyse en composantes principales [pub 6] et régression stochastique de faible rang[pub 7].

Le résultat prouvé par Ewin Tang suscite de nombreuses réactions. On considère généralement que son algorithme classique aussi performant qu'un algorithme quantique pour le problème de recommandation élimine l'un des meilleurs exemples d'accélération quantique[1] - [3] - [4] - [5]. Certains chercheurs en tirent cependant des conclusions positives pour l'informatique quantique, comme Robert Young (directeur du Quantum Technology Centre de l'Université de Lancaster), qui rappelle que « Si nous n'avions pas investi dans l'informatique quantique, l'algorithme quantique qui a inspiré M.Tang[Note 1] n'aurait pas existé ».

Ewin Tang est nommée par le magazine Forbes dans sa liste annuelle (pour 2019) des 30 scientifiques américains de moins de 30 ans les plus influents[6].

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Ewin Tang » (voir la liste des auteurs).

Publications

Notes

Références

• Ressources relatives à la recherche :
  • Google Scholar
  • (en) Digital Bibliography & Library Project
• Page Web personnelle