Generative Quantum Search for Combinatorial Optimization: Learning Shallow Quantum Samplers for Classically Refined Solution Subspaces

Résumé Technique : Recherche de Recherche Quantique Générative pour l'Optimisation Combinatoire

Énoncé du Problème
Cette recherche examine si des échantillonneurs quantiques superficiels peuvent surpasser les échantillonneurs classiques dans l'optimisation combinatoire en plaçant une masse de probabilité plus élevée au sein d'un « bassin de récupération classique ». L'étude adapte l'architecture GQE+QSCI (Generative Quantum Eigensolver + Quantum-Selected Configuration Interaction), initialement développée pour la chimie quantique, au domaine de l'optimisation de graphes (spécifiquement le Maximum Weighted Independent Set, MWIS). L'hypothèse centrale est qu'un échantillonneur quantique pourrait générer une distribution de solutions candidates qui, lorsqu'elle est affinée par un algorithme de réparation et d'expansion classique, produit un taux de succès supérieur à celui des échantillonneurs classiques.

Méthodologie
L'auteur propose le cadre GQO+QSS (Generative Quantum Optimization + Quantum-Selected Search), qui suit un pipeline en quatre étapes :

1. Politique Générative : Un modèle d'apprentissage automatique (politique conditionnée par le graphe) génère des programmes de circuits quantiques (par exemple, les paramètres QAOA).
2. Échantillonnage Quantique : Les circuits sont exécutés sur un simulateur ou un QPU (Piast-Q) pour produire des chaînes de bits (solutions candidates).
3. Récupération Classique : Une fonction de réparation spécifique au problème corrige les solutions infaisables, suivie d'une expansion locale (par exemple, un voisinage de $r$-flip) pour créer un sous-espace de recherche restreint.
4. Solveur Restreint : Un solveur classique exact trouve la solution optimale au sein de ce sous-espace restreint.

Formalisation Théorique Clé
Le document formalise la question du « bénéfice quantique » en utilisant la masse du bassin de récupération ($p_r$) :
$$p_r(q_\theta, G) = \Pr_{x \sim q_\theta} [x \in A_r(G)]$$
où $A_r(G)$ est l'ensemble des états qui, après réparation et expansion par $r$-flip, contiennent l'optimum global. La probabilité de succès avec $B$ tirages est $P_{success} = 1 - (1 - p_r)^B$. L'étude postule que la métrique critique n'est pas la taille du sous-espace échantillonné par rapport à l'espace total ($|S_Q|/2^n$), mais la masse de probabilité $p_r$ que l'échantillonneur place dans le bassin récupérable.

Protocole Expérimental

• Jeux de données : 150 instances de MWIS dont les vérités de terrain sont certifiées via CBC + vérification par force brute.
• Lignes de base (Baselines) : Neuf échantillonneurs ont été comparés, incluant l'aléatoire uniforme, le mode glouton (greedy), le recuit simulé (SA), la recherche tabu, la recherche locale à redémarrage multiple, Metropolis, le QAOA avec warm-start, le QAOA oracle (meilleures configurations parmi 50) et une politique classique apprise correspondante.
• Contraintes : Un protocole préenregistré et figé avec un budget fixe de 200 tirages par échantillonneur.
• Matériel : Les expériences comprenaient des simulations et une exécution sur le processeur à ions piégés Piast-Q (20 qubits).

Résultats Clés

1. Dominance Classique : La recherche tabu et le recuit simulé (SA) ont nettement surpassé tous les échantillonneurs quantiques et les politiques classiques apprises sur toutes les tailles de problèmes testées ($n=16$ à $n=28$). La recherche tabu a atteint une masse de bassin de récupération ($p_r$) allant de 0,822 à $n=16$ à 0,944 à $n=18$, avec des valeurs de 0,878 à $n=20$, 0,943 à $n=24$ et 0,901 à $n=28$. Le SA variait de 0,088 à 0,428 sur ces tailles.
2. Sous-performance Quantique : Tous les échantillonneurs quantiques (warm-start QAOA, oracle QAOA et politiques génératives) ont perdu face au SA et à la recherche tabu pour chaque taille de problème sous le protocole équitable préenregistré.
3. L'Artéfact de l'« Oracle » : Les résultats positifs précédents montrant le QAOA surpassant le SA ont été identifiés comme des artéfacts de la sélection de configuration par instance (une borne supérieure « oracle »). Lorsqu'ils sont évalués avec des configurations aléatoires (une méthode déployable), le QAOA oracle atteint $p_r = 0,014$ à $n=28$, bien en dessous du 0,088 du SA.
4. Parité Classique Apprise : Une politique classique apprise (140K paramètres) a obtenu des performances comparables au QAOA oracle ($p_r = 0,005–0,101$ contre $0,014–0,113$), indiquant que le circuit quantique n'offre aucun avantage structurel par rapport à un modèle classique apparié dans ce contexte.
5. Robustesse du Matériel : Les expériences sur Piast-Q ont montré une cohérence de récupération de 93,4 % entre les échantillons du QPU et du simulateur, confirmant la robustesse du matériel mais révélant aucun avantage quantique en termes de qualité d'optimisation.
6. Transition de Récupération : L'étude a cartographié une « transition de récupération » où la récupération classique est suffisante pour $n \le 16$ mais commence à échouer pour $n \ge 20$ avec une expansion de 2-flip. Cependant, même dans ce régime de transition, des lignes de base classiques fortes (SA, Tabu) maintiennent des performances supérieures.

Signification et Revendications
Le document se présente comme une étude de falsification. Sa revendication principale est que, sous une évaluation rigoureuse et préenregistrée avec des lignes de base classiques appariées, les distributions de propositions dérivées de QAOA superficiels ne surpassent pas les modèles de proposition classiques appariés pour capturer les bassins de récupération classique dans le MWIS.

• Aucun Avantage Quantique : L'auteur affirme explicitement l'absence d'avantage quantique pour l'architecture GQO+QSS dans les régimes testés.
• Réfutation des Revendications Précédentes : L'étude attribue les résultats positifs antérieurs à l'effet « oracle » de la sélection de la meilleure configuration par instance, ce qui n'est pas une méthode déployable.
• Correction de Métrique : Le papier soutient que la « fraction du sous-espace » ($|S_Q|/2^n$) est une métrique tautologique sous des budgets de tirages fixes et que la masse du bassin de récupération ($p_r$) est la quantité scientifiquement exacte à mesurer.
• Direction Future : L'auteur suggère que pour que l'échantillonnage quantique apporte de la valeur, il doit systématiquement placer plus de masse dans le bassin de récupération que les fortes lignes de base classiques (comme le SA) dans les régimes où la récupération classique échoue ($n \ge 55$), un défi que les circuits superficiels actuels n'ont pas relevé.

L'étude conclut que, bien que l'architecture GQO+QSS soit un cadre valide pour l'optimisation hybride, les échantillonneurs quantiques superficiels actuels n'offrent pas d'avantage structurel par rapport aux fortes méthodes de recherche stochastique classiques pour la tâche spécifique de capture du bassin de récupération du MWIS.