Scaling Qubit Mapping and Routing With Position Graph Abstraction and Memoization

Cet article présente un cadre de compilation pour les architectures QCCD à ions piégés qui exploite une abstraction de graphe de position et des techniques de mémoïsation pour accélérer considérablement la recherche heuristique SABRE pour la cartographie et le routage des qubits en éliminant les calculs redondants tout en préservant la qualité des décisions.

L'essentiel

Imaginez que vous essayez d'organiser une compétition de danse massive et à haut risque dans un couloir étroit et bondé. Les danseurs sont des qubits (les unités de base des ordinateurs quantiques), et l'objectif est de faire se rencontrer des paires spécifiques de danseurs dans la même petite pièce (un « piège ») pour exécuter un duo spécial (une porte quantique).

Cependant, il existe des règles strictes :

1. Le couloir est bondé : Vous ne pouvez pas simplement téléporter les danseurs ; ils doivent physiquement traverser le couloir.
2. Pas de double réservation : Seule un certain nombre de danseurs peuvent tenir dans une pièce à la fois.
3. Embouteillages : Si un danseur doit passer devant un autre danseur qui est immobile, le chemin est bloqué. Vous devez déterminer comment déplacer le danseur immobile hors du chemin en premier.

C'est le défi de la Compilation Quantique pour un type spécifique d'ordinateur quantique appelé QCCD à ions piégés. L'article que vous avez fourni décrit un nouveau « système de contrôle du trafic » qui rend l'organisation de cette danse beaucoup plus rapide et plus efficace.

Voici une analyse de ce que les auteurs ont fait, en utilisant des analogies simples :

1. L'Ancienne Carte vs le Nouveau « Graphique de Position »

Le Problème : Auparavant, les programmes informatiques utilisaient une carte simple appelée « Graphique de Couplage ». Cette carte était comme un diagramme de métro qui ne montrait que quelles stations étaient connectées. C'était idéal pour les ordinateurs où vous échangez simplement deux éléments (comme échanger des places), mais cela échouait pour ces ordinateurs à ions où vous devez physiquement déplacer des ions à travers un labyrinthe complexe de couloirs et de pièces.

La Solution : Les auteurs ont introduit le Graphique de Position.

• Analogie : Imaginez l'ancienne carte comme un dessin de ligne de métro. Le nouveau Graphique de Position est un plan architectural complet en 3D du bâtiment. Il ne montre pas seulement quelles pièces sont connectées ; il montre chaque carreau du sol, chaque couloir, chaque porte, et exactement combien de temps il faut pour marcher d'un endroit à un autre.
• Pourquoi c'est important : Cela permet à l'ordinateur de comprendre les contraintes physiques réelles, comme « Vous ne pouvez pas traverser ce mur » ou « Cette pièce est trop petite pour deux personnes ».

2. Le Problème du « Agent de Circulation » (Congestion)

Le Problème : Lorsque l'ordinateur essaie de déplacer un danseur (ion) vers une pièce, il trouve souvent le chemin bloqué par un autre danseur. L'ancien logiciel s'arrêtait, regardait la carte, calculait un nouveau chemin et réessayait. Si le chemin était à nouveau bloqué, il recalculait à nouveau. C'était comme un GPS qui recalculait l'itinéraire entier depuis zéro à chaque fois que vous rencontriez un feu rouge. C'était incroyablement lent.

La Solution : Les auteurs ont créé LightSHAW (une version « Légère » de leur système précédent).

• Analogie : Imaginez un agent de circulation qui garde un carnet de notes (un cache).
  • Mémoïsation : Au lieu de recalculer la distance du Point A au Point B à chaque fois, l'agent l'écrit une fois. Si la même situation se reproduit, il consulte simplement la note.
  • Le « Profil de Blocage » : Le système se souvient que « Si vous essayez d'aller du Couloir 1 à la Pièce 5, vous devez toujours passer par la Porte 3 ». Il pré-calcule la « pénalité » pour cette porte étant bloquée.
  • Le Résultat : Lorsqu'un embouteillage se produit, le système ne panique pas et ne recalculé pas tout. Il vérifie rapidement ses notes : « Ah, je connais cet embouteillage. Je sais exactement comment le dégager. » Cela rend le processus beaucoup plus rapide.

3. Le « Filtre Intelligent » (Élagage)

Le Problème : Lorsqu'il décide dans quelle pièce un groupe de danseurs devrait aller, l'ordinateur vérifiait auparavant chaque pièce possible dans le bâtiment, effectuant un calcul complet pour chacune.

• Analogie : C'est comme essayer de trouver le meilleur restaurant d'une ville en entrant dans chacun d'eux, en commandant un repas, en le goûtant, puis en décidant.

La Solution : Ils ont ajouté une étape d'Élagage.

• Analogie : Avant d'entrer dans un restaurant, le système consulte un « aperçu du menu » (un score de borne inférieure). Si l'aperçu indique : « Cet endroit est définitivement trop cher », le système l'ignore immédiatement sans jamais mettre les pieds à l'intérieur. Il ne fait le contrôle complet et coûteux que sur les quelques restaurants qui semblent prometteurs. Cela économise une quantité massive de temps.

4. La Grande Surprise : Cela Fonctionne aussi pour les Systèmes Simples

L'Affirmation : Habituellement, lorsque vous rendez une carte plus détaillée (comme passer d'un plan de métro à un plan 3D), l'ordinateur devient plus lent car il doit traiter plus de données.

• Le Résultat : Les auteurs ont testé leur nouveau « Graphique de Position » sur des systèmes simples (ordinateurs supraconducteurs) qui n'ont pas besoin du plan 3D complexe. Ils ont constaté que le nouveau système était aussi rapide que l'ancien système simple.
• Analogie : C'est comme passer d'une carte papier à une application GPS. Vous pourriez penser que le GPS est plus lent car il a plus de données, mais ils l'ont optimisé si bien qu'il fonctionne aussi vite que la carte papier pour les trajets simples, tout en étant toujours capable de gérer des détours complexes lorsque nécessaire.

Résumé des Résultats

L'article affirme qu'en utilisant ce nouveau « Graphique de Position » et les astuces de mémoire « LightSHAW » :

1. Vitesse : Ils peuvent compiler (organiser) des circuits quantiques pour de grands ordinateurs à ions complexes beaucoup plus rapidement qu'auparavant.
2. Évolutivité : À mesure que le nombre de danseurs (qubits) augmente, le temps nécessaire pour les organiser croît beaucoup plus lentement qu'auparavant.
3. Fiabilité : Le système peut gérer des bâtiments « plus serrés » (pièces plus bondées) où d'autres systèmes échouent complètement.
4. Polyvalence : Ce système unique peut désormais gérer à la fois les ordinateurs simples de « permutation » et les ordinateurs complexes de « navette » sans ralentir.

En bref, ils ont construit un système de contrôle du trafic plus intelligent et plus rapide qui se souvient des embouteillages passés et saute les mauvais itinéraires, permettant aux ordinateurs quantiques d'exécuter des danses complexes sans rester bloqués dans les embouteillages.

Résumé technique

Résumé technique : Mise à l'échelle de la cartographie et du routage de qubits avec l'abstraction de graphe de position et la mémorisation

Énoncé du problème

La cartographie et le routage évolutifs des qubits restent des goulots d'étranglement critiques dans la compilation quantique, en particulier pour les architectures de dispositifs à couplage de charge quantique à ions piégés (TI-QCCD). Contrairement aux systèmes supraconducteurs où le routage est modélisé par des opérations SWAP sur un graphe de couplage statique, le TI-QCCD nécessite le déplacement physique des ions à travers des segments et des jonctions. Ce processus est contraint par la légalité des mouvements, les limites de capacité des pièges et la congestion (lorsque des positions intermédiaires sont occupées).

Les méthodes heuristiques existantes, telles que SABRE, reposent sur des abstractions comme les graphes de couplage qui sont insuffisantes pour le TI-QCCD car elles ne peuvent pas exprimer les contraintes complexes du transport physique, de l'occupation intermédiaire et du blocage de chemin. Bien qu'un travail antérieur ait introduit l'abstraction de graphe de position pour unifier les emplacements exécutables, les chemins de déplacement et les contraintes de routage, sa première implémentation a souffert de problèmes de mise à l'échelle sévères. Par exemple, la compilation d'un circuit de 128 qubits sur un dispositif de 180 ions pouvait prendre une journée en raison de calculs redondants lors de la recherche heuristique et de la résolution de la congestion.

Méthodologie

L'article propose un cadre de compilation qui améliore l'abstraction de graphe de position avec des stratégies de mise en cache et de mémorisation pour éliminer les calculs redondants sans altérer les décisions de routage.

1. Abstraction de graphe de position

Le cadre utilise le graphe de position ($G_p$), un graphe étiqueté où :

• Les sommets représentent des emplacements physiques occupables (pièges, régions de transport intermédiaires).
• Les arêtes représentent des transitions valides (échanges au sein d'un piège, fusion/séparation entre piège et transport, ou déplacement dans le transport).
• Les étiquettes distinguent les types d'opérations (échange, fusion/séparation, déplacement).
  Cette abstraction généralise le graphe de couplage (utilisé pour les systèmes supraconducteurs) pour prendre en charge la topologie plus riche du TI-QCCD.

2. Mise en cache au niveau de l'architecture

Pour réduire la surcharge, les auteurs pré-calculent et mettent en cache des quantités dépendantes de l'architecture qui restent statiques pendant une exécution de compilation :

• Chemins les plus courts entre toutes les paires et matrices de distance.
• Sous-graphes exécutables dérivés des étiquettes d'arêtes.
• Profils de blocage de chemin : Pour tout déplacement source-cible, une liste mise en cache des positions intermédiaires pouvant causer un blocage, ainsi que des pénalités fixes pour les résoudre.

3. LightSHAW : Résolution de congestion mémorisée

La contribution principale est LightSHAW, une variante mise en cache de l'heuristique SHAW (SHuttling-AWare). SHAW résout la congestion de manière récursive lorsqu'un ion en mouvement est bloqué par une position occupée. LightSHAW optimise cela via une cache à deux niveaux :

• Cache d'ensemble de notation locale : Met en cache l'ensemble des positions voisines à inspecter pour un mouvement de déblocage candidat donné, évitant ainsi une traversal répétée du graphe pour définir le voisinage de recherche.
• Mémorisation de la congestion basée sur une clé de configuration : Mémorise le score de congestion basé sur une « signature d'occupation locale » ($\sigma$). La clé est $(p, t, b, d, \sigma)$, où $p$ est la position candidate, $t$ est la cible, $b$ est le blocage, $d$ est la profondeur de recherche et $\sigma$ représente l'occupation de l'ensemble de notation local. Cela permet au système de réutiliser les scores pour des motifs de congestion locaux répétés sans re-balayer l'ensemble du dispositif.

4. Élagage de la sélection de piège

Pour optimiser la sélection des pièges cibles pour les portes multi-qubits, les auteurs mettent en œuvre une stratégie d'élagage par borne inférieure. Ils calculent une borne inférieure optimiste sur le coût de routage pour chaque piège (en ignorant la congestion et les exigences de créneaux distincts). Les pièges sont évalués par ordre croissant de cette borne ; le score exact s'arrête dès que la borne inférieure du candidat suivant dépasse le meilleur score exact trouvé jusqu'à présent.

5. Validation sur les architectures supraconductrices

Pour s'assurer que le graphe de position n'impose pas de surcharge inutile sur des architectures plus simples, les auteurs ont instancié LightSABRE (une variante de SABRE) en utilisant à la fois un backend de graphe de couplage traditionnel et un backend de graphe de position. Les deux implémentations ont été configurées pour prendre des décisions de routage identiques, isolant ainsi le coût de l'abstraction elle-même.

Contributions clés

1. Suppression des calculs redondants : Identification et mise en cache des chemins de DÉPLACEMENT les plus courts, des distances de temps de parcours et des informations de chemin liées au blocage dans SHAW.
2. Algorithme LightSHAW : Introduction d'une procédure de résolution de congestion mémorisée qui réutilise les informations dépendantes de l'architecture (chemins de déplacement, régions de déblocage locales) et les scores d'occupation locale, réduisant considérablement le travail répété lors du déblocage récursif des blocages.
3. Analyse de la surcharge d'abstraction : Démonstration que le graphe de position peut remplacer le graphe de couplage pour le routage LightSABRE avec une surcharge d'exécution négligeable, prouvant que des modèles architecturaux plus riches ne compromettent pas intrinsèquement la vitesse de compilation.
4. Cadre open-source : Fourniture d'une implémentation prenant en charge les flux de travail supraconducteurs et TI-QCCD, facilitant l'expérimentation sur des architectures quantiques hétérogènes.

Résultats expérimentaux

Les auteurs ont évalué le cadre en utilisant des benchmarks incluant des circuits QAOA, QFT et de simulation hamiltonienne (TFIM, TFXY) allant de 16 à 512 qubits.

• Mise à l'échelle du temps de compilation : LightSHAW surpasse nettement le SHAW original et le simulateur QCCDSim de l'état de l'art en termes de mise à l'échelle.
  • SHAW : Mise à l'échelle en $O(x^{3.91})$.
  • QCCDSim : Mise à l'échelle en $O(x^{3.04})$.
  • LightSHAW : Mise à l'échelle en $O(x^{1.72})$.
  • Bien que LightSHAW ait une surcharge plus élevée pour les très petits circuits par rapport à QCCDSim, il égale ou dépasse les performances de QCCDSim sur les circuits plus grands (par exemple, architectures de 180 ions) et se met à l'échelle de manière beaucoup plus favorable.
• Temps d'opération (Qualité) : LightSHAW produit des ordonnancements avec un temps d'opération total (exécution de porte + déplacement) significativement plus faible que QCCDSim. Par exemple, sur un circuit QAOA de 512 qubits, LightSHAW a atteint un ratio de temps d'opération de 0,171 par rapport à QCCDSim, indiquant une réduction d'environ 6 fois du temps d'exécution.
• Robustesse : Dans des scénarios stricts de contraintes de ressources (forte utilisation d'ions par piège), QCCDSim a souvent échoué à produire des compilations valides (notées 'X' dans les résultats), tandis que LightSHAW a terminé avec succès toutes les instances.
• Compatibilité supraconductrice : Lorsqu'il est appliqué au routage supraconducteur (LightSABRE), le backend de graphe de position correspond au temps d'exécution du backend de graphe de couplage traditionnel, confirmant que l'abstraction n'introduit aucune pénalité significative pour les architectures plus simples.

Importance

L'article soutient que l'abstraction de graphe de position fournit une voie pratique et efficace vers une cartographie et un routage évolutifs des qubits à travers des architectures quantiques hétérogènes. En combinant une représentation consciente de l'architecture avec une évaluation heuristique mémorisée, le cadre résout le goulot d'étranglement de la mise à l'échelle de la compilation TI-QCCD sans sacrifier les performances sur les systèmes supraconducteurs. Les résultats suggèrent que l'infrastructure de compilateur peut dépasser les modèles d'adjacence minimaux pour prendre en charge des contraintes physiques complexes (comme le déplacement) tout en maintenant l'efficacité requise pour la compilation quantique à grande échelle. Le travail établit qu'une représentation unifiée peut servir à la fois les architectures basées sur SWAP et celles basées sur le déplacement, permettant à un cadre unique de gérer des contraintes matérielles diverses.