Quantum Counting in the Rydberg Blockade

Résumé technique : Comptage quantique dans le blocage de Rydberg

Énoncé du problème
Le comptage du nombre de solutions à des problèmes combinatoires, tels que la satisfaisabilité booléenne (SAT), est une tâche fondamentale en intelligence artificielle, en fiabilité des réseaux et en physique statistique. Cependant, le comptage exact pour les instances difficiles appartient à la classe de complexité #P, qui est considérée comme intraitable pour les ordinateurs classiques. Bien que le comptage approximatif par échantillonnage soit une alternative viable, celui-ci nécessite la capacité d'échantillonner les solutions de manière presque uniforme. Les méthodes classiques basées sur l'échantillonnage peinent souvent à atteindre cette uniformité efficacement. De plus, les approches quantiques existantes, telles que celles basées sur les itérations de Grover, nécessitent des profondeurs de circuit qui croissent exponentiellement avec le nombre de variables, ce qui les rend inaccessibles aux processeurs quantiques actuels à échelle intermédiaire bruyante (NISQ).

Méthodologie : RydCount
Les auteurs proposent RydCount, un algorithme de comptage approximatif basé sur l'échantillonnage, conçu nativement pour les ordinateurs quantiques à atomes neutres (NAQC). L'algorithme cible les formules de 2-satisfaisabilité (2SAT) planaires.

1. Codage physique : L'algorithme associe les variables booléennes à des registres atomiques piégés dans des pinces optiques. Les contraintes 2SAT sont imposées par le blocage de Rydberg. Spécifiquement, le système évolue sous un Hamiltonien de Rydberg où les excitations simultanées d'atomes voisins dans l'état de Rydberg sont énergétiquement prohibées. Cette contrainte physique encode naturellement la formule 2SAT monotone $\phi_G(x) = \bigwedge_{(i,j) \in E} (\neg x_i \lor \neg x_j)$, où le sous-espace de basse énergie correspond à l'espace des solutions de la formule.
2. Protocole d'échantillonnage : La sous-routine centrale, RydSamp, consiste à préparer un état de base computationnelle initial (typiquement $|0\rangle^{\otimes n}$), à appliquer une « trempe » (quench) via une impulsion laser statique pour un temps d'évolution aléatoire $t \in [t_{min}, t_{max}]$, et à mesurer l'état résultant dans la base computationnelle.
3. Mécanisme de rétroaction (Feed-Forward - FF) : Pour améliorer l'uniformité de l'échantillonnage, l'algorithme utilise un protocole de rétroaction. Si une chaîne de bits mesurée est une solution valide, elle est réinjectée comme état initial pour l'itération suivante. L'analyse théorique suggère que pour des états initiaux génériques, la dynamique chaotique de l'Hamiltonien de Rydberg propage l'amplitude de l'état à travers l'espace de Hilbert accessible, conduisant à une distribution presque uniforme sur l'ensemble des solutions après un nombre suffisant d'étapes FF ($k$).
4. Auto-réduction du comptage : L'algorithme suit le cadre de Jerrum-Valiant-Vazirani (JVV). Il fixe de manière itérative les variables à leur état de maximum de vraisemblance en fonction des échantillons collectés, réduisant ainsi la taille du problème à chaque étape. L'estimation finale est le produit des inverses de ces probabilités observées.

Contributions clés et résultats

• Faisabilité théorique : Les auteurs démontrent que la représentation par blocage de Rydberg préserve l'auto-réductibilité requise pour le comptage JVV. Ils montrent que, bien que l'Hamiltonien de Rydberg ne produise pas une distribution parfaitement uniforme en raison d'un blocage imparfait et des queues d'interaction à longue portée, il parvient à un échantillonnage « presque uniforme » ($n\eta \lesssim 1$) pour des instances allant jusqu'à $n \approx 10^4$ variables en un nombre polynomial d'étapes FF.

• Simulations classiques :

  • Grilles 1D et 2D : Les simulations sur des chaînes 1D et des grilles triangulaires 2D montrent que le compte estimé converge vers une valeur située dans un facteur multiplicatif constant de la valeur exacte à mesure que le nombre d'échantillons augmente.
  • Analyse du biais : Les auteurs identifient un biais systématique dans les grilles 2D et les grilles ponctuées causé par les interactions de voisinage immédiat supérieur (next-nearest neighbor), qui pénalisent les états de poids de Hamming élevé. Cela conduit à une sous-estimation de la probabilité que les variables soient dans l'état $|1\rangle$, entraînant une surestimation systématique du compte total. Par conséquent, l'algorithme agit comme une borne supérieure efficace sur le compte exact dans ces scénarios plutôt que comme une estimation précise à un facteur multiplicatif près.
  • Grilles ponctuées : Pour les grilles 2D « ponctuées » aléatoires (où des sites sont supprimés), l'algorithme converge vers un facteur de $1,1$ de la valeur exacte pour de faibles densités de trous. Les auteurs notent que des solveurs classiques comme GANAK présentent une mise à l'échelle exponentielle du temps de calcul pour ces instances, suggérant l'existence d'instances #2SAT classiquement difficiles au sein de cet ensemble de graphes, bien qu'ils ne prétendent pas que RydCount est plus rapide ou supérieur en termes de temps d'exécution.

• Démonstration expérimentale : Les auteurs ont implémenté une variante hybride simplifiée de RydCount sur un NAQC Pasqal Orion Alpha. En raison des limitations matérielles (absence d'adressabilité sélective des atomes), ils n'ont pas pu effectuer la pleine auto-réduction itérative. Au lieu de cela, ils ont :

  1. Utilisé un échantillonnage en une seule étape ($k=1$) à partir de l'état fondamental.
  2. Pré-sélectionné un séparateur de graphe pour décomposer le problème de 81 variables en deux sous-problèmes plus petits.
  3. Résolu les sous-problèmes de manière classique et les a combinés avec le facteur multiplicatif quantique dérivé du séparateur.
  4. Évalué deux chemins de décimation (fixation des variables à 0 ou 1) pour établir des bornes supérieures et inférieures.

  Résultats expérimentaux : Pour une instance de grille planaire à 81 variables, les tirages bruts du matériel ont produit des estimations situées dans un facteur de 5 (pour le chemin $x_c=1$) et de 1,01 (pour le chemin $x_c=0$) de la valeur exacte. La post-sélection des chaînes de bits de solutions valides a amélioré le chemin $x_c=0$ à un facteur $< 1,25$. Les deux chemins ont réussi à encadrer le compte exact.

Signification et perspectives
L'article affirme que RydCount représente une approche viable à court terme pour le comptage approximatif sur les dispositifs NISQ. Sa signification réside dans :

1. Implémentation native : Il utilise la physique naturelle des NAQC (blocage de Rydberg) pour imposer des contraintes, évitant ainsi les circuits profonds requis par les algorithmes quantiques basés sur les portes logiques.
2. Scalabilité : Le protocole est démontré comme fonctionnel pour des tailles de problèmes ($n=81$) qui sont difficiles pour les processeurs quantiques actuels non-recuit et qui approchent les limites des solveurs classiques de pointe pour certains ensembles de graphes spécifiques.
3. Potentiel futur : Les auteurs notent que si les taux d'horloge actuels sont faibles (< 10 Hz), les améliorations futures vers 100 Hz, combinées à la capacité de piéger des milliers d'atomes et de mettre en œuvre une adressabilité sélective (déjà démontrée dans les laboratoires académiques), pourraient positionner RydCount comme une alternative compétitive aux méthodes classiques pour les problèmes #P-difficiles. L'utilisation de chaînes d'atomes pour encoder des graphes bipartites 3-réguliers plans suggère que la méthode pourrait être étendue à des instances #P-complètes.

Les auteurs restent modestes, reconnaissant que la démonstration expérimentale actuelle est une variante hybride simplifiée et que les biais systématiques dus aux interactions à longue portée doivent être atténués (par exemple, via un meilleur blocage de Rydberg ou une meilleure adressabilité) pour obtenir des estimations précises plutôt que de simples bornes.