Multiple-Bases Belief Propagation List Decoding for Quantum LDPC Codes

Resumen Técnico: Decodificación por Lista de Propagación de Creencias con Múltiples Bases para Códigos Cuánticos LDPC

Enunciado del Problema
Los códigos de Paridad de Baja Densidad Cuántica (QLDPC) son críticos para la computación cuántica tolerante a fallos escalable debido a sus matrices de verificación de paridad dispersas, que minimizan las interacciones entre qubits. Sin embargo, el rendimiento de la decodificación estándar por Propagación de Creencias (BP) para códigos QLDPC a menudo se ve degradado por la degeneración del código, los ciclos cortos y los conjuntos de atrapamiento dentro del gráfico de Tanner. Aunque los decodificadores de alto rendimiento existentes, como BP con Decodificación por Estadísticas Ordenadas (BP-OSD) y Propagación de Creencias con Decimación Guiada (BPGD), ofrecen tasas de error mejoradas, adolecen de inconvenientes significativos: BP-OSD requiere una complejidad de post-procesamiento superlineal ($O(n^3)$), y BPGD implica un alto número de iteraciones y pasos de decimación complejos, lo que conduce a una mayor latencia y costo computacional. Existe la necesidad de una estrategia de decodificación que mejore el rendimiento de la tasa de error sobre la BP estándar, manteniendo una complejidad de tiempo lineal y evitando el post-procesamiento superlineal.

Metodología
El artículo propone el Decodificador por Lista de Propagación de Creencias con Múltiples Bases (MBBP-LD). Este marco extiende el concepto clásico de Propagación de Creencias con Múltiples Bases (MBBP) al entorno cuántico generando diversidad de decodificación estructurada sin depender de la selección aleatoria de filas ni de un post-procesamiento complejo.

1. Representaciones Redundantes Estructuradas: En lugar de duplicar aleatoriamente las filas de verificación de paridad (como en la decodificación de Paridad de Verificación Aumentada), el método propuesto construye múltiples representaciones redundantes de verificación de paridad utilizando descomposiciones de subárboles sin ciclos del gráfico de Tanner.

   • El algoritmo particiona los nodos de comprobación en una colección de subárboles maximales ($\mathcal{T}$) basándose en una permutación específica de los nodos de comprobación.
   • Un subárbol se define como maximal si añadir cualquier nodo de comprobación adyacente crearía un ciclo.
   • Para cada subárbol $t \in \mathcal{T}$, se forma una matriz de verificación de paridad aumentada $H^{(t)}$ adjuntando la submatriz correspondiente al subárbol ($H_t$) a la matriz original $H$.
   • El Lema 1 establece que para grafos regulares en comprobación, el número de filas adicionales introducidas está acotado, asegurando que la augmentación no aumente drásticamente la complejidad.

2. Decodificación Paralela y Agregación de Lista:

   • Múltiples decodificadores BP se ejecutan en paralelo, cada uno operando sobre una matriz aumentada distinta $H^{(t)}$.
   • Los decodificadores que convergen dentro de un límite de iteraciones fijo contribuyen con sus estimaciones de error a una lista de candidatos $\mathcal{L}$.

3. Regla de Decisión (Puntuación Ponderada por Frecuencia):

   • Una función de decisión $f_{DM}$ selecciona la estimación de error final de la lista de candidatos.
   • La regla propuesta de Puntuación Ponderada por Frecuencia (FWS) asigna una puntuación a cada candidato basándose en su frecuencia de aparición en la lista y su peso de Hamming:
     $$\text{Puntuación}(e) = \frac{|\{e' \in \mathcal{L} : e' = e\}|}{w_H(e) + 1}$$
   • Esta regla favorece a los candidatos que aparecen repetidamente (indicando robustez a través de diferentes estructuras de grafos) mientras penaliza los errores de alto peso. Si ningún decodificador converge, el sistema declara un fallo y devuelve el vector de todos los ceros.

Contribuciones Clave

• Diversidad Estructurada: El artículo introduce un método determinista basado en subárboles para construir representaciones redundantes de verificación de paridad, contrastando con los enfoques de augmentación aleatoria anteriores. Esta estructura está diseñada para inducir trayectorias de decodificación diversas que mitiguen los efectos de los conjuntos de atrapamiento.
• Preservación de la Complejidad: El marco mantiene la complejidad de tiempo lineal y la eficiencia de hardware de la BP estándar. Bajo una implementación paralela, la latencia de decodificación permanece comparable a la BP estándar, ya que el número de filas adicionales está acotado por un factor constante en relación con la longitud del bloque.
• Evitación de Post-procesamiento Superlineal: A diferencia de BP-OSD y BPGD, MBBP-LD evita etapas de decimación con sobrecarga de $O(n^3)$ o alta, ofreciendo una alternativa más eficiente para la implementación práctica.

Resultados Numéricos
Se realizaron simulaciones en códigos de bicicleta bivariados ($[[144, 12, 12]]$ y $[[288, 12, 18]]$) y en el código B1 ($[[882, 24, 18 \le d \le 24]]$) sobre un canal simétrico binario con errores de tipo X independientes.

• Ganancias de Rendimiento: MBBP-LD supera consistentemente a BP-OSD y BPGD en diversos regímenes de ruido.
  • Para el código $[[144, 12, 12]]$, logra una reducción del 3–24% en la Tasa de Error Lógico (LER) en comparación con BP-OSD y del 7–17% en comparación con BPGD.
  • Para el código $[[288, 12, 18]]$, las reducciones alcanzan hasta un 49% en comparación con BP-OSD y un 36% en comparación con BPGD.
  • Para el código B1 más grande, MBBP-LD logra una reducción superior al 91% en LER en comparación con BP-OSD en $p=0.04$ y hasta un 66% de reducción en comparación con BPGD paralelo.
• Eficiencia: Aunque BPGD-Serie a veces muestra una LER ligeramente mejor en regímenes de bajo ruido, incurre en costos computacionales significativamente mayores (por ejemplo, en $p=0.04$, BPGD-Serie promedia 2.5 iteraciones por etapa pero requiere decodificación repetida, mientras que MBBP-LD promedia 14.4 iteraciones totales). MBBP-LD mantiene un número de iteraciones comparable a la BP estándar, preservando una latencia similar a la BP.
• Subárbol vs. Aleatorio: Las comparaciones en el código $[[288, 12, 18]]$ muestran que las particiones basadas en subárboles producen consistentemente una LER más baja que las particiones aleatorias emparejadas, con mejoras que oscilan entre el 2.5% y el 9.4%, particularmente en regímenes de bajo ruido.

Significado y Afirmaciones
El artículo afirma que MBBP-LD cierra exitosamente la brecha entre el alto rendimiento de los decodificadores de post-procesamiento complejo y la eficiencia de la BP estándar. Al aprovechar las propiedades tipo árbol de las estructuras locales del gráfico para crear redundancia estructurada, el decodificador mejora la convergencia y las capacidades de corrección de errores sin sacrificar la complejidad de tiempo lineal esencial para la computación cuántica escalable. Los autores posicionan esto como una solución práctica que evita la sobrecarga superlineal de los métodos de alto rendimiento existentes mientras ofrece mejoras sustanciales en la tasa de error. Se señala que el trabajo futuro se centrará en construcciones específicas del código de verificaciones redundantes y reglas de decisión refinadas.