Códigos CSS sobre cuerpos finitos: códigos cuánticos para qudits

En la lección anterior cambiamos el cúbit por un qudit de $p$ niveles y vimos que el código de 3 cútrits $\langle XXX, ZZZ\rangle$ funciona justo porque $1+1+1\equiv 0 \pmod 3$. Y en la lección 9 aprendimos a fabricar un código cuántico con dos códigos binarios. Hoy juntamos las dos ideas. El relato iba así: se dudaba de que fuera posible, Shor lo hizo con 9 cúbits y Calderbank, Shor y Steane enseñaron a construir códigos cuánticos con códigos clásicos. Ahora damos el paso que lleva al final del curso: ¿funciona la receta CSS con códigos sobre $\mathbb{F}_p$? Funciona casi palabra por palabra, y abre la puerta a usar cualquier código lineal del curso de códigos para proteger qudits.

La idea

En la versión binaria había dos códigos. Uno vigilaba los errores $X$ (los cambios de bit) y el otro los errores $Z$ (los cambios de fase). La única condición era que las comprobaciones de los dos tipos conmutaran, y eso se traducía en una inclusión entre códigos: $C_2^\perp\subseteq C_1$.

Con qudits pasa lo mismo. Un error $X^a$ en un qudit suma $a$ al símbolo, como un error de valor $a$ en un código clásico sobre $\mathbb{F}_p$. Un error $Z^b$ multiplica por una fase que depende del símbolo. Las comprobaciones de tipo $Z$ leen los errores $X$ con la matriz de paridad de $C_1$; las de tipo $X$ leen los errores $Z$ con la de $C_2$. Lo único nuevo son los coeficientes: ahora un error tiene posición y valor, y aparecen algunos signos menos.

Repaso Producto escalar y dual sobre F_p

Para $u,v\in\mathbb{F}_p^n$, el producto escalar es $u\cdot v=u_1v_1+\dots+u_nv_n$ calculado módulo $p$. El dual de un código $C$ es $C^\perp=\{v: v\cdot c=0 \text{ para toda } c\in C\}$ y tiene dimensión $n-\dim C$. Las filas de una matriz de paridad de $C$ generan $C^\perp$ (lección del curso de códigos). Sobre $\mathbb{F}_p$ un vector puede ser ortogonal a sí mismo: $(1,1,1)\cdot(1,1,1)=3=0$ en $\mathbb{F}_3$.

Los ingredientes

Trabajamos con $n$ qudits de $p$ niveles, $p$ primo, y $\omega=e^{2\pi i/p}$. Para vectores $a,b\in\mathbb{F}_p^n$:

$$X(a)\ket{x}=\ket{x+a},\qquad Z(b)\ket{x}=\omega^{\,b\cdot x}\ket{x}.$$

Es decir, $X(a)=X^{a_1}\otimes\cdots\otimes X^{a_n}$ suma el vector $a$ y $Z(b)=Z^{b_1}\otimes\cdots\otimes Z^{b_n}$ pone la fase $\omega^{b\cdot x}$. La regla de conmutación es:

$$Z(b)X(a)\ket{x}=\omega^{\,b\cdot(x+a)}\ket{x+a}=\omega^{\,b\cdot a}\,X(a)Z(b)\ket{x}.$$

Así que $X(a)$ y $Z(b)$ conmutan si y solo si $a\cdot b=0$. Es el producto simpléctico de la lección anterior aplicado a $(a\mid 0)$ y $(0\mid b)$.

La construcción CSS sobre $\mathbb{F}_p$

Toma dos códigos lineales $C_1, C_2\subseteq\mathbb{F}_p^n$ con

$$C_2^\perp\subseteq C_1 .$$

Sea $H_1$ una matriz de paridad de $C_1$ (sus filas generan $C_1^\perp$) y $H_2$ una de $C_2$ (sus filas generan $C_2^\perp$). Los estabilizadores son:

• $Z(h)$ para cada fila $h$ de $H_1$: detectan los errores $X$;
• $X(g)$ para cada fila $g$ de $H_2$: detectan los errores $Z$.

Dos de tipo $Z$ conmutan siempre, y dos de tipo $X$ también. Un $X(g)$ y un $Z(h)$ conmutan porque $g\in C_2^\perp\subseteq C_1$ y $h\in C_1^\perp$, así que $g\cdot h=0$. Esa es toda la razón de la condición $C_2^\perp\subseteq C_1$.

Hay $(n-\dim C_1)+\dim C_2^\perp$ generadores, así que el código guarda

$$k=n-\big[(n-\dim C_1)+\dim C_2^\perp\big]=\dim C_1-\dim C_2^\perp$$

qudits lógicos. Si $C_1$ y $C_2$ tienen parámetros $[n,k_1]_p$ y $[n,k_2]_p$, sale $k=k_1+k_2-n$.

Estados lógicos: uno por clase lateral

Para cada $x\in C_1$ definimos

$$\ket{x+C_2^\perp}=\frac{1}{\sqrt{|C_2^\perp|}}\sum_{y\in C_2^\perp}\ket{x+y}.$$

Es la suma de todas las palabras de la clase lateral $x+C_2^\perp$, la misma idea de la decodificación por síndrome. Las comprobaciones de la lección 9 valen igual: $X(g)$ solo reordena la suma; $Z(h)$ da la fase $\omega^{h\cdot(x+y)}=\omega^0=1$, porque $x+y\in C_1$ y $h\in C_1^\perp$; y el estado depende solo de la clase. Dos clases distintas no comparten ningún ket, así que sus estados son ortogonales.

Hay $|C_1|/|C_2^\perp|=p^{\dim C_1-\dim C_2^\perp}=p^k$ clases: justo la dimensión del código. Si $k=1$, se elige $\bar x\in C_1$ fuera de $C_2^\perp$ y se llama $\ket{j_L}=\ket{j\bar x+C_2^\perp}$. Entonces $\bar X=X(\bar x)$ cumple $\bar X\ket{j_L}=\ket{j+1_L}$. Para $\bar Z$ basta un $\bar z\in C_2$ con $\bar z\cdot\bar x=1$: como $\bar z\cdot y=0$ para todo $y\in C_2^\perp$, se tiene $\bar Z\ket{j_L}=Z(\bar z)\ket{j_L}=\omega^{j}\ket{j_L}$.

Síndromes y distancia

Un error $E=X(a)Z(b)$ tiene vector $(a\mid b)$. Con el producto simpléctico del curso, $\langle (u\mid v),(a\mid b)\rangle_s=v\cdot a-u\cdot b$:

• el estabilizador $Z(h)$, de vector $(0\mid h)$, da $s=h\cdot a$: es el síndrome clásico $H_1a^T$ de la parte $X$ del error;
• el estabilizador $X(g)$, de vector $(g\mid 0)$, da $s=-g\cdot b$: es menos el síndrome clásico $H_2b^T$ de la parte $Z$.

Al medir el generador sale el valor propio $\omega^{s}$. En binario el signo menos no se nota; sobre $\mathbb{F}_3$ sí.

La distancia es el menor peso de un error indetectable que no sea un estabilizador. Para un código CSS,

$$d=\min\{\mathrm{wt}(c): c\in (C_1\setminus C_2^\perp)\cup(C_2\setminus C_1^\perp)\},$$

y en particular $d\ge\min(d(C_1),d(C_2))$. Es el lema de la construcción CSS de Ketkar, Klappenecker, Kumar y Sarvepalli (2006), que lo enuncian para cualquier $\mathbb{F}_q$. Un artículo de referencia sobre códigos estabilizadores no binarios, sobre cualquier $\mathbb{F}_q$, es el de Ashikhmin y Knill (2001).

El código de 3 cútrits, releído

Toma $p=3$, $C_2^\perp=\langle 111\rangle$ y $C_1=\langle 111\rangle^\perp=\{x: x_1+x_2+x_3=0\}$. Como $(1,1,1)\cdot(1,1,1)=3=0$, se cumple $C_2^\perp\subseteq C_1$. Aquí $C_2=C_1$, y la única fila de $H_1$ y de $H_2$ es $(1,1,1)$: los estabilizadores son $Z(111)=ZZZ$ y $X(111)=XXX$. Y $k=2-1=1$.

$C_1$ tiene 9 palabras, repartidas en 3 clases de $\langle 111\rangle$. Con $\bar x=(0,1,2)$:

$$\ket{0_L}=\tfrac{1}{\sqrt3}\big(\ket{000}+\ket{111}+\ket{222}\big),\quad \ket{1_L}=\tfrac{1}{\sqrt3}\big(\ket{012}+\ket{120}+\ket{201}\big),\quad \ket{2_L}=\tfrac{1}{\sqrt3}\big(\ket{021}+\ket{102}+\ket{210}\big).$$

Son exactamente los de la lección 11. La receta da $\bar X=X(\bar x)=X_2X_3^2$, pero en la lección 11 usamos $X_1X_2^2=X(1,2,0)$. Las dos sirven: $(1,2,0)=(0,1,2)+(1,1,1)$ está en la misma clase, así que los dos operadores solo difieren en el estabilizador $XXX$ y hacen lo mismo sobre el código, $\ket{j_L}\mapsto\ket{j+1_L}$. Nos quedamos con los de la lección 11: $\bar X=X_1X_2^2$ y $\bar Z=Z(2,1,0)=Z_1^2Z_2$, que vale porque $(2,1,0)\in C_2$ y $(2,1,0)\cdot(0,1,2)=1$. La distancia es 2: $(1,2,0)$ está en $C_1$, no en $\langle 111\rangle$ y pesa 2.

Ejemplo resuelto: el Hamming ternario

El código de Steane nacía del Hamming binario. Su primo ternario es el código de Hamming $[13,10,3]_3$: su matriz de paridad tiene como columnas un representante de cada recta de $\mathbb{F}_3^3$ (el primer símbolo no nulo es 1). Hay $(27-1)/2=13$:

$$H=\begin{pmatrix} 0&0&0&0&1&1&1&1&1&1&1&1&1\\ 0&1&1&1&0&0&0&1&1&1&2&2&2\\ 1&0&1&2&0&1&2&0&1&2&0&1&2 \end{pmatrix}.$$

Ninguna columna es nula ni múltiplo de otra, así que $d\ge3$, y la columna 3 es la suma de la 1 y la 2, así que $d=3$.

Paso 1: ¿contiene a su dual? Las filas de $H$ generan $C^\perp$, el código símplex $[13,3]$. Basta comprobar que las filas son ortogonales entre sí y consigo mismas. Con enteros, los productos son $9$, $18$ y $21$ (cada fila consigo misma) y $9$, $9$ y $12$ (las parejas): todos múltiplos de 3. Así que $C^\perp\subseteq C$. (De hecho, las 26 palabras no nulas de $C^\perp$ pesan 9.)

Paso 2: el código cuántico. Tomamos $C_1=C_2=C$ y $H_1=H_2=H$. Los seis generadores son $Z(h_1),Z(h_2),Z(h_3)$ y $X(h_1),X(h_2),X(h_3)$, con $h_i$ las filas de $H$. Por ejemplo, $Z(h_1)=Z_5Z_6\cdots Z_{13}$ y $X(h_3)=X_1X_3X_4^2X_6X_7^2X_9X_{10}^2X_{12}X_{13}^2$. Queda

$$k=\dim C-\dim C^\perp=10-3=7.$$

Las palabras de $C\setminus C^\perp$ pesan al menos 3 y hay alguna de peso 3. Por tanto es un $[[13,7,3]]_3$: 7 cútrits lógicos en 13 físicos, y corrige cualquier error en un cútrit. Ketkar et al. obtienen así toda una familia a partir de los Hamming que contienen a su dual.

Paso 3: estados lógicos. Hay $3^7=2187$ clases, cada una con 27 kets. El de todo ceros es

$$\ket{0\cdots0_L}=\frac{1}{\sqrt{27}}\sum_{y\in C^\perp}\ket{y},$$

con términos como $\ket{0000000000000}$ o $\ket{0000111111111}$ (la fila $h_1$). Para el primer cútrit lógico tomamos $\bar x=(1,1,2,0,\dots,0)$, que está en $C$ porque la columna 1 más la 2 más dos veces la 3 da $(0,3,3)=0$. Y $\bar z=(1,0,0,0,1,2,0,\dots,0)$, que también está en $C$ y cumple $\bar z\cdot\bar x=1$. Así, $\bar X=X_1X_2X_3^2$ y $\bar Z=Z_1Z_5Z_6^2$ son lógicos de peso 3, y $\ket{j_L}=\ket{j\bar x+C^\perp}$ (con los otros seis cútrits lógicos a 0).

Paso 4: un error y su síndrome. Sobre el cútrit 6 actúa $E=X^2Z$, es decir, $a=2e_6$ y $b=e_6$. La columna 6 es $(1,0,1)$.

• Generadores de tipo $Z$: $s=H a^T=2\cdot(1,0,1)=(2,0,2)$.
• Generadores de tipo $X$: $s=-H b^T=-(1,0,1)=(2,0,2)$.

Se miden los valores propios $\omega^2,1,\omega^2$ y otra vez $\omega^2,1,\omega^2$.

Paso 5: leer el síndrome. Como en el Hamming binario, el síndrome señala la columna, pero ahora además da el valor. En $(2,0,2)$ el primer símbolo no nulo es 2: el error $X$ tiene valor $a=2$ y está en la columna $(2,0,2)/2=(1,0,1)$, la 6. En la otra mitad, $-b\cdot(\text{columna})=(2,0,2)$ da $b=1$ y otra vez la columna 6. Se aplica $E^{-1}=(X^2Z)^{-1}$ al cútrit 6 y el estado vuelve a ser el original.

Los 104 errores de peso 1 ($13$ posiciones por $8$ errores no triviales) dan 104 síndromes no nulos y distintos.

Más allá de los primos: $q=p^m$

La lección 13 necesita $\mathbb{F}_8$, así que conviene saber qué cambia cuando $q=p^m$. Cada símbolo de $\mathbb{F}_q$ es ahora un qudit de $q$ niveles, con base $\ket{x}$ para $x\in\mathbb{F}_q$, y $X(a)\ket{x}=\ket{x+a}$ suma en $\mathbb{F}_q$. Pero $\omega^{b\cdot x}$ ya no tiene sentido, porque $b\cdot x$ es un elemento de $\mathbb{F}_q$ y no un número entre $0$ y $p-1$. La solución es la traza del cuerpo (no la de una matriz) $\operatorname{Tr}(c)=c+c^p+c^{p^2}+\dots+c^{p^{m-1}}$, que lleva $\mathbb{F}_q$ a $\mathbb{F}_p$ y respeta la suma. Se define $Z(b)\ket{x}=\omega^{\operatorname{Tr}(b\cdot x)}\ket{x}$, con $\omega=e^{2\pi i/p}$ (en $\mathbb{F}_8$, $\omega=-1$). Es el convenio de Ketkar et al. La condición CSS sigue siendo $C_2^\perp\subseteq C_1$ con el producto escalar usual de $\mathbb{F}_q$: si $g\cdot h=0$, entonces $\operatorname{Tr}(g\cdot h)=0$ y $X(g)$, $Z(h)$ conmutan. Un detalle: los estabilizadores son ahora $X(g)$ y $Z(h)$ para todos los $g\in C_2^\perp$ y $h\in C_1^\perp$, no solo para las filas de las matrices de paridad, porque un múltiplo $\beta g$ con $\beta\in\mathbb{F}_q$ fuera de $\mathbb{F}_p$ no es una potencia de $X(g)$. El código sigue teniendo $k=\dim C_1-\dim C_2^\perp$, ahora contando qudits de $q$ niveles.

Ejercicios

Ejercicio 1

¿Sirve $C_2^\perp=\langle 1111\rangle$, $C_1=\langle1111\rangle^\perp$ sobre $\mathbb{F}_3$? ¿Y $C_2^\perp=\langle 11111\rangle$, $C_1=\langle11111\rangle^\perp$ sobre $\mathbb{F}_5$? En el caso que funcione, da $k$ y $d$.

Ver la solución

Sobre $\mathbb{F}_3$, $(1,1,1,1)\cdot(1,1,1,1)=4=1\neq0$, así que $(1,1,1,1)\notin C_1$ y no se cumple $C_2^\perp\subseteq C_1$: $X(1111)$ y $Z(1111)$ no conmutan.

Sobre $\mathbb{F}_5$, $(1,1,1,1,1)\cdot(1,1,1,1,1)=5=0$: sí funciona. $C_1=\{x: x_1+\dots+x_5=0\}$ tiene dimensión 4, así que $k=4-1=3$. Ninguna palabra de peso 1 suma cero, pero $(1,4,0,0,0)$ sí, y no está en $\langle11111\rangle$. Como $C_2=C_1$, $d=2$: es un $[[5,3,2]]_5$, el hermano del código de 3 cútrits.

Ejercicio 2

El tetracódigo $T\subseteq\mathbb{F}_3^4$, de matriz generatriz con filas $(1,0,1,1)$ y $(0,1,1,2)$, cumple $T^\perp=T$. ¿Qué código cuántico da con $C_1=C_2=T$? Escribe su estado.

Ver la solución

Como $T^\perp=T$, se cumple $C_2^\perp=T\subseteq T=C_1$, pero $k=\dim T-\dim T^\perp=2-2=0$. No guarda ningún cútrit: es un $[[4,0]]_3$, un único estado fijado por los cuatro generadores $X(1011)$, $X(0112)$, $Z(1011)$ y $Z(0112)$. Hay una sola clase lateral, la del 0:

$$\tfrac13\big(\ket{0000}+\ket{1011}+\ket{2022}+\ket{0112}+\ket{0221}+\ket{1120}+\ket{2210}+\ket{1202}+\ket{2101}\big).$$

Por ejemplo, $(1,0,1,1)+2(0,1,1,2)=(1,2,3,5)=(1,2,0,2)$. Para guardar información hace falta que $C_2^\perp$ sea estrictamente menor que $C_1$, como en el Hamming $[13,10,3]_3$.

Ejercicio 3

En el $[[13,7,3]]_3$ del ejemplo: (a) halla el síndrome de $Z_9^2$ y comprueba que se lee bien; (b) ocurre $X_2X_5$. ¿Qué hace el decodificador de peso mínimo?

Ver la solución

(a) La parte $X$ del error es nula, así que los generadores de tipo $Z$ dan $(0,0,0)$. Con $b=2e_9$ y la columna 9, $(1,1,1)$, los de tipo $X$ dan $-2\cdot(1,1,1)=(1,1,1)$. Entonces $-b\cdot(\text{columna})=(1,1,1)$, es decir, $b\cdot(\text{columna})=(2,2,2)=2\cdot(1,1,1)$: valor $b=2$ en la columna 9. Se corrige con $Z_9^{-2}=Z_9$.

(b) Los generadores de tipo $Z$ dan la suma de las columnas 2 y 5: $(0,1,0)+(1,0,0)=(1,1,0)$, que es la columna 8. El decodificador cree que hubo un $X_8$ y aplica $X_8^{-1}=X_8^2$. En total queda $X_2X_5X_8^2$, de vector $(0,1,0,0,1,0,0,2,0,0,0,0,0)$. Está en $C$ (columna 2 + columna 5 + 2·columna 8 $=(3,3,0)=0$) y no en $C^\perp$, porque pesa 3 y no 9. Es un operador lógico: el dato queda estropeado sin que salte ninguna alarma. Dos errores superan lo que corrige un código de distancia 3, igual que en el Hamming clásico.

En resumen

• Con $C_1,C_2\subseteq\mathbb{F}_p^n$ y $C_2^\perp\subseteq C_1$, los estabilizadores $Z(h)$ (filas de $H_1$) y $X(g)$ (filas de $H_2$) conmutan porque $g\cdot h=0$.
• Los estados lógicos son $\ket{x+C_2^\perp}$, uno por clase lateral de $C_1/C_2^\perp$, y hay $p^k$ con $k=\dim C_1-\dim C_2^\perp$.
• Un error $X(a)Z(b)$ da el síndrome clásico $H_1a^T$ y menos el síndrome $H_2b^T$; ambos señalan posición y valor.
• El código de 3 cútrits es CSS con $C_2^\perp=\langle111\rangle$, y el Hamming ternario da un $[[13,7,3]]_3$ que corrige un error.
• Para $q=p^m$ se usa $Z(b)\ket{x}=\omega^{\operatorname{Tr}(b\cdot x)}\ket{x}$ y la condición sigue siendo $C_2^\perp\subseteq C_1$.

Siguiente lección: Reed-Solomon cuánticos