⚛️ quantum physics

Efficient Circuit Transpilation of Commuting Gates on 2D Grids

Cet article introduit un schéma de transpilation adaptatif pour les circuits de portes commutatives sur des grilles 2D qui alterne entre des séquences de SWAP dépendantes du problème et des mises à jour de la disposition des qubits, réduisant de manière significative la profondeur du circuit et le nombre de portes pour améliorer les performances de QAOA sur les problèmes de Max Cut et de Maximum Independent Set.

Auteurs originaux : Sabina Drăgoi, Daniel J. Egger

Publié 2026-07-14

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Sabina Drăgoi, Daniel J. Egger

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez de résoudre un puzzle géant et désordonné sur une table, mais avec un piège : vous ne pouvez déplacer les pièces que si elles sont juste à côté les unes des autres. Si deux pièces que vous devez connecter se trouvent aux deux extrémités opposées de la table, vous devez remuer toute la table, en échangeant les voisines jusqu'à ce qu'elles finissent par se toucher. C'est exactement le casse-tête auquel les ordinateurs quantiques sont confrontés lors de l'exécution d'algorithmes d'optimisation complexes comme le QAOA.

Le problème est que la « table » (le matériel quantique) est souvent disposée sous forme de grille, comme un damier. Mais les « pièces du puzzle » (le problème mathématique) n'ont souvent besoin de communiquer qu'avec quelques voisins spécifiques, pas avec tout le monde. L'ancienne méthode pour résoudre cela consistait à ignorer les connexions supplémentaires de la grille et à faire comme si la table n'était qu'une seule longue ligne. On déplaçait les pièces d'avant en arrière le long de cette ligne, en échangeant les voisins encore et encore jusqu'à ce qu'elles puissent interagir. Cela fonctionnait, mais c'était comme faire un détour sinueux de 16 kilomètres pour parcourir un champ d'un kilomètre et demi.

La découverte principale : le « mélange intelligent »
Dans cet article, les auteurs proposent une façon beaucoup plus intelligente de mélanger les pièces. Au lieu de forcer tout le monde dans une seule ligne, ils ont inventé une stratégie « gourmande » (greedy) qui examine le puzzle spécifique que vous essayez de résoudre et construit un plan de mélange sur mesure.

Imaginez cela comme un contrôleur de trafic à une intersection très fréquentée. L'ancienne méthode (la « stratégie linéaire ») forçait chaque voiture à rouler en file indienne, même si une rue latérale était ouverte. La nouvelle méthode regarde la carte, voit qu'une voiture n'a besoin de faire que deux pâtés de maisons vers l'est, et dit : « Hé, tu peux simplement prendre la rue latérale ! » Elle construit une séquence d'échanges qui emprunte le chemin le plus court pour les connexions spécifiques requises.

Ce qu'ils ont écarté
Les auteurs soutiennent explicitement l'idée qu'un plan de mélange unique et prédéterminé n'est pas la meilleure approche. Ils démontrent qu'utiliser un modèle d'échange fixe (comme la stratégie de la « ligne » standard) est souvent sous-optimal, surtout lorsque le problème ne nécessite pas que chaque pièce communique avec toutes les autres. Ils montrent également que l'utilisation d'un contrôleur de trafic standard (comme le transpileur Qiskit) sur une disposition en grille produit des circuits beaucoup plus profonds et désordonnés que leur approche personnalisée. Ils ne se contentent pas de le suggérer ; ils l'ont mesuré.

Les résultats : des chemins plus courts, de meilleures réponses
L'équipe a testé ce mélange « gourmand » sur deux types de puzzles : trouver la meilleure façon de diviser un groupe d'amis en deux équipes (Maximum Cut) et trouver le plus grand groupe d'amis qui ne se connaissent pas (Maximum Independent Set).

Ils ont effectué des simulations sur des graphes allant jusqu'à 90 nœuds (pièces). Voici ce qu'ils ont trouvé :

Moins d'étapes : Leur mélange personnalisé a réduit le nombre de mouvements d'« échange » (swap) d'environ la moitié par rapport à l'ancienne méthode basée sur la ligne.
Moins d'erreurs : Comme le circuit est plus court, il y a moins d'endroits où les erreurs peuvent s'immiscer. Dans leurs simulations, cela leur a permis de gérer des problèmes allant jusqu'à 80 qubits (les pièces du puzzle) qui étaient auparavant trop bruyants pour être exécutés efficacement.
De meilleurs scores : Lorsqu'ils ont réellement exécuté ces circuits sur du matériel quantique IBM, les résultats ont été impressionnants. Pour le problème de la « division des équipes », leur méthode a amélioré la qualité de la réponse jusqu'à 6,6 %. Pour le problème de « la recherche du groupe », l'amélioration était encore plus élevée, atteignant 9,3 %.

À quel point sont-ils sûrs d'eux ?
Les auteurs sont très confiants dans leurs chiffres, mais ils prennent soin de distinguer ce qu'ils ont simulé de ce qu'ils ont mesuré.

Simulations : La réduction massive de la profondeur du circuit et du nombre de portes (jusqu'à un facteur deux) provient de l'exécution de milliers de simulations sur des ordinateurs classiques. Ces simulations montrent que la nouvelle méthode passe beaucoup mieux à l'échelle à mesure que le problème s'agrandit, croissant avec la racine carrée de la taille plutôt qu'avec la taille elle-même.
Matériel réel : Les améliorations du « ratio d'approximation » (le score de la solution) ont été mesurées sur de véritables dispositifs quantiques IBM. Ils ont mené ces expériences sur des graphes allant jusqu'à 80 nœuds. Les résultats ont systématiquement montré que leur méthode gourmande surpassait la méthode linéaire standard, même sans utiliser de techniques sophistiquées de correction d'erreurs.

L'essentiel
Cet article suggère que si vous voulez tirer le meilleur parti des ordinateurs quantiques bruyants d'aujourd'hui, vous ne devez pas simplement forcer le problème à prendre une forme qui s'adapte au matériel. Au contraire, vous devez adapter les mouvements du matériel pour qu'ils correspondent au problème. En utilisant une approche « gourmande » qui adapte le mélange aux connexions spécifiques nécessaires, ils ont réussi à extraire plus de performance des machines existantes, nous permettant potentiellement de résoudre des puzzles plus grands et plus complexes que ce que nous pouvions faire auparavant. Ce n'est pas une baguette magique qui résout tout instantanément, mais c'est un moyen très efficace de faire travailler nos outils beaucoup plus dur et plus intelligemment.

Résumé technique : Transpilation efficace de circuits de portes commutatives sur des grilles 2D

Énoncé du problème

Les problèmes d'optimisation combinatoire, tels que le Max-Cut (MC) et l'Ensemble Indépendant Maximum (MIS), sont centraux dans de nombreuses applications mais sont souvent NP-complets. L'Algorithme d'Optimisation Approchée Quantique (QAOA) offre une approche quantique de ces problèmes en les mappant sur des Hamiltoniens. Cependant, la mise en œuvre pratique sur des ordinateurs quantiques numériques se heurte à des obstacles importants dus à la connectivité limitée du matériel.

L'Hamiltonien du problème $H_C$ induit généralement des interactions entre de nombreuses paires de qubits. Sur un matériel à connectivité restreinte (par exemple, des grilles 2D), ces interactions non adjacentes doivent être réalisées à l'aide de portes SWAP pour acheminer les qubits vers des positions adjacentes. Ce processus de routage augmente la profondeur du circuit et l'erreur accumulée, ce qui peut souvent annuler les bénéfices des algorithmes quantiques. Alors que les méthodes de transpilation standard (comme celles de Qiskit) utilisent des mappages initiaux aléatoires et un routage fixe, elles produisent souvent des circuits sous-optimaux, particulièrement pour les graphes d'interaction creux. De plus, les réseaux de SWAP prédéterminés conçus pour des graphes totalement connectés sont inefficaces pour les Hamiltoniens de coût creux.

Méthodologie

Les auteurs proposent un schéma de transpilation spécifiquement conçu pour les circuits composés de blocs de portes à deux qubits commutatives (typiques du QAOA) sur un matériel de réseau à deux dimensions (2D). La méthodologie centrale consiste à alterner entre la construction de séquences de couches de SWAP dépendantes du problème et la mise à jour du placement des qubits.

Le document introduit et compare plusieurs stratégies :

Stratégie Linéaire ( $S_{line}, C_{line}^{grid}$ ) : La référence de pointe où la grille 2D est traitée comme une ligne 1D. Les couches de SWAP alternent entre les arêtes paires et impaires de la ligne la plus longue de la grille.
Stratégie Hybride ( $S_{line}, C_{grid}$ ) : Une modification de la stratégie linéaire qui applique le routage de SWAP basé sur une ligne, mais exploite les arêtes inutilisées de la grille 2D pour appliquer directement les portes $R_{ZZ}$ (interactions) lorsque cela est possible, sans modifier le réseau de SWAP sous-jacent.
Stratégie de Grille ( $S_{grid}, C_{grid}$ ) : Une stratégie utilisant un ensemble de base adapté de couches de SWAP ( $B_{grid}$ ) qui alterne les échanges horizontaux et verticaux pour exploiter pleinement la connectivité 2D.
Stratégie Gloutonne Dépendante du Problème ( $S_{greedy}, C_{grid}$ ) : La contribution principale des auteurs. Cette méthode emploie un algorithme de recherche gloutonne pour adapter la séquence de SWAP et le mappage initial des qubits au Hamiltonien de coût spécifique de l'instance du problème.
- Boucle Interne : Utilise une recherche en profondeur (DFS) pour explorer un arbre de configurations de qubits atteignables. Elle recherche le chemin le plus court de couches de SWAP permettant d'implémenter toutes les interactions requises. Pour gérer la complexité, la recherche est limitée à une profondeur maximale $k_{max}$ avant de sélectionner la meilleure séquence partielle et de continuer.
- Boucle Externe : Met à jour de manière itérative le mappage initial des qubits ( $\pi_0$ ) à l'aide d'un solveur de mappage basé sur la satisfaction (SAT). Si la longueur de la séquence de SWAP actuelle dépasse une longueur de référence, l'algorithme réinitialise la recherche avec un nouveau mappage initial afin de potentiellement trouver une séquence plus courte.
- Ensemble de Base : La recherche utilise un ensemble de base étendu ( $B_{extended}^{grid}$ ) incluant des couches de SWAP supplémentaires au-delà de la base de grille standard pour échanger l'overhead de recherche contre une réduction de la profondeur du circuit.

Contributions Clés

Transpilation Dépendante du Problème : Le document introduit un algorithme glouton qui construit dynamiquement des stratégies de SWAP et des mappages initiaux adaptés au graphe d'interaction spécifique du problème d'optimisation, plutôt que de s'appuyer sur des réseaux fixes et agnostiques au problème.
Référence Hybride : La proposition d'une stratégie hybride qui utilise les arêtes de la grille 2D pour les interactions tout en maintenant un squelette de SWAP linéaire, servant de référence intermédiaire.
Analyse de Scalabilité : Démonstration théorique et empirique que les stratégies basées sur la grille, particulièrement l'approche gloutonne, atteignent une amélioration asymptotique de l'ordre de $O(\sqrt{n})$ dans les métriques de complexité de circuit (couches de SWAP, profondeur, nombre de portes) par rapport aux stratégies linéaires, alors que les stratégies linéaires suivent une échelle en $O(n)$ .
Validation Matérielle : Exécution expérimentale de circuits QAOA sur le matériel à réseau rectangulaire d'IBM pour des problèmes allant jusqu'à 80 qubits, validant les résultats de simulation.

Résultats

Les auteurs ont testé leur approche sur des instances de MC sur des graphes Réguliers Aléatoires (RR) (degré $d=3$ ) et des instances de MIS sur des graphes d'Erdős–Rényi (ER) (probabilité d'arête $q=0,08$ ).

Complexité du Circuit : Comparée aux méthodes standards (incluant la stratégie linéaire et le transpiler SABRE de Qiskit), la stratégie glutonne a réduit la profondeur du circuit et le nombre de portes à deux qubits d'un facteur d'environ deux pour les graphes creux.
- Pour les graphes RR, le nombre de couches de SWAP, la profondeur et les portes CZ évoluaient en $n$ , $n$ , et $n^2$ pour les stratégies linéaires, tandis que la stratégie glutonne maintenait des constantes plus faibles et un meilleur comportement de mise à l'échelle.
- Pour les graphes ER, la stratégie glutonne a nettement surpassé les stratégies linéaires, avec un nombre de portes CZ évoluant en $O(n^{5/2})$ contre $O(n^3)$ pour les stratégies linéaires.
Régime de Faisabilité : La réduction du nombre de portes a étendu la taille des problèmes réalisables sur un matériel bruité. Pour un budget de portes CZ fixe (ex: 3 600 portes), la stratégie glutonne a permis l'exécution d'instances allant jusqu'à 100 nœuds, alors que la stratégie linéaire était limitée à environ 60 nœuds.
Ratios d'Approximation : Les expériences matérielles ont démontré des performances améliorées :
- Max-Cut (MC) : La stratégie glutonne a amélioré le ratio d'approximation moyen de jusqu'à 6,62 % (à 72 qubits) par rapport à la stratégie linéaire.
- Ensemble Indépendant Maximum (MIS) : L'amélioration est encore plus prononcée, atteignant 9,32 % (à 56 qubits).
Comparaison de Troncature : Contra : des approches qui tronquent l'Hamiltonien de coût pour réduire la profondeur (sacrifiant les garanties théoriques), la stratégie glutonne a implémenté un sous-ensemble significativement plus large d'interactions cibles pour le même nombre de couches de SWAP, préservant ainsi davantage la structure du problème.

Signification et Revendications

Le document affirme qu'une transpilation efficace est cruciale pour la performance pratique du QAOA sur le matériel de l'ère NISQ (Near-term Intermediate-Scale Quantum). Les auteurs soutiennent que leur schéma de transpilation conscient du problème est la clé pour améliorer les performances des algorithmes quantiques sur les dispositifs bruyants, particulièrement pour les problèmes d'optimisation creux.

Les principales revendications concernant la signification incluent :

Permettre des Expériences Plus Grandes : La méthode permet des expériences allant jusqu'à 80 qubits sur le matériel actuel en réduisant la profondeur du circuit et l'accumulation d'erreurs.
Amplifier les Améliorations Matérielles : À mesure que la qualité du matériel s'améliore (augmentant le budget disponible de portes CZ), les bénéfices d'une transpilation efficace sont amplifiés. La stratégie glutonne permet une augmentation plus importante de la taille des problèmes accessibles par rapport aux stratégies linéaires à mesure que le budget de portes croît.
Pertinence pour l'Avantage Quantique : L'approche est particulièrement pertinente pour sonder les régimes de potentiel avantage quantique, incluant les régimes de dureté où les solveurs classiques peinent (ex: instances de MIS à faible densité avec 500 nœuds).
Pérennité : Le travail souligne qu'à mesure que les codes de correction d'erreurs (comme le code bicycle bivariaire) nécessiteront une connectivité structurée et non locale basée sur des réseaux rectangulaires, l'adaptation des stratégies de transpilation pour exploiter la connectivité 2D sera essentielle pour réduire la complexité des circuits dans les futures architectures.

Les auteurs concluent que bien que leur méthode repose sur des couches de SWAP prédéfinies, elle démontre qu'une transpilation consciente du problème est une étape nécessaire pour combler le fossé entre les algorithmes quantiques théoriques et l'exécution pratique sur un matériel bruité.