QuPort: Topology-, Port-, and Congestion-Aware Compilation for Modular Multi-QPU Quantum Systems

Cet article présente QuPort, un cadre de compilation pour les systèmes modulaires multi-QPU qui utilise un modèle à trois niveaux et l'algorithme TPCCAP pour optimiser conjointement la cartographie des qubits, l'allocation des ports et la congestion des interconnexions, réduisant ainsi le trafic inter-QPU et les goulots d'étranglement de communication.

L'essentiel

Imaginez que vous essayez d'organiser une fête massive et complexe où les invités sont des « bits quantiques » (qubits) et les pièces où ils se retrouvent sont de petits ordinateurs quantiques distincts appelés QPUs.

Autrefois, tous les invités se trouvaient dans une seule et immense salle de bal. Le travail de l'« organisateur de la fête » (le compilateur) consistait simplement à s'assurer que les invités qui devaient se parler se tenaient côte à côte. S'ils ne l'étaient pas, l'organisateur devait déplacer les gens (un processus appelé « routage ») jusqu'à ce qu'ils puissent discuter.

Mais maintenant, nous construisons des ordinateurs quantiques modulaires. Au lieu d'une seule immense salle de bal, nous avons un bâtiment avec de nombreuses petites pièces séparées (les QPUs). Certaines pièces sont reliées par des couloirs, mais ces couloirs sont étroits et coûteux à utiliser.

Cet article présente un nouvel organisateur de fête nommé QuPort. Voici comment il fonctionne, en utilisant des analogies simples :

1. Les Trois Cartes

Pour planifier la fête, QuPort examine trois cartes différentes simultanément :

• La Liste des Invités (Graphe Logique) : Qui doit parler à qui, et combien ? (Certains invités sont les meilleurs amis et doivent parler constamment ; d'autres se disent juste « bonjour » une fois).
• Le Plan de la Pièce (Carte Physique) : Dans chaque petite pièce, quelles chaises sont côte à côte ?
• Le Plan du Bâtiment (Graphe d'Interconnexion) : Comment les pièces sont-elles reliées ? Y a-t-il des couloirs directs, ou devez-vous traverser trois autres pièces pour atteindre la suivante ?

2. Le Grand Problème : L'« Entrée » Goulot d'Étranglement

Si vous placez deux meilleurs amis dans des pièces différentes, ils doivent crier à travers le couloir. Mais il y a deux gros problèmes :

1. Trop de cris : Si trop de paires d'amis sont dans des pièces différentes, les couloirs se bouchent.
2. Trop peu de portes : Chaque pièce n'a que quelques « portes de communication » (ports). Si vous placez 100 invités dans une pièce mais que seulement 5 d'entre eux doivent crier vers l'extérieur, vous ne pouvez en laisser sortir que 5 à la fois. Les autres restent bloqués.

3. La Solution : La Stratégie TPCCAP

QuPort utilise une stratégie spéciale appelée TPCCAP pour décider qui va dans quelle pièce. Il tente d'équilibrer trois choses :

• Distance : Il tente de garder les meilleurs amis dans la même pièce. S'ils doivent être dans des pièces différentes, il les place dans des pièces voisines (couloirs courts).
• Pression sur les Portes : Il s'assure qu'aucune pièce n'est forcée d'utiliser plus de « portes » qu'elle n'en possède réellement. Il ne mettra pas 10 invités criards dans une pièce n'ayant que 5 portes.
• Trafic dans les Couloirs : Il répartit les cris de manière à ce qu'aucun couloir unique ne soit encombré par trop de trafic.

4. Comment QuPort Planifie la Fête (Les Algorithmes)

QuPort ne se contente pas de deviner ; il utilise quelques astuces ingénieuses pour trouver la meilleure disposition :

• Regroupement par Arêtes Lourdes : Il examine d'abord les amitiés les plus fortes et verrouille ces paires dans la même pièce avant de s'occuper du reste.
• Gourmand Équilibré : Il remplit les pièces un invité à la fois, choisissant toujours la pièce qui a le plus de sens pour cet invité sans rendre la pièce trop bondée.
• Recuit Simulé : C'est comme une phase de « deuxième réflexion ». Après le plan initial, il tente des petits changements aléatoires (comme échanger deux invités) pour voir si la fête se déroule mieux. Si un changement améliore les choses, il le conserve. S'il empire les choses, il pourrait tout de même le conserver un moment pour éviter de rester coincé dans un plan « assez bon » mais pas « parfait ».

5. La Liste des « Événements à Distance »

Une fois les invités assignés aux pièces, QuPort crée une liste d'instructions spéciale.

• Instructions Locales : « L'invité A et l'invité B sont dans la Pièce 1. Ils peuvent parler normalement. »
• Événements à Distance : « L'invité A est dans la Pièce 1 et l'invité B est dans la Pièce 2. Ils doivent se parler. »

QuPort ne détermine pas comment ils parlent à travers le couloir (qu'ils utilisent des lasers, des fils ou de la magie). Il marque simplement l'endroit où cette conversation doit avoir lieu et indique aux ingénieurs matériels : « Vous devez construire un protocole ici pour gérer ce cri spécifique. »

6. Le Calendrier

Enfin, QuPort estime combien de temps durera la fête. Il compte combien de « cris » peuvent se produire simultanément sans boucher les couloirs ni épuiser les portes. Il donne une estimation approximative du temps total (makespan) basée sur ces règles abstraites.

Ce Que QuPort N'EST PAS

L'article est très clair sur ce que cet outil n'est pas :

• Ce n'est pas une machine physique.
• Il ne connaît pas la physique spécifique de votre ordinateur quantique (comme la durée de vie d'une batterie ou la quantité d'erreurs qu'un laser produit).
• Il ne réalise pas réellement les « cris » à travers les pièces.

En résumé : QuPort est un contrôleur de trafic intelligent pour un ordinateur quantique modulaire. Il détermine la meilleure façon de répartir le travail entre différents petits ordinateurs afin qu'ils ne restent pas bloqués en attendant les uns les autres, tout en veillant à ce qu'ils n'essaient pas d'utiliser plus de portes ou de couloirs qu'il n'en existe réellement. Il prépare les instructions afin que les ingénieurs matériels puissent ensuite déterminer la meilleure façon de construire la technologie de « cris ».

Résumé technique

Résumé technique : QuPort - Compilation consciente de la topologie, des ports et de la congestion pour les systèmes quantiques modulaires multi-QPU

1. Énoncé du problème

Les architectures quantiques modulaires, qui connectent plusieurs unités de traitement quantique (QPU) via des interconnexions, présentent un défi de compilation unique, distinct des dispositifs monolithiques. Dans la compilation sur un seul dispositif, la contrainte principale est la carte de couplage locale ; les interactions non locales sont résolues par l'insertion de portes SWAP. Cependant, dans les systèmes modulaires, les interactions entre qubits situés sur différents QPU ne sont pas de simples portes locales « plus longues », mais dépendent de ressources de communication rares : la topologie des interconnexions, les ports de communication et la capacité des liens.

Les compilateurs existants traitent souvent la communication inter-QPU comme une préoccupation secondaire ou la dissimulent au sein d'un routage standard. Cette approche est insuffisante pour les systèmes modulaires car une affectation acceptable sur un seul graphe de couplage peut échouer dans un contexte modulaire si elle :

1. Génère un trafic inter-QPU excessif.
2. Concentre le trafic sur un petit nombre de liens d'interconnexion (provoquant une congestion).
3. Attribue trop de qubits frontaliers (qubits interagissant avec d'autres QPU) à un QPU disposant de ports de communication insuffisants.

L'article répond au besoin d'un cadre de compilation qui raisonne explicitement et simultanément sur la connectivité locale du dispositif et la communication inter-QPU, avant la sélection d'un protocole spécifique de porte distante physique (par exemple, liens photoniques, génération d'intrication).

2. Méthodologie

QuPort est un cadre de compilation basé sur Python, construit sur Qiskit. Il introduit un modèle système à trois niveaux et un algorithme de partitionnement spécifique pour optimiser l'utilisation des ressources.

2.1 Modèle système

Le cadre abstrait le problème de compilation en trois graphes distincts :

1. Graphe d'interaction logique ($G_L$) : Un graphe non orienté pondéré où les nœuds sont des qubits logiques et les poids des arêtes représentent la fréquence ou l'importance temporelle des interactions à deux qubits.
2. Carte de couplage physique : Un graphe orienté représentant la connectivité au sein de chaque QPU individuel (par exemple, grille, anneau, clique).
3. Graphe d'interconnexion des QPU ($G_Q$) : Un graphe non orienté représentant la topologie reliant les QPU (par exemple, maillage, anneau, Clos, arbre gras). Ce graphe est utilisé pour calculer les distances de saut et les charges des liens.

Le système suppose $N$ QPU, chacun disposant de $C$ qubits de calcul et de $P$ qubits de communication. Une partition logique-vers-QPU ($\pi$) doit respecter la contrainte de capacité ($C+P$) par QPU.

2.2 L'objectif TPCCAP

Le cœur de QuPort est la fonction objectif TPCCAP (Partitionnement conscient de la topologie, des ports et de la congestion), $J(\pi)$, qui minimise une somme pondérée de trois termes de coût :

1. Distance de coupe pondérée : $\sum w_{ij} \cdot d(\pi(i), \pi(j))$. Cela pénalise les interactions entre qubits affectés à des QPU éloignés dans le graphe d'interconnexion, où $d$ est la distance du plus court chemin.
2. Dépassement des ports de communication : $\sum \max(0, b_q - P)^2$. Cela pénalise les QPU où le nombre de qubits frontaliers ($b_q$) dépasse le nombre de ports de communication disponibles ($P$).
3. Congestion de la charge routée des liens : $\sum L_e^2$. Cela pénalise la charge au carré sur les arêtes d'interconnexion ($e$), décourageant la concentration du trafic sur des liens spécifiques.

2.3 Algorithmes

QuPort implémente un pipeline d'heuristiques pour résoudre le problème de partitionnement et de disposition :

• Regroupement par arêtes lourdes : Fusionne les paires logiques à poids élevé en clusters tant que la taille du cluster ne dépasse pas la capacité du QPU.
• Partitionnement glouton équilibré : Attribue les qubits logiques un par un en fonction du degré pondéré, équilibrant la charge entre les QPU tout en récompensant le placement à proximité des voisins déjà affectés.
• Recherche locale TPCCAP : Affine la partition initiale en déplaçant des qubits pour réduire l'objectif $J(\pi)$ tout en maintenant les contraintes de capacité.
• TPCCAP-SA (Recuit simulé) : Ajoute une étape de raffinement stochastique pour échapper aux minima locaux en acceptant occasionnellement des mouvements qui augmentent la fonction objectif.
• Disposition consciente des ports de communication : Après le partitionnement, sélectionne des qubits logiques spécifiques pour occuper les ports de communication en fonction de leur « score externe » (poids total des interactions avec d'autres QPU).
• Construction de programme distribué : En mode distribué, le cadre extrait les opérations à deux qubits inter-QPU en tant qu'événements distants explicites et insère des barrières de synchronisation, tout en routant les opérations locales uniquement au sein de leurs cartes de couplage de QPU respectives.

2.4 Ordonnancement et estimation des coûts

QuPort inclut un estimateur conscient de la topologie qui approxime le temps d'exécution (makespan) en utilisant des paramètres de coût abstraits :

• Coûts locaux : Temps d'exécution des portes pour les opérations à un qubit, à deux qubits et SWAP.
• Coûts distants : Un modèle combinant le coût de génération d'intrication ($\tau_E$), le coût aller-retour classique ($\tau_C$) et la surcharge distante ($\tau_R$).
• Ordonnancement : Les opérations distantes sont regroupées en « tours » en fonction des ports de communication disponibles et des capacités des liens, en respectant la topologie des interconnexions.

3. Contributions clés

1. Abstraction explicite à trois niveaux : L'article propose une abstraction au niveau du compilateur qui sépare le graphe d'interaction logique, la carte de couplage physique et le graphe d'interconnexion des QPU. Cette séparation permet l'optimisation de coûts spécifiques au modulaire (distance, ports, congestion) qui sont invisibles pour les compilateurs monolithiques standard.
2. L'objectif TPCCAP : Une fonction objectif novatrice qui optimise conjointement la distance des QPU, la rareté des ports de communication et la congestion des liens, plutôt que de traiter ces éléments comme des préoccupations séparées ou secondaires.
3. Chemin de compilation distribué : Un mécanisme qui produit une représentation intermédiaire où les circuits locaux et les événements distants sont explicitement séparés. Cela permet au compilateur de générer des ordonnancements conscients du modulaire sans s'engager dans une implémentation matérielle spécifique des portes distantes.
4. Cadre open-source : L'implémentation de ces algorithmes en Python/Qiskit, fournissant un environnement reproductible pour l'étude des stratégies de compilation modulaire.

4. Résultats et validation

L'article se concentre sur la structure algorithmique et la correction du cadre plutôt que sur la présentation de résultats de temps d'exécution matériel calibrés.

• Correction : Les auteurs fournissent des preuves formelles (Propositions 1 et 2) démontrant que leurs algorithmes de partitionnement (arêtes lourdes, glouton, TPCCAP, TPCCAP-SA) satisfont strictement les contraintes de capacité par QPU et que leurs routines de routage multi-chemin conservent le poids du trafic.
• Validation : Le cadre applique des vérifications de validation sur les entrées de partition, la construction de la disposition et les matrices de trafic pour garantir des valeurs finies, non négatives et symétriques.
• Portée des résultats : L'article ne prétend pas surpasser des protocoles matériels spécifiques ni fournir des taux d'erreur calibrés. Il démontre plutôt que le cadre génère avec succès des partitions valides et des programmes distribués respectant les contraintes abstraites définies.

5. Importance et affirmations

L'article positionne QuPort comme une abstraction au niveau du compilateur plutôt que comme une implémentation matérielle. Son importance réside dans :

• Découplage de la compilation et des protocoles matériels : En séparant le partitionnement logique et l'extraction d'événements distants de la réalisation physique des portes distantes, QuPort permet aux chercheurs d'étudier la structure algorithmique de la compilation modulaire avant qu'une technologie d'interconnexion spécifique (par exemple, photonique contre micro-ondes) ne soit finalisée.
• Mappage conscient des ressources : Il met en évidence que la compilation modulaire nécessite un passage de la minimisation des SWAPs à la minimisation de la « distance de coupe », du « dépassement de port » et de la « congestion des liens ».
• Modestie des affirmations : Les auteurs déclarent explicitement que le cadre ne prétend pas fournir de temps d'exécution matériel calibré, ni n'implémente un protocole physique de porte distante. Les « événements distants » sont des représentations intermédiaires indiquant où un backend doit fournir un protocole. L'estimateur d'ordonnancement est décrit comme un « modèle glouton basé sur les couches », et non comme un ordonnanceur de contrôle réseau vérifié.

En résumé, QuPort fournit une approche structurée et guidée par des heuristiques du problème complexe d'allocation de ressources inhérent au calcul quantique modulaire, offrant un outil pour explorer les compromis entre topologie, disponibilité des ports et congestion de manière indépendante de la plateforme.