Approximate sampling from decoded quantum interferometry via Markov chain Monte Carlo methods

Titre : Échantillonnage approximatif à partir de l'interférométrie quantique décodée via des méthodes de Monte Carlo par chaînes de Markov

Énoncé du problème
L'interférométrie quantique décodée (DQI) est un algorithme quantique proposé pour aborder l'optimisation combinatoire approximative, spécifiquement les familles de problèmes max-LINSAT (incluant Max-XORSAT et l'Intersection Polynomiale Optimale, OPI). Bien que la DQI offre de solides garanties de performance théoriques et qu'elle ait fait l'objet de revendications d'une accélération quantique super-polynomiale par rapport aux algorithmes classiques connus dans des régimes de paramètres spécifiques (particulièrement pour l'OPI), sa performance empirique par rapport aux méthodes classiques reste peu explorée. Le problème central abordé dans ce travail est de savoir si les méthodes d'échantillonnage classiques peuvent émuler les capacités d'optimisation de la DQI, remettant ainsi en question ou affinant les revendications d'avantage quantique. Les auteurs étudient la complexité de la DQI en analysant les versions décision, recherche et échantillonnage de ces problèmes d'optimisation, notant que la DQI résout nativement le problème d'échantillonnage, ce qui induit une distribution biaisée vers des solutions à score élevé.

Méthodologie
Les auteurs emploient une double approche combinant caractérisation analytique et simulation numérique à grande échelle :

1. Caractérisation analytique : Les auteurs dérivent un cadre analytique simplifié pour la performance de la DQI. Ils connectent la performance attendue de la DQI aux statistiques binomiales en analysant les moments de la fonction objectif sous la distribution DQI. Cette analyse repose sur les propriétés du code correcteur d'erreurs dual associé à l'instance du problème. Ils identifient également des obstructions théoriques à la preuve de la dureté classique de l'échantillonnage de la distribution DQI, notamment concernant la réduction du problème de recherche au problème de décision et l'applicabilité des réductions de comptage standard.

2. Simulation numérique (MCMC) : Pour tester la performance empirique, les auteurs utilisent des méthodes de Monte Carlo par chaînes de Markov (MCMC), plus précisément l'échantillonnage de Gibbs par blocs, pour échantillonner à partir de la distribution induite par l'état DQI.

   • Distribution cible : Puisque les probabilités de sortie de la DQI sont classiquement calculables efficacement, les auteurs construisent une chaîne de Markov dont la distribution stationnaire correspond à la distribution de sortie de la Doli $P(x) \propto P^2(f(x))$, où $P$ est un polynôme de degré $\ell$ et $f(x)$ est la fonction objectif.
   • Algorithmes : Ils comparent deux stratégies d'échantillonnage : « restart » (exécution de chaînes indépendantes pour chaque nouvel échantillon) et « keep-going » (continuation d'une seule chaîne pour trouver plusieurs échantillons distincts).
   • Benchmarks : Les méthodes sont testées sur deux familles de problèmes :
     • Max-XORSAT : Instances aléatoires creuses avec $p=2$.
     • Intersection Polynomiale Optimale (OPI) : Instances basées sur des codes de Reed-Solomon avec $p > 2$.
   • Mise à l'échelle : Les expériences montent jusqu'à plus de 1000 qubits effectifs pour Max-XORSAT et au-delà de 150 qubits effectifs pour l'OPI. Le « nombre de qubits équivalents » ($n_p = n \lceil \log_2 p \rceil$) est utilisé comme paramètre de mise à l'échelle pour l'OPI afin de permettre une comparaison directe avec les estimations de ressources quantiques.

Principales contributions

• Simplification analytique : Le papier fournit une dérivation inédite des moments de performance de la DQI en utilisant des bases monomiales plutôt que des polynômes symétriques ou de Kravchuk. Cela révèle qu'une condition nécessaire au succès de la DQI (distance élevée du code dual) implique que la version décision du problème est classiquement facile, déplaçant ainsi l'attention de l'analyse de complexité vers les versions recherche et échantillonnage.
• Identification des obstructions : Les auteurs identifient des obstacles spécifiques à la preuve de la dureté classique de l'échantillonnage DQI, notamment la difficulté de réduire le problème de recherche au problème de décision dans le contexte des garanties de performance de la DQI, et la nature structurée de l'ensemble des « bonnes » solutions $S$.
• Évaluation empirique : Ce travail présente la première étude empirique complète d'algorithmes d'échantillonnage classiques émulant la DQI. Il démontre que les techniques MCMC standard peuvent atteindre de manière fiable les ratios d'approximation attendus de la DQI sur une large gamme de tailles de problèmes.

Résultats

• Max-XORSAT : Pour Max-XORSAT, la méthode d'échantillonnage de Gibbs par blocs atteint le seuil de performance de la DQI avec un temps d'exécution qui évolue de manière polynomiale (environ $n^5$) avec le nombre de qubits. Cela indique que pour cette classe de problèmes, l'échantillonnage classique peut égaler efficacement la performance d'optimisation de la DQI.
• Intersection Polynomiale Optimale (OPI) : Pour l'OPI, où la DQI revendique un avantage super-polynomial, le temps d'exécution MCMC évolue de manière exponentielle avec le nombre de qubits ($n_p$). Cependant, la base de cette croissance exponentielle est faible, environ 1,1 (spécifiquement $1,096^{n_p}$).
• Échantillonnage vs Recherche : Le comportement de mise à l'échelle qualitative pour le problème d'échantillonnage reflète celui du problème de recherche. Les auteurs observent que la stratégie « keep-going » est plus efficace pour Max-XORSAT (suggérant des solutions regroupées/clustered), tandis que la stratégie « restart » est plus efficace pour l'OPI (suggérant un manque de regroupement des solutions ou une propriété de gap de recouvrement/overlap gap property).
• Sensibilité au seuil : Lorsqu'on abaisse le seuil de performance pour l'OPI, une transition de phase est observée dans la qualité de l'ajustement de la mise à l'échelle du temps d'exécution : les ajustements de type loi de puissance sont meilleurs pour des seuils plus bas, tandis que les ajustements exponentiels deviennent supérieurs au-dessus d'un seuil d'environ 0,66. Le seuil de la DQI pour l'OPI se situe bien dans le régime exponentiel.

Signification et Revendications
Les auteurs déclarent que leurs conclusions ne réfutent pas les revendications existantes d'un avantage quantique super-polynomial pour la DQI, car le temps d'exécution MCMC classique pour l'OPI présente bien une croissance exponentielle. Cependant, le papier plaide pour une perspective plus nuancée de cet avantage :

1. Petite base exponentielle : La base exponentielle observée de ~1,1 est comparativement petite, suggérant que les algorithmes classiques peuvent rester compétitifs avec la DQI pour une large gamme de tailles d'instances pratiquement pertinentes, ne tombant potentiellement derrière que pour des instances très grandes.
2. Émulation classique : Les résultats démontrent que les algorithmes d'échantillonnage classiques peuvent étroitement égaler la performance d'optimisation de la DQI, remettant en question l'idée que l'avantage quantique est absolu ou facilement accessible pour les tailles de problèmes actuelles.
3. Paysage de complexité : Ce travail clarifie que la complexité de la DQI est profondément liée aux versions recherche et échantillonnage du problème, plutôt qu'à la version décision, et que les outils standards pour prouver la dureté de l'échantillonnage ne s'appliquent pas directement à la DQI.

En conclusion, le papier fournit des preuves empiriques que, bien que la DQI puisse offrir un gain de vitesse théorique, l'avantage quantique pratique est moins flagrant que précédemment suggéré, les méthodes MCMC classiques offrant une alternative viable et efficace pour de nombreuses tâches d'optimisation.