Un nouvel algorithme quantique accélère la résolution d'une vaste classe de problèmes

La version originale de cette histoire est parue dans Quanta Magazine .

Pour les informaticiens, résoudre des problèmes s'apparente à de l'alpinisme. Ils doivent d'abord choisir un problème à résoudre – un peu comme identifier un sommet à gravir – puis élaborer une stratégie pour le résoudre. Les chercheurs en physique classique et quantique s'affrontent en utilisant des stratégies différentes, avec une saine rivalité entre eux. Les chercheurs quantiques proposent un moyen rapide de résoudre un problème – souvent en gravissant un sommet que personne ne jugeait digne d'être escaladé – puis les équipes classiques s'affrontent pour voir si elles peuvent trouver une meilleure solution.

Cette compétition se termine presque toujours par une égalité virtuelle : lorsque les chercheurs pensent avoir conçu un algorithme quantique plus rapide ou plus performant que tout autre, les chercheurs classiques en proposent généralement un qui l'égale. La semaine dernière encore, une prétendue accélération quantique, publiée dans la revue Science , a suscité le scepticisme immédiat de deux groupes distincts qui ont montré comment effectuer des calculs similaires sur des machines classiques.

Mais dans un article publié l'année dernière sur le site de prépublication scientifique arxiv.org, des chercheurs ont décrit ce qui ressemble à une accélération quantique à la fois convaincante et utile . Ils ont décrit un nouvel algorithme quantique plus rapide que tous les algorithmes classiques connus pour trouver de bonnes solutions à une large gamme de problèmes d'optimisation (qui recherchent la meilleure solution possible parmi un nombre considérable de choix).

Jusqu'à présent, aucun algorithme classique n'a détrôné le nouvel algorithme, connu sous le nom d'interférométrie quantique décodée (IQD). C'est « une avancée majeure dans le domaine des algorithmes quantiques », a déclaré Gil Kalai , mathématicien à l'Université Reichman et éminent sceptique de l'informatique quantique . Les rapports sur les algorithmes quantiques suscitent l'enthousiasme des chercheurs, d'une part parce qu'ils peuvent apporter de nouvelles idées sur des problèmes complexes, et d'autre part parce que, malgré tout le buzz autour des machines quantiques, on ne sait pas clairement quels problèmes en bénéficieront réellement. Un algorithme quantique surpassant tous les algorithmes classiques connus dans les tâches d'optimisation représenterait une avancée majeure dans l'exploitation du potentiel des ordinateurs quantiques.

« Je suis enthousiaste », a déclaré Ronald de Wolf , informaticien théoricien au CWI, l'institut national de recherche en mathématiques et informatique des Pays-Bas, qui n'a pas participé au développement du nouvel algorithme. Il a toutefois averti qu'il était tout à fait possible que les chercheurs trouvent un jour un algorithme classique tout aussi performant. Et faute de matériel quantique, il faudra encore un certain temps avant de pouvoir tester empiriquement le nouvel algorithme.

Cet algorithme pourrait inspirer de nouveaux travaux dans le domaine classique, selon Ewin Tang , informaticien à l'Université de Californie à Berkeley, qui s'est fait connaître à l'adolescence en créant des algorithmes classiques comparables à ceux quantiques . « Ces nouvelles affirmations sont suffisamment intéressantes pour que je dise aux spécialistes des algorithmes classiques : "Hé, vous devriez consulter cet article et travailler sur ce problème" », a-t-elle déclaré.

Lorsque les algorithmes classiques et quantiques s'affrontent, c'est souvent sur le terrain de l'optimisation, un domaine qui vise à trouver les meilleures options pour résoudre un problème épineux. Les chercheurs se concentrent généralement sur des problèmes pour lesquels le nombre de solutions possibles explose à mesure que le problème s'aggrave. Quel est le meilleur moyen pour un camion de livraison de parcourir dix villes en trois jours ? Comment emballer les colis à l'arrière ? Les méthodes classiques de résolution de ces problèmes, qui impliquent souvent de passer intelligemment en revue les solutions possibles, deviennent rapidement intenables.

Le problème d'optimisation spécifique abordé par DQI est le suivant : on vous donne un ensemble de points sur une feuille de papier. Vous devez élaborer une fonction mathématique passant par ces points. Plus précisément, votre fonction doit être un polynôme, c'est-à-dire une combinaison de variables élevées à des exposants entiers et multipliées par des coefficients. Mais elle ne doit pas être trop compliquée, c'est-à-dire que les puissances ne doivent pas être trop élevées. Vous obtenez ainsi une ligne courbe qui ondule de haut en bas en parcourant la page. Votre tâche consiste à trouver la ligne ondulante qui touche le plus de points.

Des variantes de ce problème apparaissent sous diverses formes en informatique, notamment en codage d'erreurs et en cryptographie, domaines axés sur le codage sécurisé et précis des données lors de leur transmission. Les chercheurs du DQI ont constaté, en substance, que tracer une meilleure ligne revient à rapprocher un message codé bruité de sa signification exacte.

Mais tout cela est arrivé plus tard. Lorsque les chercheurs à l'origine de DQI ont commencé à travailler sur leur algorithme, ils n'avaient même pas ce problème en tête.

« Il aurait été tout à fait plausible pour un chercheur orienté vers un objectif de commencer par poser le problème, puis de déterminer si les algorithmes quantiques pouvaient le résoudre plus rapidement que les algorithmes classiques », a déclaré Stephen Jordan , physicien chez Google Quantum AI et l'un des principaux architectes de DQI. « Bien sûr, pour nous, cela ne s'est pas produit comme ça. Nous y sommes parvenus par un chemin détourné et tortueux. »

Jordan s'est engagé dans cette voie en 2023, lorsqu'il a rejoint Google et découvert qu'il collaborerait avec Eddie Farhi , un physicien de Google dont les travaux se concentrent depuis longtemps sur les algorithmes quantiques plus performants que les algorithmes classiques. (Farhi était autrefois le directeur de thèse de Jordan au Massachusetts Institute of Technology.) Jordan savait qu'en 2014, Farhi avait réalisé une attaque quantique sur un problème d'optimisation en pensant à l'énergie, les énergies inférieures correspondant à de meilleures solutions. Pour Farhi, l'énergie reliait l'optimisation à la physique quantique.

Mais Jordan souhaitait faire quelque chose de différent. Il s'est tourné vers un autre concept inhérent à la physique quantique : la reconnaissance de toute chose comme des ondes. Grâce à un outil mathématique appelé transformée de Fourier quantique, Jordan a trouvé un moyen de traduire en ondes quantiques toutes les réponses potentielles à une classe bien connue de problèmes d'optimisation. Ce faisant, il a pu manipuler le système quantique de manière à ce que des ondes plus grandes (sous forme d'amplitudes quantiques plus élevées) correspondent à de meilleures solutions.

Mais il restait un défi de taille à relever. Dans un système quantique, se demander « Quelle est la plus grande amplitude ? » n'est pas aussi simple que de reconnaître la plus grosse vague sur la plage. Le paysage quantique est incroyablement complexe, et il était difficile d'identifier les amplitudes quantiques correspondant aux meilleures solutions.

Après de nombreux faux départs, Jordan a réalisé une percée décisive : le processus de sélection des meilleures solutions s'est avéré similaire à celui d'élimination des erreurs dans les messages codés, appelé décodage. Il s'agit d'un domaine de l'informatique bien étudié, riche en techniques que Jordan pourrait explorer. En traduisant un problème d'optimisation en problème quantique, puis en y appliquant le prisme du décodage, il a découvert une nouvelle façon de développer des algorithmes quantiques.

Avec Noah Shutty , également chez Google, Jordan a commencé à tester des schémas de décodage, observant leurs performances face aux algorithmes classiques sur divers problèmes d'optimisation. Il leur fallait à la fois la bonne approche et un problème qui fonctionne. « Il s'avère que les algorithmes classiques sont difficiles à battre », a déclaré Jordan. « Après quelques mois d'essais, nous n'avions toujours pas remporté de victoires en informatique quantique. »

Mais finalement, le duo a découvert un algorithme de décodage, introduit dans les années 1960, permettant de détecter et de corriger les erreurs individuelles dans un message codé. Trouver ce problème était la clé. « Lorsque nous avons étudié la question, le succès a semblé immédiat », a déclaré Jordan. Ils avaient enfin trouvé un problème et une approche qui, ensemble, semblaient constituer une accélération quantique.

Bien sûr, cela ne signifiait pas que c'était infaillible. « Il existe peut-être une méthode classique capable de reproduire efficacement l'intégralité de votre approche », a déclaré Jordan. « De telles déquantifications ne sont pas toujours évidentes. »

Pour apaiser ces craintes, ils ont consulté Mary Wootters , experte en théorie du codage (et ancienne directrice de thèse de Shutty à l'Université de Stanford). Elle a soigneusement recherché tout algorithme classique connu susceptible d'égaler leur accélération quantique. L'avantage s'est maintenu. Les vérifications de l'équipe suggèrent également qu'il le restera. « Ils ont fait preuve de diligence raisonnable », a déclaré Tang.

Forts de cette analyse, ils ont examiné plus attentivement le problème d'optimisation qu'ils cherchaient à résoudre. Jordan craignait qu'il soit trop spécialisé et sans applications plus larges, mais Shutty a reconnu que ce problème de décodage était une variante de problèmes bien connus et utiles en matière de chiffrement et d'autres domaines.

Jordan reconnaît que sans une machine quantique suffisamment puissante, l'IQD restera une avancée théorique majeure. « L'IQD ne peut pas fonctionner sur les ordinateurs quantiques actuels », a-t-il déclaré. Mais ils continuent d'avancer. Depuis la publication de leurs travaux en août dernier, le groupe a étendu l'application de l'IQD au-delà du problème initial à une classe plus large de problèmes d'optimisation, incluant davantage de cas de ces problèmes de « meilleur chemin ».

Jusqu’à présent, a déclaré Jordan, il s’attend à ce que DQI puisse également battre les algorithmes classiques dans ces problèmes.

Pour l'instant, la communauté quantique reste enthousiaste. « Trouver des algorithmes quantiques qui présentent un avantage sur les algorithmes classiques est un projet passionnant depuis trente ans, et le nombre d'algorithmes qui présentent un tel avantage est limité », a déclaré Kalai. « Par conséquent, chaque nouvel algorithme est un motif de célébration. »

Article original reproduit avec la permission de Quanta Magazine , une publication éditoriale indépendante de la Fondation Simons dont la mission est d'améliorer la compréhension publique de la science en couvrant les développements et les tendances de la recherche en mathématiques et en sciences physiques et de la vie.