An End-to-End Hybrid Quantum--Classical Sampling Workflow for Discrete Markov Random Fields: A Reproducible Case Study

Résumé Technique : Un flux de travail d'échantillonnage hybride quantique-classique de bout en bout pour les champs de Markov discrets

Énoncé du problème
L'échantillonnage des champs de Markov discrets (MRF) est un défi fondamental dans l'inférence probabiliste, la vision par ordinateur et la physique statistique. La difficulté principale réside dans le tirage d'échantillons d'une distribution jointe $P_\theta(x)$, ce qui nécessite une normalisation par une fonction de partition $Z(\theta)$ qui somme sur $2^n$ configurations. Bien que les méthodes classiques de Monte Carlo par chaînes de Markov (MCMC) soient la norme, elles souffrent souvent d'un mélange lent et d'une forte autocorrélation sur les graphes à boucles. À l'inverse, l'inférence variationnelle et la propagation de croyance (belief propagation) font face à des limites d'exactitude ou de convergence. Cette étude examine si l'échantillonnage quantique par encodage d'amplitude offre un avantage pratique par rapport aux méthodes classiques, spécifiquement dans un régime où la distribution complète peut être précalculée classiquement ($O(2^n)$), ce qui exclut les accélérations exponentielles quantiques mais permet une comparaison rigoureuse de l'efficacité de l'échantillonnage et de l'indépendance.

Méthodologie
L'étude emploie une approche à double architecture pour traiter différentes échelles de problèmes ($n$) :

1. Encodage d'amplitude (petit $n$) : Pour $n \in \{8, 10, 12\}$, les auteurs construisent un pipeline où la diagonale de l'Hamiltonien $H_\theta$ est calculée classiquement en temps $O(2^n)$. Les probabilités cibles sont normalisées, et les amplitudes $\alpha_x = \sqrt{P_\theta(x)}$ sont préparées à l'aide du primitif StatePreparation de Qiskit. Cela crée un état quantique $|\psi\rangle = \sum_x \sqrt{P_\theta(x)}|x\rangle$. Les mesures dans la base de calcul produisent des échantillons indépendants et identiquement distribués (i.i.d.). Cette approche sacrifie le potentiel d'accélération exponentielle de la modélisation générative par circuits quantiques (QCGM) complète pour une vérification propre et auditable du processus d'échantillonnage.
2. Circuits Quantiques Variationnels (VQC) (plus grand $n$) : Pour des $n$ plus grands, où l'énumération complète est irréalisable, les auteurs entraînent des ansätze efficaces pour le matériel (hardware-efficient). Ces circuits consistent en $d$ couches de rotations $R_Y$ sur un seul qubit entrelacées avec des portes CNOT d'intrication. Trois stratégies d'intrication ont été testées : linéaire (qubits adjacents), sensible aux cliques (correspondant à la topologie du graphe MRF) et complète (tous vers tous). Les circuits sont entraînés pour minimiser la divergence de Kullback–Leibler (KL) entre la distribution induite et la cible $P_\theta$.
3. Baselines Classiques : Les méthodes quantiques sont comparées à quatre échantillonneurs classiques :
   • Gibbs à site unique (balayage aléatoire).
   • Gibbs par blocs (mise à jour des cliques maximales).
   • Gibbs par blocs ajusté (appartenance aux blocs adaptée).
   • Température parallèle (PT) avec 8 répliques.
   • Inverse-CDF Exacte : Une baseline classique qui utilise la distribution précalculée pour tirer des échantillons i.i.d., servant de comparaison « pommes contre pommes » pour l'encodeur d'amplitude une fois les coûts de pré-traitement amortis.

Contributions Clés
L'article ne revendique pas d'accélération quantique. Ses contributions sont caractérisées comme une étude de benchmarking rigoureux et de résultats négatifs :

1. Caractérisation de l'écart d'ESS : Une quantification de l'écart de la taille d'échantillon effective (ESS) entre l'échantillonnage i.i.d. par encodage d'amplitude et quatre baselines MCMC classiques sur 60 instances (cinq familles de graphes).
2. Amortissement du temps de calcul (Wall-Clock) : Une comparaison équitable du temps de calcul qui inclut explicitement le coût de pré-traitement classique $O(2^n)$ requis par l'encodeur d'amplitude quantique, en comparant avec l'échantillonnage par Inverse-CDF exacte.
3. Plafond d'échelle classique : Une étude de mise à l'échelle multi-essais des états de tenseur matriciel (MPS) jusqu'à $n=40$, établissant un plafond de fidélité classique concret pour les futurs approches variationnelles.
4. Reproductibilité : La publication du code open-source et des artefacts exécutables qui régénèrent tous les tableaux et figures à partir de fichiers de données JSON engagés.

Résultats

• Ratios d'ESS : Sur 60 instances, le ratio de l'ESS quantique sur l'ESS classique a montré une hiérarchie claire. L'échantillonneur quantique a surpassé le Gibbs à site unique avec un facteur moyen de 16,35, le Gibbs par blocs de 7,29, le Gibbs par blocs ajusté de 1,82, et la Température Parallèle de 1,79. Cela indique que si l'échantillonnage quantique conserve un avantage structurel (sortie i.i.d., $\tau \approx 1$), les échantillonneurs MCMC classiques modernes (spécifiquement la Température Parallèle) réduisent considérablement cet écart.
• Performance en temps de calcul (Wall-Clock) : Lorsque le coût de pré-traitement $O(2^n)$ est amorti, l'échantillonneur Inverse-CDF Exacte atteint un taux moyen de 17 683 598 ESS/s, contre 487 706 ESS/s pour l'échantillonneur quantique. Cela représente un avantage de 36× en taux moyen et de 153× en ratios moyens par instance, confirmant l'absence d'avantage en temps de calcul pour le flux de travail quantique dans ce régime.
• VQC vs MPS (Résultat Négatif) : Les VQC peu profonds et efficaces pour le matériel (profondeur 3) ont nettement sous-performé par rapport au MPS à budget égal à toutes les tailles testées ($n=8, 10, 12$). Les fidélités pour les VQC étaient de 0,306, 0,210 et 0,165, contre 0,990, 0,958 et 0,878 pour MPS.
• VQC vs Mean-Field : À $n=8$ et $n=10$, l'approximation Mean-Field a atteint une fidélité de distribution globale plus élevée que le VQC, bien que le VQC ait surpassé les méthodes classiques sur les erreurs marginales de singleton.
• Mise à l'échelle MPS : À $n=40$, un MPS avec une dimension de liaison $\chi=32$ a atteint une fidélité de 0,721 ± 0,059, établissant un benchmark pour les futures approches quantiques.
• Stratégies d'intrication : L'intrication sensible aux cliques n'a apporté aucun avantage de fidélité mesurable par rapport à l'intrication linéaire aux échelles testées.

Signification et Revendications
L'article stipule explicitement qu'il ne revendique pas d'avantage quantique. Sa signification réside dans :

1. Clarification du récit de l'« avantage quantique » : Il démontre que l'avantage apparent de l'échantillonnage quantique dans les MRF est très sensible au choix de la baseline classique. Bien que l'échantillonnage quantique offre une indépendance structurelle, le MCMC classique optimisé (comme la Température Parallèle) réduit presque totalement l'écart d'ESS, et l'échantillonnage exact classique (Inverse-CDF) domine en temps de calcul quand le coût de pré-traitement est pris en compte.
2. Définition du régime de validité : L'encodeur d'amplitude est un outil défendable uniquement lorsque des échantillons quantiques i.i.d. ou une préparation d'état cohérente en aval (ex: estimation d'amplitude) sont strictement requis, ou lorsqu'on ne peut pas énumérer la distribution complète mais qu'aucune baseline classique n'est disponible.
3. Résultats négatifs pour les VQC peu profonds : L'étude fournit des preuves que les ansätze peu profonds et efficaces pour le matériel sont insuffisants pour capturer la structure globale des distributions de MRF très pointues par rapport aux méthodes de réseaux de tenseurs comme MPS.
4. Benchmarking : Elle établit un cadre reproductible et des plafonds numériques spécifiques (ex: MPS à $n=40$) que les futurs algorithmes quantiques devront dépasser pour démontrer une utilité.

Les auteurs concluent que les voies les plus plausibles vers un futur avantage quantique résident dans la simulation d'Hamiltonien QCGM complète, des ansätze variationnels plus profonds ou adaptés au problème, ou des benchmarks sur matériel bruyant à grande échelle, tous identifiés comme des travaux futurs.