Introduction
Les ordinateurs quantiques font l'objet de beaucoup de battage médiatique, mais la vérité est que nous ne savons toujours pas à quoi ils serviront. Ces appareils tirent parti de la physique particulière du monde subatomique et ont le potentiel d'effectuer des calculs que les ordinateurs classiques classiques ne peuvent tout simplement pas. Mais il s'est avéré difficile de trouver des exemples d'algorithmes avec un "avantage quantique" clair qui permet des performances au-delà de la portée des machines classiques.
Pendant la majeure partie des années 2010, de nombreux informaticiens ont estimé qu'un groupe particulier d'applications avait de grandes chances de trouver cet avantage. Certains calculs d'analyse de données seraient exponentiellement plus rapides s'ils étaient écrasés par un ordinateur quantique.
Puis vint Ewin Tang. En tant que jeune diplômée de 18 ans en 2018, elle a trouvé une nouvelle façon pour les ordinateurs classiques de résoudre ces problèmes, frapper l'avantage promis par les algorithmes quantiques. Pour beaucoup de ceux qui travaillent sur des ordinateurs quantiques, Tang Le travail de était un règlement de comptes. "Un par un, ces cas d'utilisation super excitants viennent d'être tués", a déclaré Chris Cade, informaticien théoricien au centre de recherche néerlandais sur l'informatique quantique QuSoft.
Mais un algorithme a survécu indemne : une torsion quantique sur une approche mathématique de niche pour étudier la « forme » des données, appelée analyse topologique des données (TDA). Après une avalanche d'articles en septembre, les chercheurs pensent maintenant que ces calculs TDA sont hors de portée des ordinateurs classiques, peut-être en raison d'un lien caché avec la physique quantique. Mais cet avantage quantique ne peut se produire que dans des conditions très spécifiques, remettant en question sa praticité.
Seth Lloyd, ingénieur en mécanique quantique au Massachusetts Institute of Technology qui a co-créé l'algorithme quantique TDA, se souvient très bien de son origine. Lui et son collègue physicien Paul Zanardi assistaient à un atelier de physique quantique dans une ville idyllique des Pyrénées en 2015. Quelques jours après le début de la conférence, ils sautaient des discussions pour traîner sur la terrasse de l'hôtel alors qu'ils essayaient de se faire une idée d'une technique mathématique "abstraite folle". dont ils avaient entendu parler pour analyser les données.
Zanardi était tombé amoureux des mathématiques sous-jacentes à TDA, qui étaient enracinées dans topologie, une branche des mathématiques concernée par les caractéristiques qui subsistent lorsque les formes sont écrasées, étirées ou tordues. "C'est l'une de ces branches des mathématiques qui imprègne tout", a déclaré Vedran Dunjko, chercheur en informatique quantique à l'université de Leiden. "Il y en a partout." L'une des questions centrales du domaine est le nombre de trous dans un objet, appelé nombre de Betti.
La topologie peut s'étendre au-delà de nos trois dimensions familières, permettant aux chercheurs de calculer les nombres de Betti dans des objets à quatre, 10 et même 100 dimensions. Cela fait de la topologie un outil attrayant pour analyser les formes des grands ensembles de données, qui peuvent également inclure des centaines de dimensions de corrélations et de connexions.
Introduction
Actuellement, les ordinateurs classiques ne peuvent calculer que des nombres de Betti jusqu'à environ quatre dimensions. Sur la terrasse de cet hôtel pyrénéen, Lloyd et Zanardi ont tenté de briser cette barrière. Après environ une semaine de discussion et d'équations griffonnées, ils avaient les bases d'un algorithme quantique qui pouvait estimer les nombres de Betti dans des ensembles de données de très grandes dimensions. Ils publié en 2016, et les chercheurs l'ont accueilli dans le groupe des applications quantiques pour l'analyse des données qui, selon eux, avaient un avantage quantique significatif.
En deux ans, TDA était la seule à ne pas avoir été impactée par le travail de Tang. Bien que Tang admette que TDA est "véritablement différente des autres", elle et d'autres chercheurs se sont demandé dans quelle mesure son évasion aurait pu être un coup de chance.
Dunjko et ses collègues ont décidé de tenter à nouveau de trouver un algorithme classique pour TDA qui pourrait éliminer son avantage quantique. Pour ce faire, ils ont tenté d'appliquer les méthodes de Tang à cette application particulière, sans savoir ce qui se passerait. « Nous n'étions vraiment pas sûrs. Il y avait des raisons de croire que celui-ci survit peut-être à la 'Tangisation' », se souvient-il.
Il a survécu. Dans les résultats publiés pour la première fois sous forme de préimpression en 2020 et publiés en octobre dans Quantum, l'équipe de Dunjko montré que la survie de TDA n'était pas un hasard. Pour trouver un algorithme classique qui pourrait suivre le rythme de l'algorithme quantique, "il faudrait faire quelque chose de différent que d'appliquer aveuglément le [processus] d'Ewin Tang à l'algorithme de Seth Lloyd", a déclaré Cade, l'un des co-auteurs de l'article.
Nous ne savons pas avec certitude si les algorithmes classiques ne peuvent pas rattraper TDA, mais nous y arriverons peut-être bientôt. "Sur les quatre étapes que nous devons franchir pour prouver cela … nous en avons peut-être fait trois", a déclaré Marcos Crichigno, physicien théoricien de la startup QC Ware. La meilleure preuve à ce jour provient d'un article qu'il a publié l'année dernière avec Cade montrant qu'un calcul topologique similaire ne peut pas être résolu efficacement par les ordinateurs classiques. Crichigno travaille actuellement pour prouver le même résultat spécifiquement pour TDA.
Crichigno soupçonne que la résilience de TDA indique un lien inhérent – et totalement inattendu – avec la mécanique quantique. Ce lien vient de la supersymétrie, une théorie de la physique des particules qui propose une symétrie profonde entre les particules qui composent la matière et celles qui portent des forces. Il s'avère, comme l'expliquait le physicien Ed Witten dans les années 1980, que les outils mathématiques de la topologie permettent de décrire facilement ces systèmes supersymétriques. Inspiré par le travail de Witten, Crichigno a été inverser cette connexion en utilisant la supersymétrie pour étudier la topologie.
« C'est fou. C'est une connexion vraiment, vraiment, vraiment étrange », a déclaré Dunjko, qui n'était pas impliqué dans le travail de Crichigno. "J'ai la chair de poule. Littéralement."
Cette connexion quantique cachée pourrait être ce qui distingue TDA des autres, a déclaré Cade, qui a travaillé avec Crichigno sur ce sujet. "Il s'agit vraiment, par essence, d'un problème de mécanique quantique, même si cela n'en a pas l'air", a-t-il déclaré.
Mais alors que TDA reste un exemple d'avantage quantique pour l'instant, des recherches récentes de Amazon Services Web, Google ainsi que Laboratoire de Lloyd au MIT a considérablement réduit les scénarios possibles dans lesquels l'avantage est le plus évident. Pour que l'algorithme fonctionne de manière exponentielle plus rapide que les techniques classiques - la barre habituelle pour un avantage quantique - le nombre de trous de grande dimension doit être incroyablement grand, de l'ordre de billions. Sinon, la technique d'approximation de l'algorithme n'est tout simplement pas efficace, annulant toute amélioration significative par rapport aux ordinateurs classiques.
C'est "un ensemble de conditions difficiles à trouver" dans les données du monde réel, a déclaré Cade, qui n'a participé à aucun des trois articles. Il est difficile de savoir avec certitude si ces conditions existent, donc pour l'instant, nous n'avons que notre intuition, a déclaré Ryan Babbush, l'un des principaux auteurs de l'étude de Google, et ni lui ni Cade ne s'attendent à ce que ces conditions soient courantes.
Tang, actuellement doctorant à l'Université de Washington, ne pense pas que la TDA soit l'application quantique pratique recherchée par le domaine, compte tenu de ces limites. "Je pense que le domaine dans son ensemble a été remodelé" pour s'éloigner de la chasse aux algorithmes, a-t-elle déclaré. Elle s'attend à ce que les ordinateurs quantiques soient plus utiles pour en savoir plus sur les systèmes quantiques eux-mêmes, et non pour analyser des données classiques.
Mais les chercheurs à l'origine des travaux récents ne voient pas la TDA comme une impasse. Lors d'une réunion Zoom entre toutes les équipes de recherche après la publication des récentes prépublications, "chacun d'entre nous avait une idée de ce qu'il fallait faire ensuite", a déclaré Dunjko, qui a travaillé avec l'équipe de Google. Crichigno, par exemple, espère que l'interrogation de ce lien entre la topologie et la mécanique quantique donnera lieu à des problèmes quantiques plus inattendus qui pourraient être particulièrement adaptés au calcul quantique.
Il y a toujours la menace d'une nouvelle approche classique créative faisant ce que Tang et Dunjko ne pouvaient pas, et finalement faisant tomber TDA. "Je ne parierais pas ma maison, ni ma voiture, ni mon chat", que cela n'arrivera pas, a déclaré Dunjko. "Mais l'histoire n'est pas morte. Je pense que c'est la principale raison pour laquelle je ne suis pas du tout inquiet.
