General circuit mapping algorithm for neutral atom quantum computers

Résumé Technique : Algorithme de Cartographie de Circuits Généraux pour les Ordinateurs Quantiques à Atomes Neutres

Énoncé du Problème
Les ordinateurs quantiques à atomes neutres (NAQC) offrent une plateforme évolutive caractérisée par de longs temps de cohérence, des arrangements de qubits flexibles et des capacités natives de portes multi-qubits (ex: CCZ, Ck-phase). Cependant, l'exécution de circuits quantiques sur le matériel NAQC nécessite de déplacer physiquement les atomes via des pinces optiques pour rapprocher les qubits afin de réaliser des portes d'intrication (blocage de Rydberg). Ce processus de « re-cartographie » introduit un overhead significatif :

1. Perte de Fidélité : Chaque transfert comporte un risque de perte d'atome ou de changement d'état. Bien que les taux de succès des transferts uniques soient élevés (>0,99), les erreurs cumulées deviennent prohibitives pour les circuits comportant de nombreux qubits ou transferts.
2. Overhead Temporel : Les transferts consomment du temps, réduisant la fenêtre de calcul globale.
3. Défi d'Optimisation : Les compilateurs existants (ex: ZAC, MQT) reposent souvent sur des heuristiques telles que le recuit simulé ou des algorithmes gloutons. Bien qu'ils s'améliorent par rapport aux méthodes antérieures, ils manquent de bornes inférieures théoriques explicites pour le nombre de transferts requis et ne fournissent pas de formulation générale optimisant simultanément la distance totale parcourue et les opérations de transfert parallèle (PTO) à travers les architectures monolithiques (M-arch) et zonées (Z-arch).

Méthodologie
Les auteurs proposent un cadre mathématique unifié et indépendant du circuit, basé sur l'optimisation combinatoire de la théorie des graphes. La méthodologie se déroule en quatre étapes distinctes :

1. Représentation par Graphe (Fondement Théorique) :

   • Le circuit quantique est décomposé en un graphe orienté acyclique (DAG) où les sommets représentent des « instructions » (groupes de portes agissant sur des qubits spécifiques au sein d'une étape) et les arêtes représentent les transitions entre les étapes.
   • Le problème de la minimisation des transferts entre les étapes est modélisé comme la recherche d'une appariement de poids maximal dans des sous-graphes bipartis reliant les étapes consécutives.
   • Théorème 3.1 & 3.2 : Les auteurs prouvent que le nombre minimum de transferts pour les architectures M-arch et Z-arch peut être dérivé en sommant les minimums locaux de ces appariements. Pour la Z-arch, le graphe est décomposé en sous-graphes spécifiques à chaque zone, avec des transferts obligatoires entre les zones.

2. Codage par Bâtonnets (Réduction du Problème) :

   • Pour optimiser le placement physique des atomes, les auteurs introduisent un « codage par bâtonnets » (stick encoding). Cette représentation abstrait le problème de cartographie en regroupant les qubits qui restent statiques entre les étapes en « bâtonnets ».
   • Au sein d'un bâtonnet, les qubits forment des « sous-bâtonnets ». Le codage capture les degrés de liberté (DoF) intrinsèques : la coordonnée spatiale 2D du bâtonnet sur la grille atomique et une variable booléenne indiquant si les sous-bâtonnets au sein d'un bâtonnet multi-qubit sont inversés.
   • Ce codage découple la décision de quels qubits déplacer (déterminée par l'appariement de graphe) du placement de ces qubits, permettant une optimisation efficace de la distance parcourue.

3. Algorithme Génétique (Optimisation) :

   • Un algorithme génétique (GA) est employé pour résoudre le programme entier non linéaire résultant.
   • Le GA fonctionne sans croisement, s'appuyant plutôt sur des modifications locales aléatoires (déplacement de bâtonnets ou permutation de sous-bâtonnets) pour explorer l'espace de configuration.
   • La fonction objectif est flexible, permettant à l'utilisateur de prioriser la minimisation de la distance totale parcourue, la maximisation du nombre de transferts parallèles, ou une combinaison pondérée des deux.

4. Construction des Opérations de Transfert Parallèle (PTO) :

   • Une étape de post-traitement construit la séquence de transferts parallèles.
   • L'algorithme analyse le digraphe de transfert pour détecter des cycles. Si un cycle existe (les atomes se bloquant mutuellement sur leurs trajectoires), un « espace de stationnement » (un emplacement atomique vide) est utilisé pour briser le cycle, nécessitant un transfert supplémentaire.
   • Un algorithme glouton planifie ensuite les transferts, garantissant la compatibilité avec les contraintes matérielles (ex: limitations des déflecteurs acousto-optiques) afin de maximiser le parallélisme tout en évitant les collisions.

Contributions Clés

• Cadre Mathématique Général : L'article fournit la première formulation de type théorie des graphes déterminant la borne inférieure théorique pour le nombre de transferts d'atomes requis pour tout circuit quantique sur les plateformes NAQC, applicable aux architectures monolithiques et zonées.
• Codage Novateur : L'introduction du « codage par bâtonnets » réduit efficacement la complexité du problème de cartographie en isolant les degrés de liberté liés au placement spatial et à l'ordre interne des qubits.
• Contrôle des Compromis : Le cadre permet explicitement un arbitrage entre la minimisation de la distance totale parcourue par les atomes (réduisant le temps) et la maximisation des opérations de transfert parallèle (réduisant la latence).
• Garanties Théoriques : Contrairement aux approches heuristiques précédentes, ce travail fournit des bornes inférieures prouvables pour les comptes de transferts (Théorème 3.1/3.2) et démontre que la méthode proposée atteint systématiquement ces bornes.

Résultats
Les auteurs ont testé leur algorithme par rapport à des cartographes de pointe, spécifiquement ZAC (un cartographe pour architecture zonée sensible à la réutilisation) et MQT (Munich Quantum Toolkit).

• Nombre de Transferts : La méthode proposée atteint systématiquement le nombre minimum théorique de transferts (à 0–2 transferts près en raison des exigences de rupture de cycle) sur tous les circuits testés. En revanche, ZAC dépasse souvent ce minimum théorique.
• Distance et Parallélisme :
  • Lors de l'optimisation de la distance, la méthode proposée réduit considérablement la distance totale parcourue par rapport à ZAC (ex: une amélioration de ~333 % pour le circuit QFT).
  • Lors de l'optimisation des transferts parallèles, la méthode surpasse souvent ZAC et MQT en nombre de PTO, particulièrement pour les circuits complexes.
• Flexibilité : Les résultats soulignent un compromis : optimiser la distance ne minimise pas toujours les PTO, et inversement. Le GA permet aux praticiens d'ajuster la fonction objectif en fonction de paramètres matériels spécifiques (ex: rapport entre la vitesse de mouvement des pinces et la vitesse de commutation des pièges).

Signification et Revendications
L'article affirme fournir à la fois une base théorique et un outil pratique pour une compilation de circuits quantiques efficace et consciente de l'architecture.

• Théorique : Il établit que le nombre minimal de transferts peut être déterminé via l'appariement de graphes, offrant un point de référence pour le développement futur des compilateurs.
• Pratique : Il offre un outil d'optimisation flexible permettant de générer des cartographies adaptées au matériel. En réduisant les erreurs induites par le mouvement et en exploitant mieux le parallélisme des transferts d'atomes, la méthode améliore directement l'efficacité d'exécution sur les dispositifs NAQC.
• Évolutivité : L'approche est décrite comme générale et évolutive, capable de gérer divers ensembles de portes (y compris les portes multi-qubits) et adaptable aux futures architectures NAQC avec des zones supplémentaires (ex: pour les portes CCZ).

Les auteurs maintiennent un ton modeste concernant le temps d'exécution, notant que le choix optimal entre la minimisation de la distance ou des PTO dépend de paramètres matériels spécifiques (ex: vitesses de commutation SLM/AOD vs vitesses de mouvement des pinces) qui varient selon les plateformes. Ils recommandent d'exécuter le cartographe avec différents paramètres pour sélectionner la meilleure solution pour un dispositif donné.