Reed-Solomon cuánticos: el cierre del curso

En la lección anterior llevaste la construcción CSS a los qudits: dos códigos clásicos sobre $\mathbb{F}_p$ con $C_2^\perp\subseteq C_1$ dan un código cuántico. Estamos en la última parada del relato. Empezamos con tres obstáculos que parecían insalvables, Shor los superó, los estabilizadores lo ordenaron todo y los códigos CSS convirtieron cada buen código clásico en una fábrica de códigos cuánticos. La pregunta de hoy: los códigos de Reed-Solomon tienen la mayor distancia posible para su longitud y su dimensión (son MDS). ¿Dan también los mejores códigos cuánticos?

La idea

La construcción CSS pide dos códigos con $C_2^\perp\subseteq C_1$. Lo más sencillo es tomar el mismo código dos veces: $C_1=C_2=C$, con la condición

$$C^\perp\subseteq C.$$

Entonces los estados lógicos son las clases laterales $\ket{x+C^\perp}$ con $x\in C$, y el número de qudits lógicos es $\dim C-\dim C^\perp=k-(n-k)=2k-n$.

Si $C$ es un Reed-Solomon $[n,k,n-k+1]$ que contiene a su dual (aquí $k$ es la dimensión del código clásico), sale un código cuántico

$$[[\,n,\ 2k-n,\ n-k+1\,]]_q .$$

Compáralo con la cota de Singleton cuántica de la lección 8, $n-k_Q\ge 2(d-1)$, donde $k_Q$ es el número de qudits lógicos. Aquí $n-(2k-n)=2(n-k)=2(d-1)$: se alcanza con igualdad. Un código así se llama MDS cuántico. El mejor código clásico da el mejor código cuántico.

Solo falta saber cuándo $C^\perp\subseteq C$. No se puede suponer: hay que comprobarlo.

Cuándo un Reed-Solomon contiene a su dual

Usamos la definición del curso de códigos: $\alpha$ genera los elementos no nulos de $\mathbb{F}_q$, $n=q-1$ y los puntos de evaluación son $1,\alpha,\dots,\alpha^{n-1}$, en ese orden. Escribimos $\mathrm{ev}(f)=(f(1),f(\alpha),\dots,f(\alpha^{n-1}))$. El código es $C=\{\mathrm{ev}(f):\deg f<k\}$, o sea, el cíclico con $g(x)=(x-\alpha)\cdots(x-\alpha^{n-k})$.

Repaso Sumar una potencia en todos los puntos

Sea $S=\sum_{a\neq0}a^m$, la suma sobre los $n=q-1$ elementos no nulos de $\mathbb{F}_q$. Si $n$ no divide a $m$, entonces $\alpha^m\neq1$. Multiplicar todos los $a$ por $\alpha$ solo los cambia de orden, así que $\alpha^mS=S$, y de ahí $S=0$. Si $n$ divide a $m$, cada término vale 1 y $S=n=q-1=-1$.

El producto escalar de dos evaluaciones de monomios es $\mathrm{ev}(x^i)\cdot\mathrm{ev}(x^j)=\sum_{a\neq0}a^{i+j}$, que vale 0 si $0<i+j<n$. Con $i\le k-1$ y $1\le j\le n-k$ la suma $i+j$ queda entre 1 y $n-1$. Por tanto los $n-k$ vectores $\mathrm{ev}(x),\dots,\mathrm{ev}(x^{n-k})$ son ortogonales a todo $C$, y como son independientes y $\dim C^\perp=n-k$:

$$C^\perp=\{\mathrm{ev}(b_1x+b_2x^2+\dots+b_{n-k}x^{n-k})\}.$$

Son los polinomios sin término independiente y de grado como mucho $n-k$. Estarán en $C$ si y solo si $n-k\le k-1$, es decir, si

$$2k>n .$$

Con $2k=n$ falla: $\mathrm{ev}(x^{k})$ está en $C^\perp$ pero no en $C$.

La distancia. Toda palabra de $C$ no nula pesa al menos $n-k+1$. Las de $C^\perp$ son evaluaciones de $x\,h(x)$ con $\deg h\le n-k-1$; como $0$ no es un punto de evaluación, tienen como mucho $n-k-1$ ceros y pesan al menos $k+1>n-k+1$. Así que las palabras de peso $n-k+1$ de $C$ (que existen, porque el Reed-Solomon es MDS) no están en $C^\perp$, y la distancia cuántica, el mínimo peso de $C\setminus C^\perp$, es exactamente $n-k+1$.

Estos son los códigos de Reed-Solomon cuánticos. Los introdujeron M. Grassl, W. Geiselmann y T. Beth en 1999, con Reed-Solomon sobre cuerpos $\mathbb{F}_{2^m}$ y escritos en cúbits: cada símbolo se desarrolla en $m$ cúbits. La versión directa con qudits de $q$ niveles, que da códigos MDS cuánticos, la estudiaron Grassl, Beth y Rötteler (2004). Encaja en la construcción CSS sobre $\mathbb{F}_q$ que recogen Ketkar, Klappenecker, Kumar y Sarvepalli (2006).

Ejemplo resuelto: el código $[[6,2,3]]_7$

Trabajamos en $\mathbb{F}_7$ (restos módulo 7). Las potencias de $\alpha=3$ son $1,3,2,6,4,5$: recorren los seis elementos no nulos. Tomamos $n=6$ y $k=4$, el Reed-Solomon $[6,4,3]$ con $g(x)=(x-3)(x-2)=x^2+2x+6$.

1. El dual. Como $n-k=2$, $C^\perp$ lo generan

$$\mathrm{ev}(x)=(1,3,2,6,4,5),\qquad \mathrm{ev}(x^2)=(1,2,4,1,2,4).$$

Comprobación con un producto: $\mathrm{ev}(x)\cdot\mathrm{ev}(x^2)=1+6+8+6+8+20=49\equiv0$. Estas dos filas forman la matriz de paridad $H$ de $C$. Y como $x$ y $x^2$ tienen grado menor que 4, también están en $C$: $C^\perp\subseteq C$.

2. Parámetros. $k_Q=4-2=2$ qudits lógicos y $d=6-4+1=3$. Es un $[[6,2,3]]_7$: corrige un error cualquiera en un qudit, o dos borrones. Singleton: $6-2=4=2(3-1)$. Es MDS cuántico.

3. Estabilizadores. Con $C_1=C_2=C$ son

$$X(132645),\quad X(124124),\quad Z(132645),\quad Z(124124).$$

Los dos $X$ conmutan entre sí, y los dos $Z$ también. Un $X(g)$ y un $Z(h)$ conmutan porque $g\cdot h=0$: $g\in C^\perp\subseteq C$ y $h\in C^\perp$. Son 4 generadores independientes en 6 qudits: $6-4=2$.

4. Estados lógicos. $C$ tiene $7^4$ palabras y $C^\perp$, $7^2$, así que hay $7^2=49$ clases laterales, una por cada pareja $(j,l)$ de $\mathbb{F}_7$. Un representante de cada una es la evaluación de $j+l\,x^3$, es decir $j\cdot111111+l\cdot161616$ (porque $\mathrm{ev}(x^3)=(1,6,1,6,1,6)$). Así:

$$\ket{j,l}_L=\frac{1}{7}\sum_{y\in C^\perp}\ket{\,j\cdot111111+l\cdot161616+y\,}.$$

El estado $\ket{0,0}_L$ es la suma de los 49 kets de $C^\perp$. En la tabla, la casilla de la fila $b_1$ y la columna $b_2$ es $b_1\,\mathrm{ev}(x)+b_2\,\mathrm{ev}(x^2)$, y cada casilla $x$ es un ket $\ket{x}$ de la suma, con coeficiente $1/7$:

$b_1 \,\backslash\, b_2$	0	1	2	3	4	5	6
0	000000	124124	241241	365365	412412	536536	653653
1	132645	256062	303116	420233	544350	661404	015521
2	264513	311630	435054	552101	606225	023342	140466
3	326451	443505	560622	614046	031163	155210	202334
4	451326	505443	622560	046614	163031	210155	334202
5	513264	630311	054435	101552	225606	342023	466140
6	645132	062256	116303	233420	350544	404661	521015

Es decir, $\ket{0,0}_L=\frac17\bigl(\ket{000000}+\ket{124124}+\ket{241241}+\cdots+\ket{521015}\bigr)$. Para $\ket{1,0}_L$ se suma 1 a cada cifra: $\frac17\bigl(\ket{111111}+\ket{235235}+\ket{352352}+\cdots\bigr)$. Clases distintas no comparten ningún ket, así que los 49 estados son ortonormales.

5. Operadores lógicos. $\bar X_1=X(111111)$ lleva $\ket{j,l}_L$ a $\ket{j+1,l}_L$, y $\bar X_2=X(161616)$ lleva $\ket{j,l}_L$ a $\ket{j,l+1}_L$. Para las fases, $\bar Z_1=Z(666666)$ cumple $\bar Z_1\ket{j,l}_L=\omega^j\ket{j,l}_L$: las cifras de $\mathrm{ev}(x)$ suman 21, las de $\mathrm{ev}(x^2)$, 14, y las de $161616$, 21, así que las de cada ket de $C^\perp$ y de $161616$ suman un múltiplo de 7, y las de $j\cdot111111$ suman $6j$, así que la fase es $\omega^{6\cdot6j}=\omega^{36j}=\omega^j$. Del mismo modo, $\bar Z_2=Z(616161)$ da $\omega^l$.

6. Un error y su síndrome. Un error $X^2$ en el qudit 3 es $X(e)$ con $e=(0,0,2,0,0,0)$. Medir $Z(h)$ sobre el estado dañado da el valor propio $\omega^{h\cdot e}$:

$$s_1=\mathrm{ev}(x)\cdot e=2\cdot2=4,\qquad s_2=\mathrm{ev}(x^2)\cdot e=4\cdot2=8\equiv1 .$$

Los $X(h)$ dan síndrome 0, porque los $X$ no ven un error $X$. Ahora llega el truco de Reed-Solomon. Un error de valor $a$ en el qudit del punto $P$ da $s=(aP,\ aP^2)$. Así que el punto es $P=s_2/s_1$ y el valor es $a=s_1/P$:

$$P=1\cdot4^{-1}=1\cdot2=2,\qquad a=4\cdot2^{-1}=4\cdot4=16\equiv2 .$$

El punto 2 es $\alpha^2$, el qudit 3, con valor 2. Se corrige aplicando $X(e)^{-1}$, es decir $X^5$ en el qudit 3. Un error $Z$ lo detectan los $X(h)$ del mismo modo (con valor propio $\omega^{-h\cdot e}$, por el signo del producto simpléctico). Los $6\cdot48=288$ errores de un solo qudit dan 288 síndromes distintos y no nulos, de los $7^4=2401$ posibles.

Fíjate en que es el mismo código clásico $[6,4,3]$ usado dos veces: una contra los $X$ y otra contra los $Z$. En el curso de códigos los Reed-Solomon se decodificaban a partir de los símbolos recibidos (Decodificar Reed-Solomon y Corregir errores en Reed-Solomon). Aquí solo se dispone del síndrome. Es justo el punto de partida de decodificadores como Berlekamp-Massey, que se mencionan en la segunda de esas lecciones.

Sobre $\mathbb{F}_8$: el código $[[7,1,4]]_8$

El ejercicio 2 de la lección Códigos de Reed-Solomon usaba el $[7,4,4]$ sobre $\mathbb{F}_8=\mathbb{F}_2[x]/(x^3+x+1)$, con $\alpha^3=\alpha+1$. Aquí $n=7$, $k=4$ y $2k=8>7$: su dual, generado por $\mathrm{ev}(x),\mathrm{ev}(x^2),\mathrm{ev}(x^3)$, está dentro. Sale un

$$[[7,\ 1,\ 4]]_8,\qquad 7-1=6=2(4-1),$$

otro MDS cuántico. Cada qudit tiene 8 niveles, uno por elemento de $\mathbb{F}_8$. Como en el párrafo de la lección 12, $X(a)\ket{x}=\ket{x+a}$ y $Z(b)\ket{x}=\omega^{\operatorname{Tr}(b\cdot x)}\ket{x}$, con $\omega=-1$ (porque $p=2$) y la traza del cuerpo $\operatorname{Tr}(c)=c+c^2+c^4$, que vale 0 o 1. Los estabilizadores son $X(g)$ y $Z(h)$ con $g,h\in C^\perp$, y hay un qudit lógico de 8 niveles:

$$\ket{j_L}=\frac{1}{\sqrt{512}}\sum_{y\in C^\perp}\ket{\,j\cdot1111111+y\,},\qquad j\in\mathbb{F}_8 .$$

Cada uno es una suma de 512 kets; $\bar X=X(a\cdot1111111)$ suma $a$ a $j$, y $Z(b\cdot1111111)\ket{j_L}=(-1)^{\operatorname{Tr}(bj)}\ket{j_L}$, porque $7=1$ en $\mathbb{F}_8$ y las coordenadas de cada $y\in C^\perp$ suman 0 (por el repaso de arriba). Corrige un error en cualquiera de los 7 qudits, o hasta 3 borrones.

El relato completo y lo que viene

A mediados de los 90 parecía imposible proteger un cúbit: no se puede copiar, los errores son continuos y mirar destruye el estado. Shor (1995) respondió a los tres a la vez con 9 cúbits, y el formalismo de estabilizadores (Gottesman, 1996; su tesis, de 1997, lo expone entero) convirtió su truco en una teoría con síndromes, como la del curso de códigos. Con los códigos CSS (Calderbank y Shor, y Steane, 1996) cada par de códigos clásicos encajados da uno cuántico, y hoy has visto que los Reed-Solomon dan códigos cuánticos MDS, los de mayor distancia posible para su tamaño.

Lo que queda fuera del curso:

• El código de 5 cúbits $[[5,1,3]]$ (lo citamos en la lección 8): es el más pequeño que protege un cúbit lógico contra un error arbitrario en un cúbit, porque con $k=1$ y $d=3$ la cota de Singleton cuántica obliga a $n\ge5$. No es CSS.
• Los códigos de superficie: cúbits en una cuadrícula y estabilizadores que solo tocan vecinos. Son la base de experimentos recientes como el de Google Quantum AI, «Quantum error correction below the surface code threshold» (Nature 638, 2025; publicado en línea en diciembre de 2024), en el que al agrandar el código bajó el error del cúbit lógico.
• El umbral de error: si cada operación física falla con una probabilidad por debajo de un valor fijo (y el ruido cumple unas hipótesis razonables), se puede calcular tanto tiempo como se quiera con un error final tan pequeño como se desee (Gottesman, 2009, lo explica). Ahí está la frontera entre un cúbit lógico útil y uno que no lo es.

Para seguir: la guía de computación cuántica y, si te quedaste con ganas de Reed-Solomon, el curso de códigos correctores.

Ejercicios

Ejercicio 1

Con $\mathbb{F}_7$, $n=6$ y $k=5$: ¿contiene el Reed-Solomon a su dual? ¿Qué parámetros tiene el código cuántico? ¿Y con $k=3$?

Ver la solución

Con $k=5$, $2k=10>6$: sí. Su dual es $\{\mathrm{ev}(b_1x)\}$, generado por $(1,3,2,6,4,5)$, que tiene grado $1<5$. Sale un $[[6,\ 2\cdot5-6,\ 6-5+1]]_7=[[6,4,2]]_7$: cuatro qudits lógicos, detecta un error (no lo corrige) o corrige un borrón. También es MDS: $6-4=2=2(2-1)$.

Con $k=3$, $2k=6=n$: no. El dual contiene $\mathrm{ev}(x^3)=(1,6,1,6,1,6)$, que no es evaluación de ningún polinomio de grado menor que 3.

Ejercicio 2

En el $[[6,2,3]]_7$ del ejemplo, los estabilizadores $Z(132645)$ y $Z(124124)$ dan el síndrome $(s_1,s_2)=(6,3)$ y los $X$ dan $(0,0)$. ¿Qué error se produjo y cómo se corrige?

Ver la solución

Los $X$ no detectan nada, así que es un error $X^a$ en un qudit. El punto es $P=s_2/s_1=3\cdot6^{-1}=3\cdot6=18\equiv4$ (porque $6\cdot6=36\equiv1$). El valor es $a=s_1/P=6\cdot4^{-1}=6\cdot2=12\equiv5$.

El punto 4 es $\alpha^4$, el qudit 5. El error es $X^5$ en el qudit 5. Comprobación: $s=(5\cdot4,\ 5\cdot16)=(20,80)\equiv(6,3)$. Se corrige con $X^{-5}=X^2$ en el qudit 5.

Ejercicio 3

El ejercicio 3 de la lección Códigos de Reed-Solomon usaba el $[255,223,33]$ sobre $\mathbb{F}_{256}$. ¿Contiene a su dual? ¿Qué código cuántico da, cuántos errores corrige y qué tasa $k_Q/n$ tiene?

Ver la solución

$2k=446>255$, así que sí. Da un $[[255,\ 2\cdot223-255,\ 33]]_{256}=[[255,191,33]]_{256}$, que corrige $\lfloor32/2\rfloor=16$ errores en qudits de 256 niveles. Su tasa es $191/255\approx74{,}9\,\%$, frente al $87{,}5\,\%$ del código clásico: proteger contra $X$ y contra $Z$ a la vez cuesta el doble de redundancia, $2(n-k)=64$ en lugar de 32.

En resumen

• Con $C_1=C_2=C$ y $C^\perp\subseteq C$, la construcción CSS da $2k-n$ qudits lógicos, con estados $\ket{x+C^\perp}$.
• Un Reed-Solomon de longitud $n=q-1$ contiene a su dual si y solo si $2k>n$: el dual son las evaluaciones de los polinomios sin término independiente de grado como mucho $n-k$.
• Sale un $[[n,2k-n,n-k+1]]_q$ que alcanza la cota de Singleton cuántica: es MDS cuántico.
• Ejemplos: $[[6,2,3]]_7$ (corrige un error y lee su posición en el síndrome) y $[[7,1,4]]_8$.
• El curso termina donde empieza la ingeniería: código de 5 cúbits, códigos de superficie y el umbral.

Fin del curso. Has recorrido el camino desde «no se sabe si es posible» hasta los Reed-Solomon cuánticos. Vuelve al índice del curso cuando quieras repasar.