A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz

Résumé Technique : Une Heuristique de Réglage de Paramètres pour l'Ansatz d'Opérateur Alterné Quantique

Énoncé du Problème
L'Ansatz d'Opérateur Alterné Quantique (QAOA) est un algorithme quantique paramétré de premier plan pour la résolution de problèmes d'optimisation combinatoire. Cependant, trouver efficacement des paramètres de haute qualité ($\vec{\gamma}, \vec{\beta}$) demeure un défi pratique important. Le processus de réglage des paramètres implique généralement une boucle variationnelle quantique-classique où un optimiseur classique met à jour les paramètres en fonction de la valeur d'espérance d'une fonction de coût évaluée sur du matériel quantique ou via une simulation classique coûteuse. Ce processus est confronté à des difficultés telles que les plateaux stériles (barren plateaux), de nombreux optima locaux, et la mise à l'échelle exponentielle des ressources requises pour l'évaluation exacte des valeurs d'espérance classiques à mesure que le nombre de qubits ($n$) ou la profondeur du circuit ($p$) augmente. De plus, les dispositifs actuels de l'ère NISQ (Noisy Intermediate-Scale Quantum) exacerbent ces défis par le biais du bruit et des erreurs d'échantillonnage finies.

Méthodologie
Les auteurs proposent une « Heuristique Homogène pour le Réglage de Paramètres », une stratégie classique conçue pour remplacer l'évaluation coûteuse de la valeur d'espérance de la fonction de coût par un modèle classique efficace. Le cœur de cette approche repose sur le concept d'Homogénéité Parfaite.

1. Homogénéité Parfaite : Elle est définie comme une propriété d'état où tous les bitstrings $x$ partageant la même valeur de coût $c(x)$ possèdent des amplitudes quantiques identiques. Bien que cette propriété ne soit exacte que pour des problèmes symétriques spécifiques ou dans la limite de petits paramètres, des observations empiriques suggèrent des chevauchements élevés entre les états QAOA et les états parfaitement homogènes dans diverses configurations.
2. Proxy Homogène Classique : Les auteurs construisent un modèle classique, nommé « Proxy Homogène Classique », qui impose l'Homogénéité Parfaite par hypothèse. Dans ce proxy, l'état n'est pas décrit par $2^n$ amplitudes, mais par un ensemble d'amplitudes $Q(c)$ correspondant à chaque valeur de coût unique $c$.
   • L'évolution est modélisée selon une perspective de « somme de chemins ». Les auteurs remplacent le décompte exact des bitstrings à une distance de Hamming spécifique avec un coût $n(x; d, c)$ par une distribution dérivée analytiquement $N(c'; d, c)$ qui dépend uniquement des classes de coût.
   • Cela permet le calcul récursif des amplitudes $Q_\ell(c)$ pour chaque couche $\ell$ en utilisant l'Éq. (5), dont l'échelle est polynomiale par rapport à la taille du problème $n$ et au nombre de valeurs de coût distinctes $|C|$, à condition que $|C|$ croisse polynomialement avec $n$.
3. La Boucle Heuristique : La procédure de réglage des paramètres (Algorithme 3) utilise ce proxy comme sous-routine interne. Un optimiseur classique recherche les paramètres $(\vec{\gamma}, \vec{\beta})$ qui minimisent la « fonction d'objectif de paramètre homogène » (une estimation de la valeur d'espérance du coût dérivée du proxy). Une fois les paramètres optimaux trouvés pour le proxy, ils sont appliqués directement au circuit QAOA réel.

L'article démontre comment calculer les distributions nécessaires ($N(c'; d, c)$ et probabilités de coût $P(c')$) pour des classes spécifiques de Problèmes de Satisfaction de Contraintes (CSP) avec des clauses tirées aléatoirement, incluant le k-SAT aléatoire, le MaxCut sur des graphes d'Erdős-Rényi, et le Max-k-XOR.

Contributions Clés

• Définition de l'Homogénéité Parfaite et du Proxy : Les auteurs formalisent la condition d'Homogénéité Parfaite et définissent un Proxy Homogène Classique qui produit à la fois des descriptions d'état et des valeurs d'espérance efficacement.
• Mise à l'échelle Polynomiale : La méthode proposée permet le calcul classique des paramètres du proxy en un temps qui croît polynomialement par rapport à la fois au nombre de variables $n$ et à la profondeur $p$, évitant ainsi la croissance exponentielle des ressources associée à la simulation exacte de l'état (statevector).
• Généralisation aux Classes de CSP : L'article fournit des dérivations explicites pour les distributions du proxy pour quatre classes de CSP aléatoires, montrant que le proxy peut décrire une classe entière de problèmes plutôt qu'une instance unique.
• Cadre Heuristique : Les auteurs introduisent un flux de travail complet (Algorithme 3) qui intègre ce proxy dans les boucles d'optimisation de paramètres standards, maintenant la flexibilité dans le choix des schémas de mise à jour des paramètres.

Résultats
Les auteurs ont évalué numériquement l'heuristique sur des problèmes MaxCut sur des graphes aléatoires d'Erdős-Rényi non pondérés ($G(n, p_e)$) :

• Faible Profondeur ($p \leq 3$) : Pour des graphes avec $n=20$, l'heuristique a trouvé des paramètres qui ont produit des ratios d'approximation comparables à ceux obtenus par la stratégie de « transfert de paramètres » (transfert des paramètres optimisés globalement depuis des instances plus petites). La différence de performance n'était pas statistiquement significative, bien que l'heuristique ait montré une performance moyenne légèrement supérieure dans certains cas.
• Haute Profondeur ($p \leq 20$) : Pour des profondeurs allant jusqu'à $p=20$, l'heuristique a réussi à identifier des paramètres produisant des ratios d'approximation augmentant de manière monotone avec la profondeur. En revanche, une stratégie utilisant le transfert de paramètres avec des ressources classiques identiques a échoué à converger.
• Précision du Proxy : L'analyse numérique a montré que le proxy maintient de grands chevauchements avec les simulations de l'état complet (statevector), particulièrement pour les schémas de paramètres à rampe linéaire et dans les régimes où le paramètre $\gamma$ est petit. Les distributions analytiques utilisées dans le proxy se sont révélées fortement corrélées aux moyennes empiriques sur les instances de graphes aléatoires.

Signification et Revendications
L'article affirme que l'Heuristique Homogène offre une voie pratique pour le réglage des paramètres dans des régimes qui sont actuellement intraitables pour les dispositifs NISQ en raison du bruit, et pour les méthodes classiques en raison de la mise à l'échelle exponentielle. En remplaçant l'évaluation coûteuse de la valeur d'espérance par un proxy classique de temps polynomial, la méthode permet l'exploration de circuits QAOA plus profonds (par exemple, $p=20$) là où les stratégies précédentes échouent à converger.

Les auteurs soulignent que, bien que l'heuristique ne garantisse pas des paramètres optimaux pour chaque instance spécifique, elle fournit une stratégie robuste et globale qui est compétitive avec les méthodes établies à faible profondeur et les surpasse à des profondeurs plus élevées. Le travail suggère que l'hypothèse d'Homogénéité Parfaite, bien qu'elle ne soit pas universellement exacte, sert d'approximation suffisamment précise pour guider l'optimisation des paramètres dans de nombreux contextes d'optimisation combinatoire, particulièrement ceux impliquant des contraintes aléatoires. Les auteurs concluent en esquissant des directions futures, telles que l'incorporation d'informations spécifiques à l'instance dans le proxy et l'extension de l'approche à d'autres algorithmes quantiques variationnels comme le VQE (Variational Quantum Eigensolver).