Scaling Laws for Parameter Setting in Digitized Counterdiabatic QAOA

Dans le vaste paysage de l'informatique moderne, certains des défis les plus tenaces consistent à trouver la meilleure disposition possible parmi un nombre vertigineux de possibilités. Qu'il s'agisse d'orienter des camions de livraison dans une ville, de planifier des machines d'usine ou de régler des transactions financières, il s'agit de problèmes d'optimisation combinatoire. Pendant des décennies, les scientifiques se sont tournés vers les ordinateurs quantiques — des machines qui utilisent les règles étranges du monde subatomique — pour résoudre ces énigmes plus rapidement que les machines classiques ne le pourraient jamais. L'un des outils les plus prometteurs pour cette tâche est un algorithme appelé l'Algorithme d'Optimisation Quantique Approchée, ou QAOA. Voyez cela comme une recherche guidée : l'ordinateur prépare un état quantique, applique une série d'opérations contrôlées par des nombres spécifiques appelés paramètres, puis mesure le résultat pour voir à quel point il s'est rapproché de la solution parfaite. Le problème est que, pour chaque nouveau problème, l'ordinateur doit généralement exécuter un processus long et lent pour déterminer les meilleurs nombres à utiliser. Cette étape de « réglage » consomme du temps et des ressources, annulant souvent l'avantage de vitesse que la machine quantique était censée apporter.

Les chercheurs Yaocheng Chen et Jiapei Zhuang ont trouvé un moyen de contourner ce goulot d'étranglement pour un type spécifique d'algorithme quantique conçu pour gérer des problèmes pondérés, où les différentes connexions entre les éléments ont des intensités différentes. Ils ont découvert que les meilleurs réglages pour les commandes de l'algorithme ne sont ni aléatoires ni uniques à chaque problème. Au contraire, ces réglages suivent un modèle prévisible basé sur deux faits simples concernant le problème lui-même : le nombre moyen de connexions dont disposent les éléments et la force de ces connexions. En étudiant des milliers de configurations de problèmes différentes en simulation, l'équipe a construit un ensemble de règles capables de prédire les réglages optimaux pour un nouveau problème simplement en observant ses statistiques de base. Cela signifie qu'un ordinateur quantique peut recevoir un nouveau problème non résolu et recevoir immédiatement les bonnes instructions pour commencer la recherche, sans avoir besoin de passer du temps à déterminer quelles devraient être ces instructions.

L'équipe s'est concentrée sur une version sophistiquée de l'algorithme standard connue sous le nom de QAOA de contre-diabatique numérisé. Alors que la version standard utilise deux types d'opérations pour parcourir les réponses possibles, cette version améliorée ajoute un troisième type d'opération conçu pour empêcher le système de rester bloqué ou de commettre des erreurs au cours de son évolution. Cette étape supplémentaire rend l'algorithme plus puissant mais aussi plus complexe, nécessitant le réglage de trois ensembles de nombres pour chaque couche du processus. Les chercheurs ont commencé par effectuer des simulations hors ligne massives sur une grande variété de structures de graphes — des cartes mathématiques de connexions — allant de simples anneaux à des réseaux aléatoires complexes. Ils ont optimisé les réglages pour chacun de ces milliers de graphes afin de trouver la performance absolue.

Ce qui a émergé de cette montagne de données est une régularité frappante. Lorsque les chercheurs ajustaient la taille des connexions et le nombre moyen de liens par élément, les réglages optimaux pour tous les différents graphes se regroupaient en un amas serré. C'était comme si les détails spécifiques de chaque graphe importaient moins que l'échelle globale du problème. L'équipe a réalisé qu'elle pouvait décrire les meilleurs réglages à l'aide d'une formule simple qui prend en entrée le nombre moyen de connexions et la force des liens. Cette formule agit comme une clé universelle : une fois que vous connaissez les statistiques de base d'un nouveau problème, vous pouvez les injecter et obtenir les nombres exacts nécessaires pour exécuter le circuit quantique. Le résultat est une prescription « figée », un ensemble de règles fixes qui assigne les paramètres corrects instantanément, sautant ainsi l'étape fastidieuse de la recherche.

Pour tester si ce raccourci fonctionnait réellement, les chercheurs ont effectué des simulations sur 1 050 graphes de test différents que l'algorithme n'avait jamais vus auparavant. Ils ont comparé leur approche basée sur une formule à une méthode standard qui utilise un ensemble de nombres fixes pour tout le monde. Dans chaque cas, des circuits peu profonds avec une seule couche d'opérations aux circuits plus profonds avec quatre couches, la méthode basée sur la formule a produit une probabilité moyenne de sélection de la solution optimale plus élevée que l'approche standard à réglage fixe. À une profondeur de quatre couches, la probabilité moyenne de la solution optimale pour la nouvelle méthode a atteint 19,36 %, contre 13,11 % pour l'approche standard à réglage fixe. Cet avantage s'est maintenu à travers différents types de réseaux et différentes manières d'assigner les forces de connexion. Les chercheurs ont même testé la méthode sur un processeur quantique réel, l'IBM ibm_fez, en utilisant de petits réseaux uniformes. Bien que le bruit du matériel réel ait compliqué les résultats aux niveaux plus profonds, la méthode basée sur la formule a tout de même montré un avantage clair au niveau le plus superficiel, prouvant que les règles dérivées des simulations pouvaient se traduire sur des machines physiques.

L'étude a également exploré si ces réglages précalculés pouvaient servir de bonne base pour un affinement ultérieur. Dans une expérience distincte, les chercheurs ont pris les réglages fournis par leur formule et les ont utilisés pour initialiser une recherche d'optimisation standard sur un petit ensemble de graphes. Ils ont constaté que commencer avec les nombres de la formule permettait à la recherche d'atteindre une meilleure solution beaucoup plus rapidement qu'en partant d'une supposition aléatoire. En fait, le départ basé sur la formule a permis d'atteindre une qualité de solution moyenne supérieure à ce qu'une recherche aléatoire pourrait atteindre même après 500 tentatives. Cela suggère que la formule ne se contente pas de remplacer la recherche ; elle fournit un tremplin de haute qualité qui rend tout affinement ultérieur plus efficace.

Cependant, les chercheurs ont pris soin de noter les points où leur méthode pourrait trébucher. Les règles ont été dérivées de graphes ayant un nombre modéré de connexions, et lorsqu'ils ont testé la formule sur des graphes possédant très peu de connexions, la performance a chuté, particulièrement dans les circuits plus profonds. Cela indique que si les lois d'échelle sont puissantes, elles ont des limites et ne doivent pas être appliquées aveuglément à tout type de réseau possible. De plus, la comparaison a été faite couche par couche, ce qui signifie que l'algorithme amélioré utilisait plus d'opérations physiques par étape que l'algorithme standard. Les chercheurs ont reconnu qu'une comparaison plus équitable nécessiterait de prendre en compte le nombre total d'opérations, une question qui reste ouverte pour des études futures.

En fin de compte, ce travail démontre que le comportement des algorithmes quantiques complexes peut être maîtrisé en comprenant la géométrie simple des problèmes qu'ils résolvent. En reconnaissant que les meilleurs réglages dépendent de l'échelle du réseau plutôt que de ses détails spécifiques, les chercheurs ont transformé un problème de réglage difficile, cas par cas, en un calcul direct. Ce changement permet aux ordinateurs quantiques de consacrer leur temps précieux à résoudre des problèmes plutôt qu'à apprendre comment les résoudre, rapprochant ainsi la promesse de l'optimisation quantique d'une réalité pratique. Les conclusions suggèrent que pour un large éventail de problèmes combinatoires, le chemin vers la meilleure réponse n'est pas un mystère à résoudre de zéro à chaque fois, mais un motif qui peut être lu directement à partir de la propre structure du problème.