Sequences of Bivariate Bicycle Codes from Covering Graphs

Sintesi Tecnica: Sequenze di Codici Bivariate Bicycle da Grafi di Copertura

Enunciato del Problema
I codici Quantum Low-Density Parity-Check (qLDPC) offrono un'alternativa promettente ai codici di superficie, fornendo tassi costanti e una migliore scalabilità della distanza, riducendo potenzialmente l'overhead di spazio richiesto per il calcolo quantistico fault-tolerant. Tuttavia, l'identificazione di nuovi codici qLDPC ad alte prestazioni rimane una sfida a causa del vasto spazio di ricerca dei possibili polinomi di controllo di parità. In particolare, i codici Bivariate Bicycle (BB), che sono codici di algebra di gruppo definiti su $\mathbb{F}_2[Z_l \times Z_m]$, hanno mostrato un potenziale con istanze ad alto tasso e alta distanza (ad esempio, il codice "gross" [[144, 12, 12]]), ma un metodo generale per generare infinite famiglie di tali codici con parametri prevedibili è stato limitato. Inoltre, comprendere la relazione tra gli operatori logici e gli automorfismi attraverso diverse istanze di codice è cruciale per implementare operazioni logiche, ma è spesso difficile da analizzare per codici di grandi dimensioni.

Metodologia
Gli autori propongono un framework per generare infinite sequenze di codici BB utilizzando il concetto matematico di grafi di copertura (o lift di grafi). La metodologia principale prevede:

1. Condizioni Algebriche per la Copertura: Il documento stabilisce che un grafo di Tanner di un codice BB $\tilde{Q}$ è un grafo di copertura di un codice BB base $Q$ se specifiche condizioni algebriche sono soddisfatte riguardo ai loro parametri di reticolo e ai polinomi definitori. Nello specifico, se $Q$ ha parametri $(l, m)$ e polinomi $A, B$, un codice di copertura $\tilde{Q}$ con parametri $(\tilde{l}, \tilde{m})$ e polinomi $\tilde{A}, \tilde{B}$ è una valida $h$-copertura (dove $h = \tilde{l}\tilde{m}/lm$) se:

   • $\tilde{l} = ul$ e $\tilde{m} = tm$ per interi $u, t$.
   • Gli esponenti dei monomi in $\tilde{A}$ e $\tilde{B}$ sono congruenti a quelli in $A$ e $B$ modulo $l$ e $m$, rispettivamente.
   • L'assegnazione di tensione (voltage assignment) utilizzata per generare il grafo derivato corrisponde al "quoziente" dei parametri del reticolo.

2. Riduzione dello Spazio di Ricerca: Limitando la ricerca a polinomi che soddisfano queste condizioni di congruenza, gli autori riducono drasticamente lo spazio di ricerca per nuovi codici. Invece di cercare nell'intero spazio di polinomi di lunghezza $n$, la ricerca è limitata a variazioni dei polinomi di un codice base, riducendo la complessità da $O(n^6)$ a circa $O(h^4)$ per le $h$-coperture.

3. Mappe di Catena e Omo-logia: La mappa di copertura del grafo è estesa a una mappa di catena (chain map) tra i complessi di catena dei codici base e di copertura. Questo induce mappe su (co)omologia:

   • Mappa di Proiezione ($p$): Mappa gli operatori logici dal codice di copertura al codice base.
   • Mappa di Lifting ($\tau$): Mappa gli operatori logici dal codice base al codice di copertura.
   • Lift Preservante il Peso ($\sigma$): Un tipo specifico di lift che seleziona un singolo pre-immagine per ogni vertice, usato per porre un limite superiore alla distanza del codice di copertura.

4. Lifting degli Automorfismi: Il framework è esteso per dimostrare che gli automorfismi del grafo (e di conseguenza gli automorfismi dei codici CSS) possono essere elevati (lifted) dal base alla copertura. Sotto specifiche condizioni (h dispari e uguali conteggi di qubit logici), l'azione logica di questi automorfismi è preservata.

Contributi Chiave e Risultati

• Generazione di Sequenze di Codici: Gli autori dimostrano che noti codici BB ad alte prestazioni, come il codice gross [[144, 12, 12]], possono essere visti come doppie coperture di codici più piccoli (ad esempio, [[72, 12, 6]]). Generano infinite sequenze di nuovi codici BB con conteggi di qubit logici ($k$) fissi e dimensioni di blocco ($n$) crescenti.
• Nuove Famiglie di Codici:
  • Codici di Peso 6: Il metodo riproduce famiglie note, inclusi i codici prodotto bilanciati e i codici torici generalizzati, e genera nuove sequenze per $k=6, 8, 10, 12$.
  • Codici di Peso 8: Gli autori applicano il metodo per cercare codici BB con controlli di peso 8 (4 termini nei polinomi definitori). Trovano sequenze con $k=8, 10, 12, 14$ che esibiscono rapporti $kd^2/n$ significativamente più alti rispetto alle loro controparti di peso 6. Esempi notevoli includono i codici [[64, 14, 8] e [[144, 14, 14]].
  • Codici Qudit: La metodologia è generalizzata per codici qudit su $\mathbb{F}_q$, generando con successo codici di copertura per codici BB qudit base.
• Limiti Teorici:
  • Qubit Logici ($k$): Gli autori dimostrano che per un codice di $h$-copertura con $h$ dispari, il numero di qubit logici soddisfa $k_h \ge k$. Conjetturano che questo valga per tutti gli $h$.
  • Distanza ($d$): Per $h$ dispari, dimostrano il limite superiore $d_h \le hd$. Se $k_h = k$ e $h$ è dispari, dimostrano il limite inferiore $d_h \ge d$. Conjetturano che il limite generale $d \le d_h \le hd$ valga per tutti gli $h$.
  • Lift Preservante il Peso: Mostrano che se esiste un lift preservante il peso, ciò implica $d_h \le d$, fornendo uno strumento numerico per escludere codici di copertura dove la distanza non aumenta.
• Analisi degli Operatori Logici e degli Automorfismi: Il documento fornisce costruzioni esplicite per il lifting di operatori logici e automorfismi. Dimostra che quando $h$ è dispari e $k_h = k$, la mappa di lifting è un isomorfismo sull'omologia, garantendo che una base logica del codice base si elevi a una base logica completa del codice di copertura, preservando l'azione logica degli automorfismi (ad esempio, i gate logici CNOT e Hadamard).

Significatività
L'articolo rivendica significatività in tre aree principali:

1. Scoperta Efficiente di Codici: Identificando uno spazio di ricerca ridotto basato sulla teoria dei grafi di copertura, gli autori forniscono un metodo sistematico ed efficiente per scoprire nuovi codici BB con parametri promettenti, evitando la necessità di ricerche brute-force su l'intero spazio polinomiale.
2. Unificazione Teorica: Il lavoro unifica varie costruzioni note di codici BB (inclusi il codice gross, i codici prodotto bilanciati e i codici torici generalizzati) sotto un unico framework di grafi di copertura, rivelando relazioni strutturali tra di essi.
3. Gestione degli Operatori Logici: Lo sviluppo di mappe di proiezione e di lifting offre uno strumento pratico per analizzare codici di grandi dimensioni. Derivando operatori logici e automorfismi da codici base più piccoli e ben compresi, la complessità della gestione delle operazioni logiche in grandi codici qLDPC viene ridotta.

Gli autori osservano che, sebbene l'attenzione sia sui codici BB, i metodi dovrebbero generalizzarsi ad altri codici di algebra di gruppo e costruzioni che coinvolgono ipergrafi o prodotti elevati (lifted products). Evidenziano inoltre che, sebbene lo spazio di ricerca sia ridotto, calcolare la distanza esatta di grandi codici di copertura rimane un collo di bottiglia, e i loro limiti teorici servono come guida piuttosto che come soluzione completa per il calcolo della distanza.