Technische Samenvatting: Heuristische en Optimale Synthese van CNOT- en Clifford-circuits

Probleemstelling

Efficiënte implementatie van Clifford-circuits is fundamenteel voor kwantumfoutcorrectie en kwantumalgoritmen. De efficiëntie van deze circuits wordt doorgaans gemeten aan de hand van het aantal verstrengelende twee-qubit-gates (specifiek CNOTs voor lineaire reversibele circuits) of de circuitdiepte. Het optimaliseren van deze metrieken is uitdagend omdat een enkele Clifford-operator geïmplementeerd kan worden door talloze circuitconfiguraties met zeer verschillende gate-aantallen en dieptes. Bestaande methoden, zoals Gaussische eliminatie of heuristische benaderingen in rustiq, tket en qiskit, falen vaak in het vinden van de meest compacte implementaties, met name voor grotere aantallen qubits of specifieke coderingcircuits. Hoewel de klassieke literatuur over lineaire reversibele circuits (alleen CNOT) diverse synthesetechnieken heeft vastgesteld, blijft er behoefte aan verenigde, efficiënte methoden die het aantal twee-qubit-gates minimaliseren voor zowel CNOT-only als algemene Clifford-circuits.

Methodologie

De auteurs stellen een verenigd kader voor voor het synthetiseren van CNOT- en algemene Clifford-circuits met behulp van drie verschillende algoritmische families: Optimale, A* en Greedy synthese. De kern van hun aanpak berust op het mappen van circuitoperators naar binaire matrices en het exploiteren van equivalentieklassen om zoekruimtes te verkleinen.

1. Wiskundige Representaties

• CNOT-circuits: Gemapt naar inversibele binaire matrices in $GL(n, 2)$. Een CNOT-gate komt overeen met het toevoegen van één kolom aan een andere.
• Algemene Clifford-circuits: Gemapt naar symplectische binaire matrices in $Sp(2n, 2)$. De auteurs maken gebruik van een circuitstructuur van drie lagen: qubit-permutaties, single-qubit Cliffords, en twee-qubit symplectische transvecties (die equivalent zijn aan CNOTs tot aan single-qubit Cliffords).
• Equivalentieklassen: De auteurs verkleinen de computationele complexiteit aanzienlijk door rekening te houden met de equivalentieklassen van matrices onder:
  • Rij- en kolompermutaties (qubit-permutaties).
  • Matrixtranspositie en inversie.
  • Voor Clifford-circuits: links en rechts vermenigvuldigen met single-qubit Clifford-operators.
  • Dit maakt het mogelijk om het circuitlid met het laagste gate-aantal of de laagste diepte uit een equivalentieklasse te selecteren.

2. Algoritmische Families

A. Optimale Synthese

• Benadering: Genereert een database van alle equivalentieklassen van matrices tot een bepaald aantal qubits ($n \le 7$ voor CNOT, $n \le 5$ voor Clifford).
• Mechanisme: Matrices worden gegenereerd door alle mogelijke gates sequentieel toe te passen. Equivalentie wordt bepaald door matrices te mappen naar bi-gekleurde grafen (voor CNOT) of gegeneraliseerde grafen (voor Clifford) en te controleren op isomorfisme met behulp van pakketten zoals nauty of Bliss.
• Gebruik: Voor een doelmatrix zoekt het algoritme naar de equivalentieklasse in de vooraf berekende database en haalt de optimale gate-sequentie op, waarbij de nodige permutaties worden toegepast om de doelmatrix te matchen.

B. A* Synthese

• Benadering: Een best-first search algoritme ontworpen voor circuits van gemiddelde grootte waar optimale databases te groot zijn.
• Mechanisme: Gebruikt een priority queue om gate-sequenties te verkennen. Het maakt gebruik van een heuristiekfunctie $h(P)$ om de resterende kosten te schatten om een permutatiematrix te bereiken (voor CNOT) of een permutatie plus single-qubit Cliffords (voor Clifford).
• Heuristieken: De auteurs leiden robuuste schatters af op basis van de rij- en kolomsommen van de matrix (specifiek $H_{sum}$ en $H_{prod}$ metrieken). Ze stelden vast dat het schalen van deze heuristieken ($r \cdot h$) de prestaties verbetert. Het algoritme committeert zich niet direct aan een gate, maar breidt de node uit met de laagste $g(P) + h(P)$ waarde.
• Optimalisatie: Om de exponentiële worst-case complexiteit te beheersen, wordt de omvang van de priority queue beperkt (bijv. op 100 entries), waarbij de maximale entries worden verwijderd als de limiet wordt overschreden.

C. Greedy Synthese

• Benadering: Een snel, deterministisch algoritme voor grote circuits.
• Mechanisme: In elke stap evalueert het alle mogelijke gates en selecteert het de gate die een specifieke heuristiek minimaliseert.
• Innovatie: In tegenstelling tot eerdere scalaire heuristieken (die entries of log-sommen sommeren en vaak in lokale minima terechtkomen), introduceren de auteurs een vector-gebaseerde heuristiek. Deze vector wordt gevormd door de kolomsommen van de matrix, de inverse, de transponist en de inverse-transponist te sorteren.
• Diepte-optimalisatie: Het greedy algoritme kan worden aangepast om de circuitdiepte te minimaliseren door de diepte als primaire kostenfactor te behanden en de heuristiek als secundaire straf.

Belangrijkste Bijdragen en Resultaten

1. Algoritmische Verbeteringen

• Vector Heuristiek: De voorgestelde vector-gebaseerde heuristiek voor greedy synthese presteert aanzienlijk beter dan scalaire heuristieken (zoals $H_{sum}$ en $H_{prod}$) bij het vermijden van lokale minima. Voor circuits met $n \ge 32$ qubits was de vector-heuristiek dominant, terwijl scalaire heuristieken faalden (geannuleerde runs) met een 100% abandoneringspercentage voor circuits met $n > 32$ qubits.
• Reductie van Equivalentieklassen: Door te mappen naar graaf-isomorfisme problemen en rekening te houden met permutaties, transposes en inversies, genereerden de auteurs databases die exponentieel kleiner zijn dan voorgaande methoden (bijv. het verkleinen van de zoekruimte voor $Sp(2n, 2)$ aanzienlijk vergeleken met Bravyi et al. [4]).

2. Benchmarking Resultaten

De auteurs hebben hun methoden getest tegenover rustiq, tket, qiskit, PyZX en Volanto met behulp van willekeurige matrices en specifieke datasets.

• CNOT-circuits:
  • Optimal/A*: Voor $n \le 7$ komt het A* algoritme overeen met de optimale gate-aantallen. Voor circuits tot $n = 32$ levert het A* algoritme de laagste gate-aantallen. Voor circuits met $n \ge 32$ levert het greedy algoritme met de vector-heuristiek de laagste CNOT-aantallen, waarbij het de Gaussian elimination overtreft met een gemiddelde reductie van 50% in gate-aantal.
• Algemene Clifford-circuits:
  • Willekeurige Matrices: Het A* algoritme komt overeen met optimale aantallen voor $n \le 5$ en levert de laagste aantallen voor circuits tot $n = 16$. Voor circuits met $n > 16$ presteert het greedy algoritme aanzienlijk beter dan alle andere geteste methoden (inclusclusief pytket en rustiq).
  • Hamiltoniaanse Dataset: Op een dataset van Hamiltonian evolutie-circuits (4 tot 64 qubits) presteerde het greedy algoritme beter dan het BSHM algoritme (gevolgd door pytket optimalisatie) in zowel gate-aantal als runtime.
  • Coderingcircuits: Voor de Golay code $[[23, 1, 7]]$ vonden de auteurs een coderingcircuit met 56 verstrengelende twee-qubit gates met behulp van A*, wat een verbetering is ten opzken van de vorige beste van 57 (Steane's methode) en 61 (Reinforcement Learning).
• Vergelijking met SAT-solvers: Vergeleken met qsynth (een SAT-gebaseerde solver), evenaarden de optimale en A* algoritmen van de auteurs de gate-aantallen voor circuits tot 5 qubits, met verwerkingstijden die orden van grootte sneller waren. Voor $n \ge 6$ liep qsynth in bijna alle gevallen vast (timeout), terwijl de methoden van de auteurs succesvol voltooiingen bereikten.

3. Implementatie

De algoritmen zijn geïmplementeerd in een Python-pakket dat beschikbaar is op GitHub, waardoor de gemeenschap de resultaten kan reproduceren en de methoden op hun eigen circuits kan toepassen.

Betekenis en Claims

Het artikel claimt dat de primaire betekenis ligt in het bieden van een suite van synthesetools die consistent lagere twee-qubit gate-aantallen bereiken dan bestaande state-of-the-art methoden over een breed scala aan circuitgroottes.

• Schaalbaarheid: Het werk overbrugt de kloof tussen kleinschalige optimale synthese en grootschalige heuristische synthese, en biedt een praktische oplossing voor circuits tot 64 qubits waar voorheen optimale methoden faalden door de databasegrootte en SAT-solvers faalden door tijdrestricties.
• Robuustheid: De vector-gebaseerde heuristiek wordt benadrukt als een cruciale vooruitgang die de "lokale minima" valstrik voorkomt die gebruikelijk is bij scalaire gebaseerde greedy benaderingen.
• Praktische Impact: Het vermogen om compactere circuits te vinden voor foutcorrectiecodes (zoals de Golay code) heeft een directe impact op de haalbaarheid van fouttolerante kwantumcomputers door de benodigde hulpbronnen voor logische operaties te verminderen.
• Bescheidenheid: De auteurs erkennen dat hun optimale synthese momenteel beperkt is tot $n \le 7$ (CNOT) en $n \le 5$ (Clifford) vanwege de databasegrootte, hoewel ze suggereren dat dit uitgebreid kan worden met betere coderings-technieken. Ze merken ook op dat hoewel hun greedy algoritme snel is, het geen globale optimaliteit garandeert voor grote circuits, hoewel het empirisch de concurrenten overtreft.

Het werk concludeert met de opmerking dat de algoritmen momenteel device-agnostisch zijn en in de toekomst verder geoptimaliseerd kunnen worden door ze naar C/Rust te porteren of aan te passen aan specifieke hardware-connectiviteitsbeperkingen.