Trellises for stabilizer codes: Definition and uses

Trellises play an important theoretical and practical role for classical codes. Their main utility is to devise complexity-efficient error estimation algorithms. Here, we describe trellis representations for quantum stabilizer codes. We show that they share the same properties as their classical analogs. In particular, for any stabilizer code it is possible to find a minimal trellis representation. Our construction is illustrated by two fundamental error estimation algorithms.

Figure 1

(Color online) Trellis representation for the four-qubit code and syndrome (0,0). Here, $\mid {\mathsf{V}}_0\mid =\mid {\mathsf{V}}_4\mid =1$ and $\mid {\mathsf{V}}_1\mid =\mid {\mathsf{V}}_2\mid =\mid {\mathsf{V}}_3\mid =4$.

Figure 2

(Color online) Trellis for the five-qubit code defined by the stabilizer set $\{ZXIII,XZXII,IXZXI,IIXZX\}$ and for the syndrome $s=\left(0011\right)$ obtained through the second construction. Here $\mid {\mathsf{V}}_0\mid =\mid {\mathsf{V}}_5\mid =1$, $\mid {\mathsf{V}}_1\mid =\mid {\mathsf{V}}_2\mid =\mid {\mathsf{V}}_3\mid =4$, and $\mid {\mathsf{V}}_4\mid =2$.