Résumé Technique : Approches Variationnelles Quantiques pour le Problème du Ensemble Indépendant Maximal à l'Échelle Utile

Énoncé du Problème

Le problème de l'Ensemble Indépendant Maximal (MIS - Maximum Independent Set) cherche le plus grand sous-ensemble de sommets dans un graphe non orienté tels qu'aucun des deux sommets ne soit adjacent. Il s'agit d'un problème canonique NP-difficile avec des applications dans l'attribution des fréquences, l'analyse des interactions protéiques et la conception VLSI. Alors que les solveurs classiques exacts (branch-and-bound, programmation entière) peinent sur des instances difficiles dépassant quelques centaines de sommets, l'informatique quantique offre un potentiel heuristique. Cependant, les algorithmes variationnels à portes font face à des défis importants dans l'ère NISQ (Noisy Intermediate-Scale Quantum), notamment des nombres limités de qubits, des temps de cohérence courts et le phénomène de « plateau stérile » (barren plateau) où les gradients s'amenuisent de manière exponentielle.

Un défi structurel spécifique apparaît pour les graphes larges et denses où le MIS constitue une fraction infime du total des sommets (par exemple, 15 sur 180). Dans ces cas, la solution optimale occupe une région exponentiellement petite de l'espace de Hilbert. Les approches standards, initialisant avec une superposition uniforme, assignent une amplitude négligeable au MIS, ce qui pousse souvent les circuits variationnels à converger vers des bassins d'énergie sous-optimaux d'où il est difficile de s'échapper sans changements coordonnés multi-qubits.

Méthodologie

Les auteurs proposent un cadre stratifié combinant prétraitement de circuit, optimisation variationnelle et post-traitement classique pour répondre à ces défis à travers trois instances de référence : 64, 99 et 180 nœuds.

1. Prétraitement et Construction de Circuit

• Réordonnancement des Sommets : Pour minimiser le surcoût des SWAP et améliorer l'efficacité de l'intrication, les auteurs comparent trois stratégies de réordonnancement : le BFS pondéré par le couplage, le Reverse Cuthill-McKee (RCM) et le Réordonnancement Spectral (utilisant le vecteur de Fiedler). Le réordonnancement spectral est adopté car il surpasse systématiquement les autres sur les instances denses en regroupant les sommets structurellement proches, minimisant ainsi la distance d'indice entre les qubits fortement couplés.
• Sparsification Basée sur la Distance : Appliquée spécifiquement aux circuits QAOA, cette technique supprime les interactions à longue portée lors de la construction du circuit (ne conservant que les arêtes où $|i-j| \le k$) tout en évaluant l'énergie avec le Hamiltonien complet. Cela réduit considérablement la profondeur du circuit, rendant les simulations tractables sur des simulateurs de type Matrix Product State (MPS).
• Algorithmes : L'étude compare le Variational Quantum Eigensolver (VQE) utilisant un ansatz EfficientSU2 et l'Algorithme d'Optimisation Approchée Quantique (QAOA). Les optimiseurs incluent COBYLA et la méthode de la Perturbation Stochastique Simultanée (SPSA). L'objectif de la Valeur à Risque Conditionnelle (CVaR) est utilisé pour se concentrer sur la queue de basse énergie de la distribution de mesure.

2. Pipeline de Post-traitement Classique

Un pipeline heuristique de chaînes de bits à deux étapes convertit les mesures quantiques brutes en candidats MIS valides :

• Suppression Guidée par l'Historique : Une Moyenne Mobile Exponentielle (EMA) suit la fréquence des qubits étant dans l'état $|0\rangle$ à travers les chaînes de bits les plus performantes. Cela génère des masques de suppression pour supprimer les sommets sur-sélectionnés (violant l'indépendance) et ajouter des sommets sous-sélectionnés.
• Correction Gloutonne et Extension de Maximalité : Un algorithme glouton à deux passes répare d'abord les ensembles infaisables en supprimant les violations de poids élevé, puis étend l'ensemble vers la maximalité en ajoutant des sommets compatibles par ordre croissant de degré.

3. Initialisation par Superposition Assistée par Ancilla (Instance de 180 Nœuds)

Pour l'instance de 180 nœuds, le VQE standard stagne à une taille de 14 (le MIS connu est de 15). Pour surmonter cela, les auteurs introduisent une nouvelle technique d'initialisation :

• Sélection de Graines (Seeds) : Le post-traitement classique identifie plusieurs ensembles indépendants diversifiés et quasi-optimaux de taille 14.
• Superposition d'Ancillas : Au lieu d'initialiser à partir d'une seule graine ou d'une superposition uniforme, le circuit prépare une superposition quantique uniforme de ces $m$ solutions distinctes de taille 14 en utilisant des qubits ancillas comme registre d'index.
• Ansatz Préservant l'Excitation : L'état évolue sous un ansatz composé de portes de simulation fermionique (fSim) qui conservent le poids de Hamming total (nombre d'excitations). Cela restreint la recherche à l'espace de configuration de taille 14, éliminant le besoin de termes de pénalité et affinant le paysage énergétique pour une optimisation de précision.
• Recherche Parallèle Quantique : Les paramètres variationnels sont optimisés collectivement à travers toutes les branches de graines simultanément. La distribution résultante est ensuite traitée par l'heuristique classique, qui peut étendre les ensembles de taille 14 vers le MIS de taille 15.

Résultats Clés

Instances de Référence (64, 99 et 180 Nœuds)

• Instance de 64 Nœuds : Le VQE avec SPSA et CVaR réussit à récupérer tous les 9 MIS certifiés distincts (taille 10) à travers des exécutions répétées. Le QAOA en récupère moins (0–5 par exécution) et échoue à atteindre la taille 10 avec la Stratégie 2 (poussant tous les ensembles récupérés vers la maximalité), soulignant l'importance de la diversité des solutions.
• Instance de 99 Nœuds : Le VQE récupère jusqu'à 10 MIS distincts (taille 7) par exécution, échantillonnant une fraction significative des 56 solutions certifiées. Le QAOA n'est pas poursuivi en raison des limites de sparsification du simulateur MPS.
• Instance de 180 Nœds : Le VQE standard (Phase 1) converge vers la taille 14 mais ne peut atteindre la taille 15. La Phase 3 assistée par ancilla (VQE préservant l'excitation) découvre avec succès le MIS de taille 15. Les études d'ablation confirment que les heuristiques classiques appliquées à des graines uniques, ou les circuits préservant l'excitation initialisés à partir de graines uniques, échouent à trouver le MIS de taille 15. Seule la superposition quantique multi-graines brise la barrière de l'optimum local.

Validation Matérielle (IBM Quantum ibm_marrakesh)

• VQE : En utilisant des paramètres transférés directement d'une simulation sans bruit (sans ré-optimisation matérielle), le VQE récupère environ 50 % de la diversité du MIS sans bruit avec 40 % du budget de tir (shots). Pour l'instance de 64 nœuds, 3 MIS distincts (taille 10) ont été trouvés ; pour l'instance de 99 nœuds, 5 MIS distincts (taille 7) ont été trouvés.
• QAOA : Sous le même protocole de transfert de paramètres, le QAOA a récupéré zéro ensemble indépendant valide sur le matériel. Les auteurs attribuent cela à l'effet cumulatif d'une bande passante de circuit limitée (nécessitant des chaînes de SWAP profondes), une optimisation classique superficielle et le bruit matériel.

Signification et Revendications

L'article affirme les contributions et significations suivantes :

1. Simulation à l'Échelle Utile : À la connaissance des auteurs, la simulation MPS de 180 qubits représente la plus grande échelle à laquelle les algorithmes variationnels à portes ont résolu le problème du MIS de manière optimale.
2. Percée Méthodologique : La contribution principale est la technique de superposition d'ancilla. Elle fournit un cadre principled pour briser les optima locaux qui piègent tant les heuristiques classiques que les approches variationnelles standards. En initialisant une superposition quantique uniforme sur plusieurs graines classiques quasi-optimales et en évoluant sous un ansatz préservant l'excitation, la méthode réalise une « recherche parallèle hybride quantique-classique ». Cela permet la découverte de solutions (taille 15) inaccessibles aux méthodes à graine unique.
3. Robustesse au Bruit : La validation matérielle démontre que le pipeline d'heuristique de chaînes de bits est robuste aux conditions de bruit réalistes, récupérant une diversité de solutions significative sans ré-optimisation tenant compte du matériel.
4. Revendications Modestes sur l'Avantage Quantique : Les auteurs déclarent explicitement qu'ils ne revendiquent pas d'avantage de calcul quantique pour ces instances spécifiques. Les circuits étudiés sont classiquement simulables efficacement via MPS (dimension de liaison $\chi_{max} = 2$) en raison de leur structure d'intrication faible. La signification réside dans la démonstration que la méthodologie fonctionne et fournit une base pour de futures implémentations matérielles où des ansatze plus profonds et de plus grandes populations de graines pourraient engendrer un véritable avantage quantique.

Ce travail établit que la découverte du MIS dans le cas des 180 nœuds est une conséquence de la recherche parallèle quantique sur plusieurs initialisations quasi-optimales, plutôt que de l'heuristique de post-traitement classique seule. Ce cadre est présenté comme une approche scalable pour les problèmes d'optimisation combinatoire admettant une formulation d'Ising.