Multiple-Bases Belief Propagation List Decoding for Quantum LDPC Codes

Sintesi Tecnica: Decodifica a Lista con Propagazione delle Credenze su Multiple Basi per Codici LDPC Quantistici

Enunciato del Problema
I codici Quantistici a Parità Controllata a Bassa Densità (QLDPC) sono fondamentali per il calcolo quantistico tollerante ai guasti scalabile grazie alle loro matrici di controllo di parità sparse, che minimizzano le interazioni tra i qubit. Tuttavia, le prestazioni della decodifica standard con Propagazione delle Credenze (BP) per i codici QLDPC sono spesso degradate dalla degenerazione del codice, dai cicli brevi e dagli insiemi di intrappolamento all'interno del grafo di Tanner. Sebbene i decodificatori ad alte prestazioni esistenti, come BP con Decodifica per Statistiche Ordinate (BP-OSD) e Propagazione delle Credenze con Decimazione Guidata (BPGD), offrano tassi di errore migliorati, essi soffrono di svantaggi significativi: BP-OSD richiede una complessità di post-elaborazione super-lineare ($O(n^3)$), mentre BPGD comporta un alto numero di iterazioni e passaggi di decimazione complessi, portando a una maggiore latenza e costo computazionale. È necessaria una strategia di decodifica che migliori le prestazioni in termini di tasso di errore rispetto alla BP standard, mantenendo al contempo una complessità lineare nel tempo ed evitando un post-elaborazione super-lineare.

Metodologia
Il documento propone il Decodificatore a Lista con Propagazione delle Credenze su Multiple Basi (MBBP-LD). Questo framework estende il concetto classico di Propagazione delle Credenze su Multiple Basi (MBBP) all'ambito quantistico generando una diversità strutturata di decodifica senza fare affidamento sulla selezione casuale di righe o su un post-elaborazione complessa.

1. Rappresentazioni Ridondanti Strutturate: Invece di duplicare casualmente le righe di controllo di parità (come nella decodifica a Parità Controllata Aumentata), il metodo proposto costruisce multiple rappresentazioni ridondanti di controllo di parità utilizzando decomposizioni ad albero privo di cicli del grafo di Tanner.

   • L'algoritmo partiziona i nodi di controllo in una collezione di sottografi massimali privi di cicli ($\mathcal{T}$) basata su una specifica permutazione dei nodi di controllo.
   • Un sottografo è definito massimale se l'aggiunta di qualsiasi nodo di controllo adiacente creerebbe un ciclo.
   • Per ogni sottografo $t \in \mathcal{T}$, viene formata una matrice di controllo di parità aumentata $H^{(t)}$ aggiungendo alla matrice originale $H$ la sottomatrice corrispondente al sottografo ($H_t$).
   • Il Lemma 1 stabilisce che per grafi regolari nei nodi di controllo, il numero di righe aggiuntive introdotte è limitato, garantendo che l'aumento non incrementi drasticamente la complessità.

2. Decodifica Parallela e Aggregazione della Lista:

   • Multipli decodificatori BP eseguono in parallelo, ciascuno operando su una distinta matrice aumentata $H^{(t)}$.
   • I decodificatori che convergono entro un limite fisso di iterazioni contribuiscono con le loro stime di errore a una lista di candidati $\mathcal{L}$.

3. Regola di Decisione (Punteggio Ponderato per Frequenza):

   • Una funzione di decisione $f_{DM}$ seleziona la stima di errore finale dalla lista di candidati.
   • La proposta Regola di Punteggio Ponderato per Frequenza (FWS) assegna un punteggio a ciascun candidato basato sulla sua frequenza di occorrenza nella lista e sul suo peso di Hamming:
     $$\text{Punteggio}(e) = \frac{|\{e' \in \mathcal{L} : e' = e\}|}{w_H(e) + 1}$$
   • Questa regola favorisce i candidati che appaiono ripetutamente (indicando robustezza attraverso diverse strutture di grafo) mentre penalizza gli errori ad alto peso. Se nessun decodificatore converge, il sistema dichiara un fallimento e restituisce il vettore tutto-zero.

Contributi Chiave

• Diversità Strutturata: Il documento introduce un metodo deterministico basato su sottografi per costruire rappresentazioni ridondanti di controllo di parità, in contrasto con i precedenti approcci di aumento casuale. Questa struttura è progettata per indurre traiettorie di decodifica diverse che mitigano gli effetti degli insiemi di intrappolamento.
• Preservazione della Complessità: Il framework mantiene la complessità lineare nel tempo e l'efficienza hardware della BP standard. Nell'implementazione parallela, la latenza di decodifica rimane paragonabile alla BP standard, poiché il numero di righe aggiuntive è limitato da un fattore costante rispetto alla lunghezza del blocco.
• Evitamento di Post-Elaborazione Super-Lineare: A differenza di BP-OSD e BPGD, MBBP-LD evita stadi di post-elaborazione $O(n^3)$ o ad alto sovraccarico di decimazione, offrendo un'alternativa più efficiente per l'implementazione pratica.

Risultati Numerici
Le simulazioni sono state condotte su codici a bicicletta bivariati ($[[144, 12, 12]]$ e $[[288, 12, 18]]$) e sul codice B1 ($[[882, 24, 18 \le d \le 24]]$) su un canale simmetrico binario con errori di tipo X indipendenti.

• Miglioramenti delle Prestazioni: MBBP-LD supera costantemente BP-OSD e BPGD in vari regimi di rumore.
  • Per il codice $[[144, 12, 12]]$, ottiene una riduzione del 3–24% nel Tasso di Errore Logico (LER) rispetto a BP-OSD e del 7–17% rispetto a BPGD.
  • Per il codice $[[288, 12, 18]]$, le riduzioni raggiungono fino al 49% rispetto a BP-OSD e al 36% rispetto a BPGD.
  • Per il codice B1 più grande, MBBP-LD ottiene una riduzione del LER superiore al 91% rispetto a BP-OSD a $p=0.04$ e fino al 66% rispetto a BPGD parallelo.
• Efficienza: Sebbene BPGD-Serial mostri talvolta un LER leggermente migliore in regimi a basso rumore, sostiene costi computazionali significativamente più alti (ad esempio, a $p=0.04$, BPGD-Serial media 2,5 iterazioni per stadio ma richiede decodifiche ripetute, mentre MBBP-LD media 14,4 iterazioni totali). MBBP-LD mantiene un numero di iterazioni paragonabile alla BP standard, preservando una latenza simile a quella della BP.
• Sottografi vs. Casuale: I confronti sul codice $[[288, 12, 18]]$ mostrano che le partizioni basate su sottografi producono costantemente un LER inferiore rispetto alle partizioni casuali corrispondenti, con miglioramenti che vanno dal 2,5% al 9,4%, in particolare nei regimi a basso rumore.

Significato e Affermazioni
Il documento afferma che MBBP-LD colma con successo il divario tra le alte prestazioni dei decodificatori con post-elaborazione complessa e l'efficienza della BP standard. Sfruttando le proprietà simili a quelle degli alberi delle strutture locali del grafo per creare ridondanza strutturata, il decodificatore migliora la convergenza e le capacità di correzione degli errori senza sacrificare la complessità lineare nel tempo essenziale per il calcolo quantistico scalabile. Gli autori lo posizionano come una soluzione pratica che evita il sovraccarico super-lineare dei metodi ad alte prestazioni esistenti, fornendo al contempo sostanziali miglioramenti nei tassi di errore. Si nota che il lavoro futuro si concentrerà su costruzioni specifiche per il codice di controlli ridondanti e regole di decisione raffinate.