dSABRE: A SABRE-Style Router for Multi-Core Distributed Quantum Computers

L'article présente dSABRE, un nouveau routeur pour les ordinateurs quantiques distribués multi-cœurs qui minimise la consommation d'EPR en priorisant la résolution des portes intra-cœur et en utilisant un mécanisme de notation de téléportation conscient de la capacité, réalisant ainsi des réductions significatives de l'utilisation des ressources par rapport aux méthodes existantes les plus avancées.

L'essentiel

Imaginez que vous essayez d'organiser une immense fête dansante à haut risque, mais que le lieu est divisé en plusieurs salles distinctes (appelées cœurs). Les danseurs sont des qubits (bits quantiques), et la musique est un circuit quantique (un ensemble d'instructions).

Pour que la danse fonctionne, des paires de danseurs doivent parfois se tenir la main et tourner ensemble. S'ils sont dans la même salle, ils peuvent simplement se rapprocher facilement. Mais s'ils sont dans des salles différentes, ils ne peuvent pas traverser les murs. Ils doivent utiliser un service spécial, coûteux et lent de « téléportation » pour passer d'une salle à l'autre. Ce service consomme une ressource limitée appelée paire EPR (pensez-y comme à un précieux « ticket magique »).

Le problème est le suivant : Comment déplacer les danseurs afin qu'ils puissent danser ensemble tout en utilisant le moins possible de tickets magiques ?

C'est le problème que DSABRE résout. Voici comment l'article l'explique en termes simples :

1. Le problème avec les méthodes précédentes

Avant DSABRE, d'autres routeurs (comme TELESABRE) agissaient comme des agents de police qui ne réagissaient qu'aux problèmes.

• Si une salle devenait trop bondée de danseurs, les anciens routeurs attendaient qu'un embouteillage se produise.
• Une fois bloqués, ils tentaient de forcer un danseur à sortir, mais cela brûlait souvent des tickets magiques supplémentaires ou provoquait l'arrêt total de la fête (un « blocage »).
• Ils examinaient également les instructions de danse dans un ordre désordonné et aléatoire, ce qui rendait difficile de prédire qui devait bouger ensuite.

2. La solution DSABRE : Un gestionnaire plus intelligent et proactif

DSABRE est un nouveau « routeur » (un gestionnaire de trafic) qui utilise une stratégie plus intelligente. Il dispose de trois astuces principales pour économiser les tickets magiques :

A. La « fiche de notation à cinq points » (Meilleure prise de décision)

Lorsque DSABRE décide de déplacer un danseur vers une nouvelle salle, il ne se contente pas de regarder « à quel point » le partenaire est proche. Il utilise une fiche de notation à cinq termes :

1. Coût de mise en scène : Combien de pas le danseur doit-il faire à l'intérieur de sa salle actuelle pour atteindre la porte ?
2. Pénalité de capacité : C'est le point crucial. Si une salle de destination est déjà remplie de danseurs, DSABRE lui attribue une énorme « mauvaise note ». Il refuse d'y envoyer des danseurs, empêchant ainsi la salle de devenir un embouteillage.
3. Gain de saut : Il récompense les déplacements qui rapprochent le danseur de sa salle de destination finale, même s'il n'y est pas encore.
4. Gain immédiat : À quel point ce déplacement rapproche-t-il le danseur de son partenaire maintenant ?
5. Anticipation : Il jette un coup d'œil quelques étapes dans le futur pour voir si ce déplacement aide pour les danses à venir.

Analogie : Imaginez que vous déplacez des meubles. Les anciens routeurs poussaient simplement un canapé dans la pièce suivante parce qu'elle était « proche », même si cette pièce était déjà pleine de boîtes. DSABRE vérifie d'abord si la pièce est pleine et dit : « Non, cette pièce est trop bondée ; mettons le canapé dans le couloir à la place. »

B. L'« évacuation proactive » (Dégager l'embouteillage avant qu'il ne se produise)

C'est l'arme secrète de DSABRE.

• Ancienne méthode : Attendre qu'une salle soit pleine à 100 %, puis paniquer et essayer de faire sortir les gens.
• Méthode DSABRE : Il maintient une « liste de demandes ». S'il constate que la Salle A est sur le point d'être inondée de danseurs pour une danse à venir, mais que la Salle A est déjà presque pleine, il déplace proactivement certains danseurs inactifs (ceux qui ne dansent pas en ce moment) hors de la Salle A avant que l'afflux ne commence.
• Résultat : Lorsque l'afflux arrive, il y a de la place. Pas d'embouteillages, pas de tickets magiques gaspillés.

C. La carte « couche par couche » (Meilleure planification)

Lorsque DSABRE regarde en avant pour voir quelles danses arrivent, il ne se contente pas de parcourir la liste au hasard. Il construit une carte couche par couche, en respectant l'ordre de la danse.

• Analogie : Imaginez que vous lisez une recette. Un ancien routeur pourrait lire les ingrédients du dessert avant la soupe. DSABRE lit la recette dans le bon ordre, s'assurant de savoir exactement quels ingrédients (danseurs) sont nécessaires ensuite, afin de ne pas perdre de temps à déplacer des choses qui ne sont pas encore nécessaires.

3. Les résultats : Une fête beaucoup plus efficace

Les auteurs ont testé DSABRE sur de nombreuses « fêtes » (circuits quantiques) différentes de diverses tailles (25, 36 et 64 danseurs).

• Le résultat : DSABRE a utilisé 41 % à 44 % de tickets magiques (paires EPR) en moins que la meilleure méthode précédente (TELESABRE).
• Évolutivité : Lorsqu'ils l'ont testé sur une immense fête avec jusqu'à 360 danseurs, DSABRE a toujours fonctionné parfaitement, tandis que l'ancienne méthode restait souvent bloquée et abandonnait.

Résumé

En bref, DSABRE est une manière plus intelligente d'organiser des ordinateurs quantiques composés de nombreuses petites puces connectées entre elles. Au lieu d'attendre que des embouteillages se produisent, il :

1. Vérifie la capacité avant d'envoyer des danseurs dans des salles bondées.
2. Déplace les danseurs inactifs à l'avance pour faire de la place.
3. Planifie les déplacements dans un ordre logique, étape par étape.

Cela économise les précieux « tickets magiques » (paires EPR) nécessaires pour connecter les puces, rendant l'ordinateur quantique plus efficace.

Résumé technique

Résumé technique : DSABRE – Un routeur de style SABRE pour les ordinateurs quantiques distribués multi-cœurs

Énoncé du problème
La voie vers l'informatique quantique tolérante aux fautes nécessite une mise à l'échelle au-delà des puces monolithiques uniques vers des ordinateurs quantiques distribués (DQC), où plusieurs petites unités de traitement quantique (QPU ou « cœurs ») sont interconnectées via des liens photoniques ou micro-ondes. L'exécution de circuits sur les DQC implique un pipeline de compilation comprenant l'allocation de qubits, la sélection de primitives de communication et le routage/ordonnancement. L'objectif dominant dans ce contexte est la minimisation de la consommation de paires EPR (paires intriquées), car la génération de paires EPR est lente, bruyante et limitée en débit par rapport aux opérations de portes locales.

Bien que les routeurs de l'état de l'art comme TELESABRE utilisent des heuristiques de style SABRE pour router les circuits à travers les cœurs, ils gèrent la congestion de manière défensive. TELESABRE décourage l'atterrissage dans des cœurs saturés via des pénalités et tente de se remettre des blocages en abandonnant les informations de regard en avant. Cependant, sur des instances denses ou de grande taille, cette approche réactive consomme souvent un nombre excessif de paires EPR ou échoue totalement à converger. Le défi central abordé par cet article est l'absence de gestion proactive de la congestion et l'inefficacité des mécanismes de regard en avant existants dans les environnements inter-cœurs.

Méthodologie : DSABRE
DSABRE est un routeur de style SABRE conçu pour les processeurs multi-cœurs. Il opère dans une disposition initiale fixe (générée par Qiskit SabreLayout) et se concentre sur l'étape de routage : l'ordonnancement des SWAP intra-cœurs et des téléportations inter-cœurs (spécifiquement teledata, le déplacement de qubits logiques entre les cœurs). L'algorithme exécute une boucle pilotée par un regard en avant avec quatre phases par itération :

1. Drain : Exécuter les portes 1Q et les portes 2Q intra-cœurs adjacentes.
2. Partition : Séparer les portes restantes de la couche frontale en intra-cœurs ($F_{intra}$) et inter-cœurs ($F_{inter}$).
3. Évaluation et Application :
   • Si $F_{intra}$ n'est pas vide, sélectionner le meilleur SWAP intra-cœur.
   • Si $F_{intra}$ est vide, évaluer les candidats de téléportation inter-cœur et les candidats de soulagement proactif de la congestion, en appliquant le mouvement ayant le score le plus bas.
4. Point de contrôle/Annulation : Sauvegarder l'état en cas de progression ; si le système est bloqué pendant un nombre défini d'itérations, restaurer un point de contrôle et forcer la progression pour échapper au blocage.

Contributions et mécanismes clés
L'article identifie trois mécanismes spécifiques qui améliorent les performances de DSABRE par rapport à l'état de l'art :

1. Score de téléportation centré sur les portes à cinq termes :
   Contrairement à l'estimation d'énergie globale de TELESABRE, DSABRE utilise un score local centré sur les portes ($s$) pour les mouvements inter-cœurs. Le score combine cinq termes :

   • Coût de mise en scène ($d_{prep}$) : SWAP intra-cœurs requis pour déplacer un qubit vers un port de communication.
   • Pénalité de capacité ($c_{cap}$) : Un terme qui pénalise explicitement la téléportation vers des cœurs à faible capacité libre, empêchant le routeur de saturer les cœurs déjà saturés.
   • Gain de saut ($g_{hop}$) : Une récompense directionnelle pour les mouvements réduisant la distance inter-cœur vers la cible, compensant lorsque le port d'atterrissage est loin de la position de mise en scène optimale.
   • Gain de couche frontale ($\Delta_F$) : Réduction immédiate de la distance physique pour la porte actuelle.
   • Regard en avant ($\tilde{\Delta}_E$) : Une somme pondérée par une décroissance des réductions de distance futures.

2. Soulagement proactif de la congestion :
   DSABRE maintient un vecteur de demande explicite sur les cœurs. Avant qu'un cœur ne devienne saturé (forte demande, faible capacité), le routeur génère activement des « candidats de soulagement » pour téléporter les qubits inactifs loin des cœurs à forte demande. Ces mouvements sont évalués dans la même fonction objectif (avec $\Delta_F=0$) et rivalisent directement avec les mouvements pilotés par les portes. Cela empêche la « cascade d'éviction » qui mène au blocage dans les systèmes réactifs.

3. Ensemble étendu inter-cœur par couches BFS :
   Le SABRE standard construit des ensembles de regard en avant dans l'ordre topologique, ce qui peut mélanger des fils non liés. TELESABRE utilise des couches BFS mais pondère les portes de manière arbitraire. DSABRE construit l'ensemble de regard en avant inter-cœur couche par couche en utilisant la recherche en largeur (BFS) sur le DAG. Crucialement, au sein de chaque couche, les portes partageant un fil avec la couche frontale sont émises en premier. La décroissance du regard en avant est appliquée en fonction de la profondeur BFS ($\gamma^{dep(g)}$), garantissant que les successeurs à court terme dominent le signal et que l'ensemble respecte les dépendances du DAG plus strictement que l'ordre topologique.

Résultats expérimentaux
Les auteurs ont évalué DSABRE par rapport à TELESABRE et pytket-dqc (un routeur basé sur la téléportation de portes) sur 18 circuits MQT-Bench avec 25, 36 et 64 qubits logiques, en utilisant des architectures de grilles de grilles (B-grid et H-grid).

• Réduction des paires EPR : DSABRE réduit la consommation géométrique moyenne de paires EPR de 41–44 % par rapport à TELESABRE et de 16–68 % par rapport à pytket-dqc.
• Évolutivité : Sur un circuit aléatoire de 64 qubits, TELESABRE a échoué à converger pour toutes les graines, tandis que DSABRE a terminé le routage. Une analyse d'évolutivité sur des circuits de transformée de Fourier quantique (QFT) allant jusqu'à 360 qubits a confirmé que DSABRE maintient son avantage à mesure que la taille du circuit et l'architecture augmentent.
• Études d'ablation :
  • Le retrait de la pénalité de capacité a augmenté la consommation géométrique moyenne de paires EPR d'environ 59 % (25q) et 59 % (64q), l'identifiant comme le composant le plus critique.
  • La désactivation du soulagement proactif de la congestion a augmenté la consommation de paires EPR de 23,4 % sur la suite 64q, les circuits denses (AE, QFT) voyant une augmentation de plus de 100 %.
  • Le remplacement de l'ensemble étendu par couches BFS par un ordre topologique a augmenté la consommation de paires EPR de 3 à 11 %, les gains augmentant pour les circuits plus grands.
• Sensibilité aux coûts : À mesure que le coût relatif de la téléportation ($c_{tele}$) augmente (simulant le matériel de lien photonique), l'écart de performance entre DSABRE et TELESABRE s'élargit, DSABRE économisant jusqu'à environ 39 % de paires EPR supplémentaires à des ratios de coûts élevés.

Importance et affirmations
L'article affirme que le routage distribué bénéficie moins de formules complexes de notation par candidat et davantage de la garantie que les signaux de regard en avant et les contraintes de capacité architecturale entrent dans la même étape de notation. En intégrant un soulagement proactif de la congestion et un score conscient de la capacité, DSABRE évite les blocages et la consommation excessive de paires EPR qui affectent les routeurs défensifs et réactifs.

Les auteurs positionnent DSABRE comme complémentaire aux méthodes d'allocation statique (comme la partition d'hypergraphes) et aux ordonnanceurs conscients du temps. Ils notent que bien que DSABRE n'utilise actuellement que teledata (téléportation d'état), il est conçu comme un moteur de routage robuste pouvant être combiné avec d'autres primitives ou des passes d'exécution par rafales dans des travaux futurs. Les résultats suggèrent qu'une gestion explicite de la capacité est un composant nécessaire pour la mise à l'échelle de la compilation quantique distribuée.