Quantum group codes for non-Clifford logic: enhanced decoding, addressability and parallelizability

Technische Samenvatting: Kwantum Groepscodes voor Non-Clifford Logica

Probleemstelling
Huidige fouttolerante kwantumrekeningschema's lijden onder aanzienlijke ruimte- en tijdoverhead, wat de realisatie van praktische kwantumcomputers belemmert. Hoewel Calderbank-Shor-Steane (CSS) codes die transversale poorten ondersteunen een pad naar fouttolerantie bieden, kampen bestaande constructies met twee primaire beperkingen:

1. Decoderingcomplexiteit: State-of-the-art kwantum Algebraïsche Geometrie (AG) codes die non-Clifford transversale poorten ondersteunen (essentieel voor Magic State Distillation, of MSD), vertrouwen op decoderingsalgoritmen met een kubische tijdscomplexiteit ($O(n^3)$). Deze hoge complexiteit plant zich voort in het MSD-protocol, wat de efficiëntie beperkt.
2. Adresseerbaarheid en Paralleliseerbaarheid: Bestaande codes met transversale non-Clifford poorten implementeren doorgaans globale operaties die gelijktijdig op alle fysieke qudits inwerken. Dit gebrek aan "adresseerbaarheid"—het vermogen om specifieke subsets van logische qudits te targeten—beperkt de algoritmische flexibiliteit. Bovendien heeft recent werk aangetoond dat er codes bestaan met adresseerbare poorten, maar de constructies vertrouwen vaak op zeer specifieke families van transitieve AG-codes, en de paralleliseerbaarheid van deze poorten vereist verdere optimalisatie om de circuitdiepte te verminderen.

Methodologie
De auteurs stellen een raamwerk voor gebaseerd op kwantum groepscodes, afgeleid van klassieke quasi groepscodes met specifieke vermenigvuldigingseigenschappen. De methodologie verloopt in drie hoofdfasen:

1. Raamwerkdefinitie (Kwantum Groepscodes):
   De auteurs definiëren een klasse van kwantum CSS-codes waarbij de onderliggende klassieke codes ($C_0$ en $C_1$) quasi-$G$ codes zijn (isomorf aan rechtse idealen van een groepsalgebra $F_q[G]$). Door het bestaan van een $G$-module homomorfie-sectie voor de quotientafbeelding te waarborgen, stellen zij voorwaarden vast waaronder deze kwantumcodes paralleliseerbare en adresseerbare transversale multi-control-Z ($C_{m-1}Z$) poorten toelaten.

   • Kernmechanisme: De groepswerking maakt de constructie van modulatiefuncties mogelijk die de implementatie van logische poorten op specifieke banen (orbits) van logische qudits mogelijk maken met behulp van depth-one fysieke circuits.

2. Codeconstructie via Lifting:
   Om codes met goede parameters en efficiënte decodering te genereren, gebruiken de auteurs een lifting-procedure gebaseerd op de klassieke veldentheorie (specifiek uit [CG26]).

   • Ze beginnen met een goede klassieke AG-code $C$ over $F_q$ die voldoet aan de $m$-vermenigvuldigingseigenschap.
   • Ze construeren een onafgesplitste abelse uitbreiding van de onderliggende functiekolom, wat een nieuwe code $\tilde{C}$ over $F_{q^2}$ creëert.
   • Dit lifting-proces voorziet de nieuwe code van een grote abelse permutatie-automorfiegroep $G$, waardoor de code een vrije $F_{q^2}[G]$-module wordt. Cruciaal is dat de lifting de $m$-vermenigvuldigingseigenschap behoudt die vereist is voor transversale poorten.

3. Decoderingoptimalisatie:
   De auteurs maken gebruik van de module-structuur van de gelifte codes. In tegenstelling tot standaard AG-codes die een kubische decoderingstijd vereisen, maakt de vrije module-structuur de adaptatie van decoderingsalgoritmen mogelijk die gebruikmaken van snelle matrixvermenigvuldiging over de groepsalgebra. Dit resulteert in een quasi-kwadratische tijd-decoder ($O(n^2 \cdot \text{polylog}(n))$) met een lineaire decoderingsstraal.

Belangrijkste Bijdragen en Resultaten

• Stelling 1.1 (Codefamilies): Het artikel construeert twee families van $q$-dimensionale qudit kwantum groepscodes (waarbij $q=t^4$):

  1. Volledig Adresseerbare Familie: Codes met parameters $[[n, \Theta(n/\log n), \Theta(n)]]_q$. Deze staan volledig adresseerbare transversale $C_{\tilde{m}-1}Z$ poorten toe. De diepte van logische circuits die $m$ codeblokken bevatten, wordt begrensd door $O(k^{\tilde{m}-1})$.
  2. High-Rate Familie: Codes met parameters $[[n, \Theta(n), \Theta(n)]]_q$. Deze staan een globale transversale $C_{\tilde{m}}Z$ poort toe en orbit-wise adresseerbare $C_{\tilde{m}-1}Z$ poorten over $\Theta(\log n)$ banen.
  • In beide gevallen ondersteunen de codes een $O(n^2 \cdot \text{polylog}(n))$-tijd decoder met een lineaire decoderingsstraal, wat een significante verbetering is ten opzichte van de $O(n^3)$ complexiteit van eerdere AG-gebaseerde constructies.

• Corollary 1.2 (Magic State Distillation): Door de high-rate familie toe te passen op Magic State Distillation (MSD) protocollen, demonstreren de auteurs het bestaan van een constant-overhead distillatieprotocol voor qubit CCZ-magic states met een $O(n^2 \cdot \text{polylog}(n))$ tijdcomplexiteit. Dit vertegenwoordigt een bijna lineaire reductie in tijdcomplexiteit vergeleken met de state-of-the-art $O(n^3)$ protocollen.

• Paralleliseerbaarheid: Het werk stelt vast dat logische multi-control-Z circuits in hoge mate geparalleliseerd kunnen worden. Voor dichte circuits wordt de minimale diepte begrensd door $O(k^{m-1})$, wat optimaal is voor dergelijke circuits.

Betekenis
Het artikel beweert dat het werk kritieke knelpunten in fouttolerante kwantumcomputerberekeningen aanpakt:

1. Efficiëntie: Door de decoderingcomplexiteit te reduceren van kubisch naar quasi-kwadratisch, wordt de tijdoverhead voor MSD-protocollen aanzienlijk verlaagd, wat de praktische haalbaarheid van fouttolerante kwantumcomputerberekeningen dichterbij brengt.
2. Flexibiliteit: De introductie van adresseerbare en paralleliseerbare non-Clifford poorten gaat verder dan globale operaties, wat een nauwkeuriger controle over logische qudits mogelijk maakt. Dit is essentieel voor circuitcompilatie en algoritmen die geen globale verstrengeling vereisen.
3. Generalisatie: De constructie gaat verder dan de specifieke transitieve AG-codes die in eerder werk werden gebruikt, door gebruik te maken van een bredere klasse van gelifte AG-codes met grote abelse automorfiegroepen. Dit biedt een veelzijdiger instrumentarium voor het ontwerpen van kwantumcodes met transversale non-Clifford poorten.

De auteurs benadrukken dat hun resultaten zijn afgeleid van theoretische constructies en bestaande lifting-technieken, waarbij wordt geverifieerd dat deze transformaties de noodzakelijke eigenschappen voor transversale non-Clifford poorten behouden terwijl de decoderingsefficiëntie wordt verbeterd.