Technische Samenvatting: Clifford-circuit Synthese voor Gedistribueerde Kwantumarchitecturen met Willekeurige Netwerktopologie

Probleemstelling

Het artikel behandelt de uitdaging van het compileren van kwantumcircuits voor gedistribueerde kwantumarchitecturen, waarbij qubits zijn verdeeld in afzonderlijke blokken (bijv. gescheiden kwantumprocessors die verbonden zijn via verstrengeling of logische qubits gecodeerd in blokcodes). In dergelijke systemen zijn niet-lokale operaties (poorten die werken tussen partities) aanzienlijk duurder in termen van tijd en foutenpercentages vergeleken met lokale operaties. In de voorgestelde "bicycle architectuur" zijn de foutenpercentages van niet-lokale operaties bijvoorbeeld twee orde van grootte hoger dan die van lokale operaties.

De kern van het probleem is het synthetiseren van equivalente circuits voor CNOT, Clifford, en Clifford+RZ (inclusief Clifford+T) circuits die het aantal niet-lokale poorten minimaliseren, terwijl de willekeurige connectiviteitsbeperkingen tussen partities worden gerespecteerd. Bestaande benaderingen richten zich primair op het plannen (scheduling) en plaatsen van qubits (bijv. via teleportatie) om de kosten van bestaande niet-lokale poorten te minimaliseren, in plaats van het fundamenteel verminderen van het aantal vereiste niet-lokale poorten door middel van circuit-resynthese.

Methodologie

1. Circuitrepresentatie

De auteur introduceert een nieuwe circuitrepresentatie die alle lokale Clifford-operaties abstraheert. Elk Clifford+RZ circuit kan worden gedecomposeerd in:

• Lokaal Clifford Circuit ($C_L$): Bevat alleen operaties binnen partities.
• Niet-lokaal/Niet-Clifford DAG ($D(C_N)$): Een gerichte acyclische graaf (Directed Acyclic Graph) die de resterende operaties representeert, bestaande uit twee typen poorten:
  • Pauli Exponenten ($P(A, \theta)$): $e^{-i\theta/2 A}$, die niet-Clifford operaties coderen (bijv. T-poorten).
  • Gegeneraliseerde CNOT Poorten ($C(A, B)$): Gedefinieerd als $e^{i\frac{\pi}{4}(A \otimes I + I \otimes B - A \otimes B - I \otimes I)}$, waarbij $A$ en $B$ Pauli-strings zijn op verschillende partities. Cruciaal is dat elke gegeneraliseerde CNOT exact met één niet-lokale CNOT-poort (plus lokale Cliffords) kan worden geïmplementeerd, waardoor het minimaliseren van deze poorten gelijkstaat aan het minimaliseren van niet-lokale resources.

2. Synthese-algoritmen

Het artikel past bestaande resynthese-technieken aan om te opereren op blokmatrices en blok-tableau's, waarbij partities als atomaire eenheden worden behanden.

• BlockRowCol (voor CNOT-circuits):

  • Gebaseerd op het RowCol algoritme, dat Gaussische eliminatie gebruikt op pariteitsmatrices.
  • Kerninzicht: De pariteitsmatrix van een gedistribueerd circuit wordt beschouwd als een blokmatrix. Het doel is om de off-diagonaal blokken (inter-partitie interacties) te elimineren met behulp van blok-rij-operaties.
  • Mechanisme: Een blok-rij optelling komt overeen met het toepassen van een set gegeneraliseerde CNOT-poorten. Het aantal vereiste poorten wordt bepaald door de rang van de coëfficiëntmatrix die voor de blok-optelling wordt gebruikt.
  • Connectiviteit: Gebruikt Steiner-bomen om de willekeurige partitie-connectiviteit te respecteren bij het uitvoeren van blok-operaties.
  • Optimaliteit: Voor $k=2$ partities is het algoritme bewezen binnen een factor 2 van het optimale aantal niet-lokale poorten voor ZX-type gegeneraliseerde CNOT's. Asymptotisch is het optimaal wanneer $k = o(n / \log n)$.

• DistRowCol (voor Clifford-circuits):

  • Breidt de synthese uit naar volledige Clifford-circuits met behulp van stabilisator-tableau's.
  • Mechanisme: Ontwart partities één voor één door het stabilisator-tableau te reduceren tot een blok-diagonaal vorm. Het maakt gebruik van lemma's om Pauli-strings te vinden die commuten met bestaande stabilisatoren/destabilisatoren om de structurele integriteit tijdens eliminatie te waarborgen.
  • Complexiteit: Gebruikt maximaal $2n(k-1)$ niet-lokale poorten, wat overeenkomt met de asymptotische grenzen van BlockRowCol.

• Clifford+RZ Optimalisatie:

  • Distributie: Past methoden voor fase-polynoom synthese aan om Pauli-exponenten over partities te distribueren, waarbij heuristieken worden gebruikt om pivot-partities te selecteren die toekomstige poort-aantallen minimaliseren.
  • Folding: Introduceert Gegeneraliseerde CNOT Folding, een techniek analoog aan fase-folding. Het combineert aangrenzende gegeneraliseerde CNOT-poorten die een gedeeld Pauli-string argument delen ($C(A, B_1) \cdot C(A, B_2)$) om het aantal te verminderen, waarbij potentieel lokale Clifford-correcties worden geïntroduceerd.
  • Subcircuit Detectie: Stelt een methode voor om CNOT of Clifford subcircuits te detecteren binnen de DAG-representatie (met behulp van convexe acyclische partities en beam search) om de gespecialiseerde BlockRowCol of DistRowCol routines toe te passen.

Belangrijkste Resultaten en Benchmarks

De auteur heeft deze algoritmen geïmplementeerd en gebenchmarkt tegen pytket-dqc (een state-of-the-art tool voor gedistribueerde circuitoptimalisatie gebaseerd op qubit-plaatsing en teleportatie) en standaard resynthese-methoden.

• CNOT Circuits:

  • Voor diepe circuits en grotere qubit-aantallen presteert BlockRowCol over het algemeen beter dan of gelijk aan pytket-dqc gecombineerd met resynthese.
  • BlockRowCol is bijzonder effectief in lineaire naburige-buur architecturen, waar het het aantal niet-lokale poorten aanzienlijk vermindert vergeleken met andere methoden.
  • Voor ondiepe (shallow) circuits presteert pytket-dqc (zonder resynthese) vaak beter, waarschijnlijk door de overhead van resynthese en de voordelen van qubit-herordening (wat de huidige implementatie niet ondersteunt).

• Clifford Circuits:

  • DistRowCol toont een consistent voordeel ten opzichte van pytket-dqc met resynthese voor diepere circuits en is opvallend ongevoelig voor de specifieke connectiviteitstopologie (2D grid versus lineair).

• Clifford+T Circuits:

  • De resultaten zijn gemengd. Voor architecturen met veel partities ($k=9$), presteren resynthese-methoden (inclusief die van de auteur) vaak slechter dan pytket-dqc alleen. De auteur suggereert dat dit komt door de algemene inefficiëntie van resynthese voor Clifford+T in gedistribueerde omgevingen, in plaats van een fout in hun specifieke methode.
  • Voor $k=2$ is de prestatie vergelijkbaar met andere methoden.

• Schaalbaarheid:

  • De algoritmen zijn zeer efficiënt in runtime. De auteur heeft succesvol BlockRowCol uitgevoerd op instanties met 512 qubits en 128 partities (circuits met $> 2 \cdot 10^5$ poorten) in enkele seconden, terwijl pytket-dqc (gebaseerd op hypergraaf-partitionering) aanzienlijk trager is.

Betekenis en Claims

De auteur claimt de volgende bijdragen:

1. Asymptotische Optimaliteit: Het BlockRowCol algoritme is bewezen asymptotisch optimaal voor CNOT-circuit synthese in gedistribueerde settings wanneer het aantal partities $k$ klein is in verhouding tot het aantal qubits ($k = o(n / \log n)$).
2. Benaderde Optimaliteit voor $k=2$: Voor twee partities is de methode aangetoond binnen een constante factor (specifiek, maximaal 2x) van de optimale oplossing voor circuits die ZX-type gegeneraliseerde CNOT's gebruiken.
3. Algemeen Kader: Het werk laat zien dat bestaande synthesetechnieken gebaseerd op pariteitsmatrices, stabilisator-tableau's en fase-polynomen op natuurlijke wijze kunnen worden gegeneraliseerd naar gedistribueerde settings door te opereren op blokstructuren.
4. Praktische Toepassingen:
   • CSS Codes: De methode maakt synthese van logische CNOT-circuits in CSS-codes mogelijk met $O(nk)$ intra-block Pauli-metingen en $O(k^2)$ inter-block transversale CNOT's, onafhankelijk van de inter-block connectiviteit.
   • Phantom Codes: Biedt een bovengrens van $6k(k-1)$ CNOT-operaties voor logische circuits, wat kwadratisch schaalt met het aantal blokken in plaats van het aantal logische qubits.
   • Tree Tensor Networks: De methode kan worden gebruikt om hoog-niveau poorten in tree tensor netwerk simulaties te minimaliseren, wat een asymptotische verbetering biedt ten opzichte van standaard synthesemethoden voor klassieke simulatiekosten.

De auteur hanteert een bescheiden toon en erkent dat hun methoden voorlopig zijn en dat praktische details (zoals qubit-herordening en het afstemmen van heuristieken) verder kunnen worden geoptimaliseerd. Zij benadrukken dat hun aanpak de bestaande plaatsings- en planningstrategieën aanvult, in plaats van vervangt.