⚛️ quantum physics

Optimizing QAOA circuit transpilation with parity twine and SWAP network encodings

Cet article introduit une méthode basée sur le recuit simulé qui optimise la transpilation de circuits QAOA sur du matériel quantique à disposition fixe en réduisant considérablement la surcharge d'encodage des chaînes de parité (parity twine chains) et des réseaux SWAP, permettant ainsi d'obtenir des diminutions substantielles de la profondeur de circuit et du nombre de portes à deux qubits par rapport aux transpileurs standards.

Auteurs originaux : J. A. Montanez-Barrera, Yanjun Ji, Michael R. von Spakovsky, David E. Bernal Neira, Kristel Michielsen

Publié 2026-08-12

📖 4 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : J. A. Montanez-Barrera, Yanjun Ji, Michael R. von Spakovsky, David E. Bernal Neira, Kristel Michielsen

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 d'organiser une fête dansante massive et chaotique où chaque invité doit se tenir la main avec tous les autres invités à un moment donné pour exécuter une routine spéciale. Maintenant, imaginez que la piste de danse est un couloir étroit, en file indienne, où les gens ne peuvent se tenir la main qu'avec la personne immédiatement à côté d'eux. Dans ce couloir, les gens ne peuvent pas simplement traverser la foule pour se rejoindre ; ils doivent se déplacer, échanger leurs places et se faufiler dans la file jusqu'à devenir voisins. Ce brassage prend du temps, et chaque fois que deux personnes se cognent pour échanger leurs places, il y a un risque qu'elles trébuchent, lâchent les mains ou ratent la routine. Dans le monde de l'informatique quantique, cette piste de danse est une puce quantique, les invités sont de minuscules particules appelées qubits, et le « trébuchement » est un type d'erreur qui gâche le calcul. Les scientifiques essaient constamment de trouver comment faire pour que ces qubits communiquent entre eux efficacement sans trébucher sur eux-mêmes, surtout que les puces actuelles ressemblent à ce couloir étroit et ne peuvent pas connecter tout le monde à tout le monde directement.

Cet article porte sur la recherche de la meilleure chorégraphie pour cette danse. Les chercheurs se sont concentrés sur un algorithme spécifique appelé QAOA, qui est utilisé pour résoudre des énigmes complexes comme trouver la meilleure façon de diviser un groupe de personnes en deux équipes. Pour faire fonctionner cela sur une puce unidimensionnelle étroite, ils ont dû utiliser la « transpilation », qui est simplement un mot savant pour réorganiser les instructions afin que le matériel puisse les comprendre. Ils ont testé deux méthodes principales pour ce brassage : le « réseau SWAP », qui est comme une danse de ligne standard et organisée où tout le monde se déplace étape par étape, et une méthode plus récente et plus complexe appelée « Parity Twine Chains » (PTC), qui ressemble davantage à l'encodage des informations de deux danseurs dans les mouvements d'une seule personne pour gagner de l'espace. Les auteurs ont également inventé une nouvelle technique de « recuit simulé », qui est comme un entraîneur intelligent par tâtonnement qui essaie des milliers de compositions de départ différentes pour trouver celle qui nécessite le moins de déplacements.

L'équipe a constaté que pour les énigmes petites et éparses, les programmes informatiques standards utilisés par des entreprises comme IBM étaient en fait assez bons pour minimiser le nombre de mouvements. Cependant, à mesure que les énigmes devenaient plus grandes et que les connexions entre les qubits devenaient plus fréquentes, leurs nouvelles méthodes commençaient à briller. En utilisant leur entraîneur intelligent pour réorganiser l'ordre de départ des qubits, ils ont pu réduire considérablement le nombre de fois où les qubits devaient échanger leurs places. Pour une énigme massive de 120 qubits avec une connectivité de 25 %, leur méthode a réduit de 87 % la profondeur du circuit (le temps nécessaire pour l'exécution) et de 29 % les portes à deux qubits (les mouvements risqués) par rapport au logiciel standard d'IBM. Ils ont également testé cela sur de véritables ordinateurs quantiques, spécifiquement les dispositifs « ibm fez » et « ibm kingston ». Sur l'« ibm fez », ils ont réussi à trouver la solution parfaite pour un problème de 20 qubits en utilisant leur méthode PTC, alors que la méthode standard ne fonctionnait que jusqu'à 15 qubits. Curieusement, sur le dispositif « ibm kingston », la méthode SWAP standard a en fait légèrement mieux performé que la méthode PTC pour un type spécifique de problème, suggérant que parfois, avoir moins de mouvements n'est pas la seule chose qui compte ; la façon dont l'information est encodée compte tout autant. Les chercheurs suggèrent que, bien que leur méthode soit un outil puissant pour réduire les erreurs et gagner du temps, ce n'est pas une solution miracle qui fonctionne parfaitement dans tous les scénarios, et le meilleur choix dépend de la forme spécifique du problème et des particularités du matériel.

Résumé technique : Optimisation de la transpilation des circuits QAOA avec les encodages Parity Twine et SWAP Network

Énoncé du problème
Les processeurs quantiques supraconducteurs (QPU) actuels souffrent d'une connectivité limitée entre les qubits, ce qui restreint généralement les interactions aux plus proches voisins sur des topologies spécifiques (par exemple, les réseaux heavy-hex). L'exécution d'algorithmes comme l'Algorithme d'Optimisation Quantique Approchée (QAOA), qui nécessite souvent des interactions deux-qubits denses ou totalement connectées, nécessite un processus de transpilation. Ce processus cartographie les qubits logiques vers des qubits physiques et insère des portes SWAP pour satisfaire les contraintes de connectivité. Cependant, les portes SWAP sont décomposées en plusieurs portes deux-qubits (par exemple, trois CNOT), qui sont la principale source de bruit et d'erreur sur les dispositifs de l'ère NISQ. De plus, bien que les encodages structurés tels que les réseaux SWAP et les chaînes Parity Twine (PTC) offrent des avantages analytiques en termes de ressources pour les graphes totalement connectés, leur application aux graphes faiblement connectés (non totalement connectés) reste sous-optimale. En outre, trouver le mappage initial optimal des qubits (un problème d'isomorphisme de sous-graphe) pour minimiser le nombre de portes dans ces scénarios de faible connectivité est un problème NP-difficile, et les solveurs existants comme SATMapper présentent des limitations de scalabilité et de temps d'exécution pour les grands systèmes.

Méthodologie
Les auteurs proposent une approche hybride combinant des stratégies d'encodage structurées avec une heuristique de recuit simulé (SA) pour optimiser le mappage initial des qubits logiques vers les qubits physiques.

Encodages :
- Réseau SWAP (SWAP Network) : Un programme de routage structuré sur une chaîne 1D où des couches alternées de portes SWAP de plus proches voisins déplacent les qubits logiques pour créer les adjacences requises.
- Chaînes Parity Twine (PTC) : Une méthode encodant l'information de parité Z multi-qubits dans des qubits physiques uniques via la parité. Cela permet d'exécuter des interactions non locales sous forme de rotations locales à un qubit ( $R_Z$ ), réduisant ainsi le nombre de portes deux-qubits par rapport aux réseaux SWAP. La méthode utilise une stratégie de décodage où des mesures sont prises dans la base de parité, et un post-traitement classique permet de récupérer la chaîne de bits logique, évitant ainsi le besoin de portes CNOT supplémentaires pour revenir à la base computationnelle.
Optimisation par Recuit Simulé (SA) :
- Les auteurs introduisent un algorithme basé sur le recuit simulé (SA) pour résoudre le problème d'isomorphisme de sous-graphe pour les encodages SWAP et PTC.
- Fonction de coût : La fonction de coût est combinatoire et non lisse, évaluant le nombre de portes deux-qubits qui peuvent être élaguées (supprimées) du circuit. Elle vérifie, couche par couche, si les paires de qubits mappées correspondent à des arêtes natives du graphe de couplage du matériel. Si une interaction requise est absente du graphe du problème, les portes correspondantes dans le programme d'encodage sont omises.
- Processus : L'algorithme échange de manière itérative des paires d'étiquettes de qubits pour trouver une permutation qui minimise le nombre total de portes deux-qubits et la profondeur du circuit. Cette approche est choisie car les méthodes basées sur le gradient sont inadaptées à l'espace de recherche discret, et les méthodes exactes sont trop coûteuses en termes de calcul.
Benchmarking et Modélisation du Bruit :
- La méthode est comparée aux transpilers standards (Qiskit-T, Qiskit-P, Qiskit-AI, TKET) et à SATMapper.
- Les simulations de bruit utilisent un modèle de bruit dépolarisant agissant sur les portes deux-qubits au sein d'un protocole de Linear Ramp QAOA (LR-QAOA) pour des problèmes de Weighted MaxCut (WMC).
- La validation expérimentale est effectuée sur des dispositifs IBM Quantum (ibm_fez et ibm_kingston).

Principales contributions

Encodages optimisés par SA : L'introduction d'une stratégie de recuit simulé pour optimiser l'ordre initial des qubits pour les encodages SWAP et PTC, ciblant spécifiquement les graphes partiellement connectés.
Scalabilité : Démonstration que l'approche SA passe à l'échelle efficacement jusqu'à 200 qubits en simulation, offrant un avantage de temps d'exécution de plusieurs ordres de grandeur par rapport à SATMapper tout en offrant une qualité de solution comparable.
Décodage PTC : Une description détaillée d'une stratégie de décodage pour PTC qui élimine le besoin de portes CNOT augmentant la profondeur du circuit pour revenir à la base computationnelle.
Validation Expérimentale : La première implémentation expérimentale de l'encodage PTC sur du matériel quantique réel.

Résultats

Réduction du nombre de portes et de la profondeur : Pour les circuits QAOA dont les densités d'arêtes ( $E_d$ $E_{d}$ ) dépassent certains seuils, PTC+SA et SWAP+SA surpassent significativement les transpilers standards.
- Pour une instance de 120 qubits avec 25 % de connectivité, la méthode proposée a obtenu une réduction de 87 % de la profondeur du circuit et une réduction de 29 % des portes deux-qubits par rapport au transpiler Qiskit (niveau d'optimisation 3).
- Le seuil pour que PTC+SA surpasse Qiskit-T en nombre de portes diminue à mesure que la taille du système augmente (passant de $E_d \approx 0,35$ pour 20 qubits à $E_d \approx 0,13$ pour 120 qubits).
Efficacité du temps d'exécution : La méthode SA converge vers des solutions de haute qualité en quelques secondes pour des problèmes de 200 qubits, tandis que SATMapper nécessite des centaines, voire des milliers de secondes.
Résilience au bruit :
- Simulation : Dans les simulations de bruit, PTC a montré une probabilité de succès ( $p_{gs}$ ) plus élevée que SWAP pour des niveaux de bruit faibles à modérés en raison du nombre réduit de portes, bien que le ratio d'approximation ( $r$ ) soit similaire pour les deux.
- Matériel Réel (ibm_fez) : L'encodage PTC a étendu la portée des expériences utiles de LR-QAOA. Des solutions optimales ont été trouvées pour des tailles de problèmes allant jusqu'à 20 qubits avec PTC, contre seulement 15 qubits avec SWAP. La distinction par rapport à l'échantillonnage aléatoire s'est maintenue jusqu'à 22 qubits pour PTC contre 20 pour SWAP.
- Matériel Réel (ibm_kingston) : Pour un problème de 20 qubits avec $E_d = 0,298$ , SWAP+SA a obtenu le meilleur ratio d'approximation (amélioration de 20,83 % par rapport au hasard), surpassant PTC+SA (13,99 %). Les auteurs notent que bien que PTC utilise moins de portes, l'encodage des paires logiques dans des qubits physiques uniques peut être plus sensible à l'accumulation de bruit dans des scénarios non totalement connectés.
Comparaison des Transpilers : Les transpilers standards (comme Qiskit-T) minimisent souvent le nombre de portes au prix d'une augmentation significative de la profondeur du circuit, ce qui exacerbe le bruit. Les méthodes proposées maintiennent des circuits compacts avec une profondeur moindre.

Signification et Revendications
L'article affirme présenter la première démonstration où les encodages SWAP et PTC surpassent les méthodes de transpilation standard dans des scénarios de connectivité réduite. Cela constitue également la première implémentation expérimentale de l'encodage PTC sur du matériel quantique réel.

Les auteurs soulignent que, bien que les encodages structurés optimaux soient bien connus pour les graphes totalement connectés, leur application à des graphes partiellement connectés via la proposition d'optimisation basée sur le SA permet des réductions de ressources significatives. Ils concluent que pour des systèmes allant jusqu'à 20 qubits, l'encodage PTC améliore les performances sur le matériel réel, étendant la taille de problème viable pour le LR-QAOA. Cependant, ils notent avec modestie que dans les expériences non totalement connectées sur ibm_kingston, SWAP+SA a parfois surpassé PTC+SA, suggérant que le compromis entre le nombre de portes et la sensibilité au bruit dépend fortement de la structure d'encodage spécifique et de la topologie du problème. Ce travail établit une voie pratique pour l'exécution de QAOA sur des dispositifs de l'ère NISQ à connectivité contrainte avec un overhead réduit.

Articles similaires