Résumé Technique : Synthèse de Circuits de Clifford pour les Architectures Quantiques Distribuées avec Topologie de Réseau Arbitraire

Énoncé du Problème

L'article traite du défi de la compilation de circuits quantiques pour les architectures quantiques distribuées, où les qubits sont partitionnés en blocs distincts (par exemple, des processeurs quantiques séparés reliés par l'intrication ou des qubits logiques encodés dans des codes de blocs). Dans ces systèmes, les opérations non locales (portes agissant entre les partitions) sont nettement plus coûteuses en termes de temps et de taux d'erreur que les opérations locales. Par exemple, dans la « architecture bicycle » proposée, les opérations non locales présentent des taux d'erreur deux ordres de grandeur plus élevés que les opérations locales.

Le problème central est de synthétiser des circuits équivalents pour les circuits CNOT, Clifford et Clifford+RZ (incluant Clifford+T) afin de minimiser le nombre de portes non locales tout en respectant les contraintes de connectivité arbitraires entre les partitions. Les approches existantes se concentrent principalement sur l'ordonnancement et le placement des qubits (par exemple, via la téléportation) pour minimiser le coût des portes non locales existantes, plutôt que de réduire fondamentalement le nombre de portes non locales requises par une resynthèse de circuit.

Méthodologie

1. Représentation du Circuit

L'auteur introduit une nouvelle représentation de circuit qui fait abstraction de toutes les opérations de Clifford locales. Tout circuit Clifford+RZ est décomposé en :

• Circuit Clifford Local ($C_L$) : Contient uniquement des opérations au sein des partitions.
• DAG Non Local/Non-Clifford ($D(C_N)$) : Un graphe orienté acyclique (DAG) représentant les opérations restantes, composé de deux types de portes :
  • Exponentielles de Pauli ($P(A, \theta)$) : $e^{-i\theta/2 A}$, encodant les opérations non-Clifford (ex: portes T).
  • Portes CNOT Généralisées ($C(A, B)$) : Définies comme $e^{i\frac{\pi}{4}(A \otimes I + I \otimes B - A \otimes B - I \otimes I)}$, où $A$ et $B$ sont des chaînes de Pauli sur des partitions différentes. Crucialement, toute CNOT généralisée peut être implémentée en utilisant exactement une porte CNOT non locale (plus des Cliffords locaux), ce qui rend la minimisation de ces portes équivalente à la minimisation des ressources non locales.

2. Algorithmes de Synthèse

L'article adapte les techniques de resynthèse existantes pour opérer sur des matrices par blocs et des tableaux par blocs, en traitant les partitions comme des unités atomiques.

• BlockRowCol (pour les circuits CNOT) :

  • Basé sur l'algorithme RowCol, qui utilise l'élimination de Gauss sur les matrices de parité.
  • Insight Clé : La matrice de parité d'un circuit distribué est vue comme une matrice par blocs. L'objectif est d'éliminer les blocs hors-diagonaux (interactions inter-partitions) en utilisant des opérations de lignes par blocs.
  • Mécanisme : Une addition de lignes par blocs correspond à l'application d'un ensemble de portes CNOT généralisées. Le nombre de portes requises est déterminé par le rang de la matrice de coefficients utilisée pour l'addition par blocs.
  • Connectivité : Utilise des arbres de Steiner pour respecter la connectivité arbitraire des partitions lors de l'exécution des opérations par blocs.
  • Optimalité : Pour $k=2$ partitions, l'algorithme est prouvé être à un facteur 2 de l'optimalité du nombre de portes non locales pour les CNOT de type ZX. Asymptotiquement, il est optimal lorsque $k = o(n / \log n)$.

• DistRowCol (pour les circuits de Clifford) :

  • Étend la synthèse aux circuits de Clifford complets en utilisant des tableaux de stabilisateurs.
  • Mécanisme : Désintrique les partitions une par une en réduisant le tableau de stabilisateurs à une forme diagonale par blocs. Il utilise des lemmes pour trouver des chaînes de Pauli qui commutent avec les stabilisateurs/destabiliseurs existants afin de garantir l'intégrité structurelle pendant l'élimination.
  • Complexité : Utilise au plus $2n(k-1)$ portes non locales, correspondant aux bornes asymptotiques de BlockRowCol.

• Optimisation Clifford+RZ :

  • Distribution : Adapte les méthodes de synthèse de polynômes de phase pour distribuer les exponentielles de Pauli à travers les partitions, en utilisant des heuristiques pour sélectionner les partitions pivots afin de minimiser le nombre futur de portes.
  • Repliement (Folding) : Introduit le Repliement de CNOT Généralisé, une technique analogue au repliement de phase. Il combine des portes CNOT généralisées adjacentes partageant un argument de chaîne de Pauli ($C(A, B_1) \cdot C(A, B_2)$) pour réduire le compte, introduisant potentiellement des corrections de Clifford locales.
  • Détection de Sous-circuits : Propose une méthode pour détecter des sous-circuits CNOT ou Clifford dans la représentation DAG (en utilisant des partitions acycliques convexes et une recherche en faisceau/beam search) pour appliquer les routines spécialisées BlockRowCol ou DistRowCol.

Résultats Clés et Benchmarks

L'auteur a implémenté ces algorithmes et les a comparés à pytket-dqc (un outil de pointe pour l'optimisation de circuits distribués basé sur le placement de qubits et la téléportation) ainsi qu'à des méthodes de resynthèse standards.

• Circuits CNOT :

  • Pour les circuits profonds et les grands nombres de qubits, BlockRowCol surpasse généralement ou égale pytket-dqc combiné à la resynthèse.
  • BlockRowCol est particulièrement efficace dans les architectures de type voisin plus proche linéaire, où il réduit considérablement le nombre de portes non locales par rapport aux autres méthodes.
  • Pour les circuits peu profonds, pytket-dqc (sans resynthèse) est souvent plus performant, probablement en raison du surcoût de la resynthèse et des avantages du réordonnancement des qubits (que l'implémentation actuelle ne supporte pas).

• Circuits de Clifford :

  • DistRowCol montre un avantage constant sur pytket-dqc avec resynthèse pour les circuits profonds et est notablement insensible à la topologie de connectivité spécifique (grille 2D vs linéaire).

• Circuits Clifford+T :

  • Les résultats sont mitigés. Pour les architectures avec de nombreuses partitions ($k=9$), les méthodes de resynthèse (y compris celle de l'auteur) sont souvent moins performantes que pytket-dqc seul. L'auteur suggère que cela est dû à l'inefficacité générale de la resynthèse pour Clifford+T dans des contextes distribués, plutôt qu'à un défaut de leur méthode spécifique.
  • Pour $k=2$, les performances sont comparables aux autres méthodes.

• Scalabilité :

  • Les algorithmes sont très efficaces en temps d'exécution. L'auteur a réussi à exécuter BlockRowCol sur des instances de 512 qubits et 128 partitions (circuits avec $> 2 \cdot 10^5$ portes) en quelques secondes, alors que pytket-dqc (basé sur la partition de hypergraphes) est nettement plus lent.

Signification et Revendications

L'article revendique les contributions suivantes :

1. Optimalité Asymptotique : L'algorithme BlockRowCol est prouvé comme étant asymptotiquement optimal pour la synthèse de circuits CNOT dans des contextes distribués lorsque le nombre de partitions $k$ est petit par rapport au nombre de qubits ($k = o(n / \log n)$).
2. Optimalité Approximative pour $k=2$ : Pour deux partitions, la méthode est montrée comme étant à un facteur constant (spécifiquement, au plus 2x) de la solution optimale pour les circuits utilisant des CNOT généralisés de type ZX.
3. Cadre Général : Ce travail démontre que les techniques de synthèse existantes basées sur les matrices de parité, les tableaux de stabilisateurs et les polynômes de phase peuvent être naturellement généralisées aux contextes distribués en opérant sur des structures par blocs.
4. Applications Pratiques :
   • Codes CSS : La méthode permet la synthèse de circuits CNOT logiques dans les codes CSS en utilisant $O(nk)$ mesures de Pauli intra-blocs et $O(k^2)$ CNOT transversaux inter-blocs, indépendamment de la connectivité inter-blocs.
   • Codes Fantômes (Phantom Codes) : Fournit une borne de $6k(k-1)$ opérations CNOT pour les circuits logiques, évoluant de manière quadratique avec le nombre de blocs plutôt qu'avec le nombre de qubits logiques.
   • Réseaux de Tenseurs d'Arbre (Tree Tensor Networks) : La méthode peut être utilisée pour minimiser les portes de haut niveau dans les simulations de réseaux de tenseurs d'arbre, offrant une amélioration asymptotique par rapport aux méthodes de simulation classique standard.

L'auteur maintient un ton modeste, reconnaissant que leurs méthodes sont préliminaires et que des détails pratiques (tels que le réordonnancement des qubits et le réglage des heuristiques) pourraient être davantage optimisés. Il souligne que son approche complète, plutôt qu'elle ne remplace, les stratégies de placement et d'ordonnancement existantes.