## Abstract

Subsystem codes are a generalization of noiseless subsystems, decoherence-free subspaces and stabilizer codes. We generalize the quantum Singleton bound to _{q}-linear subsystem codes. It follows that no subsystem code over a prime field can beat the quantum Singleton bound. On the other hand, we show the remarkable fact that there exist impure subsystem codes beating the quantum Hamming bound. A number of open problems concern the comparison in the performance of stabilizer and subsystem codes. One of the open problems suggested by Poulin's work asks whether a subsystem code can use fewer syndrome measurements than an optimal _{q}-linear maximum distance separable stabilizer code while encoding the same number of qudits and having the same distance. We prove that linear subsystem codes cannot offer such an improvement under complete decoding.

## 1. Introduction

Subsystem codes (sometimes also referred to as operator quantum error-correcting codes) have emerged as an important new discovery in the area of quantum error-correcting codes, unifying the classes of stabilizer codes, decoherence-free subspaces and noiseless subsystems (Kribs *et al.* 2005, 2006; Poulin 2005; Bacon 2006; Knill 2006; Kribs 2006). This unification permits an understanding of active quantum error correction and passive quantum error correction within a common framework. However, this generalization is more than a theoretical construct. It has important practical implications too in the form of simpler error recovery schemes (Bacon 2006). These potential gains are in part the motivation behind this paper. However, first we recall some facts about quantum codes.

A quantum code *Q* is a subspace in a finite dimensional Hilbert space, . By qudit, we refer to a quantum digit with *q* levels. A quantum code *Q* encoding *k* qudits into *n* qudits and of distance *d* is referred to as an [[*n*, *k*, *d*]]_{q} quantum code. In this case, *Q* is a *q*^{k}-dimensional subspace of . Informally, the generalization to subsystem codes arose when further structure was imposed on the code subspace *Q*. A subsystem code is a quantum code that can be further resolved into a tensor product, i.e. *Q*=*A*⊗*B*. Information is stored in system *A*, while system *B*, referred to as the gauge subsystem or co-subsystem, provides some additional redundancy. Errors acting on the co-subsystem *B* alone can be ignored for the purposes of error correction. Furthermore, in the process of recovery, one need not restore the state of subsystem *B*, which provides a greater degree of flexibility than in the case of stabilizer codes. If *A* is *q*^{k}-dimensional and *B* is *q*^{r}-dimensional, then we encode *k* qudits into *n* qudits with *r* gauge qudits. The notion of distance also generalizes to subsystem codes as will be seen in §2. We denote the parameters of a subsystem code by [[*n*, *k*, *r*, *d*]]_{q}, indicating that it is a *q*-ary code with length *n*, encodes *k* qudits into the subsystem *A*, contains *r* gauge qudits and has distance *d*.

Perhaps the benefits of subsystem codes are best understood by an example. Consider the first quantum error-correcting code proposed by Shor (1995), which encodes one qubit into nine quantum bits. This code, which is capable of correcting a single error on any of the qubits, requires the measurement of eight syndrome qubits. The Bacon–Shor subsystem code (Bacon 2006), on the other hand, also encodes one qubit into nine but requires only four syndrome measurements, giving a simpler error recovery scheme.

In this context, it becomes crucial to identify when subsystem codes provide gains over the stabilizer codes. It also becomes necessary to compare the stabilizer codes and the subsystem codes fairly and with meaningful criteria. For instance, once again consider the [[9, 1, 3]]_{2} Shor code requiring *n*−*k=*9−1=8 syndrome measurements. The [[9, 1, 4, 3]]_{2} Bacon–Shor code, on the other hand, requires *n*−*k*−*r*=9−1−4=4 syndrome measurements. Clearly, this code is better than the Shor's code. However, the optimal single error-correcting binary quantum code that encodes one qubit is the [[5, 1, 3]]_{2} code, which also requires only 5−1=4 syndrome measurements. So it is apparent that while a given subsystem code can be superior to some stabilizer codes, it is not at all obvious that it is better than the best stabilizer code for the same function, *viz*., encoding *k* qubits with a distance *d*.

The first part of our paper seeks to address this issue for _{q}-linear Clifford subsystem codes which might perhaps be the most useful class of subsystem codes. In this paper, we generalize the quantum Singleton bound to _{q}-linear Clifford subsystem codes. It follows that no Clifford subsystem code over a prime field can beat the quantum Singleton bound. We then show how the quantum Singleton bound can be applied to make the comparison between stabilizer and subsystem codes (focusing on stabilizer codes that are optimal in the sense that they meet the quantum Singleton bound). This bound makes it possible to quantify the gains that subsystem codes can provide in error recovery. In particular, our results show that these gains involve a trade-off between the distance of the subsystem code and the number of information qudits and the gauge qudits. We show that if there exists an _{q}-linear maximum distance separable (MDS) stabilizer code, i.e. a code meeting the quantum Singleton bound, then no _{q}-linear subsystem code can outperform it in the sense of requiring fewer syndrome measurements for error correction.

Then, we shift our attention to a class of subsystem codes on lattices. Bacon & Casaccino (2006) obtained a subsystem code from two classical codes. We show that this method is a special case of the Euclidean construction for subsystem codes proposed by Aly *et al.* (2006) and give a coding theoretic analysis of these codes.

Since the early works on quantum error-correcting codes, it has been suspected that impure codes should somehow perform better than the pure codes. However, it was shown that the quantum Singleton bound holds true for both pure and impure stabilizer codes. However, it was not so clear with respect to the quantum Hamming bound. In fact, it was often conjectured that there might exist impure quantum error-correcting codes beating the quantum Hamming bound, but a proof remained elusive. At least in the case of binary stabilizer codes, there exists some evidence that the conjecture might not be true, as Ashikhmin & Litsyn (1999) showed that asymptotically the quantum Hamming bound was obeyed by impure codes as well, and Gottesman (1997) showed that no single error-correcting binary stabilizer code can beat the quantum Hamming bound. In this context, it is not surprising that questions were raised (Bacon 2006) about whether subsystem codes are any different. Aly *et al.* (2006) proved the quantum Hamming bound for pure subsystem codes. We show here that impure subsystem codes can indeed beat the quantum Hamming bound for pure subsystem codes. For example, we demonstrate that the lattice subsystem codes can provide examples of impure subsystem codes that beat the quantum Hamming bound.

The paper is structured as follows. We review the necessary background in §2 and then prove the quantum Singleton bound for subsystem codes in §3. The lattice subsystem codes are the focus of attention in §§4 and 5, wherein it is shown that there exist impure subsystem codes that beat the quantum Hamming bound. We conclude with a few open questions on subsystem codes.

## 2. Background

Let _{q} be a finite field with *q* elements and characteristic *p*. Let be an _{q}-linear classical code denoted by [*n*, *k*, *d*]_{q}, where and *d* is the minimum distance of *C*. We define , where wt(*c*) is the Hamming weight of *c*. Sometimes an alternative notation (*n*, *K*, *d*)_{q} is also used where *K*=|*C*|. If *C* is an _{q}-linear subspace over _{q}, then we say that it is an additive code.

If , then their Euclidean inner product is defined as . The Euclidean dual of a code is defined as { for all *x*∈*C*}. We say that a code *C* is self-orthogonal with respect to the Euclidean inner product if .

We use the notation to denote concatenation of . Let *u*=(*a|b*) and *v*=(*a*′|*b*′) be in . We define the symplectic weight of *u* as and the symplectic weight of a code as . For codes over , another inner product plays a more important role in the context of quantum codes. The trace-symplectic product between *u* and *v* is defined as . The trace-symplectic dual of is defined as . If , we say that it is self-orthogonal with respect to the trace-symplectic inner product.

### (a) Subsystem codes from classical codes

We now briefly review the background on subsystem codes. First, we give a group theoretic description and then an alternate description in terms of classical codes. Further details can be found in Aly *et al.* (2006) and Klappenecker & Sarvepalli (2006).

Let *q* be the power of a prime *p* and _{q} a finite field with *q* elements. Let denote an orthonormal basis for ^{q}. Let *X*(*a*) and *Z*(*b*) be unitary operators on ^{q} whose action on any element |*x*〉 in *B* is defined aswhere is a primitive *p*th root of unity. These operators are a *q*-ary generalization of the well-known Pauli matrices *X* and *Z*. Their action on an arbitrary element in ^{q} is obtained by invoking linearity. Let and be the error group on , defined as the tensor product of *n* such error operators, i.e.The weight of an error in is defined as the number of *E*_{i} which are not equal to identity and it is denoted by wt(*E*). We can also associate with *E* a vector . We define the symplectic weight of as

Every nontrivial normal subgroup *N* in defines a subsystem code *Q*. Let (*N*) be the centralizer of *N* in and *Z*(*N*), the centre of *N*. As a subspace, the subsystem code *Q* defined by *N* is precisely the same as the stabilizer code defined by *Z*(*N*). By theorem 4 in Klappenecker & Sarvepalli (2006), *Q* can be decomposed as *A*⊗*B*, where andSince information is stored only on subsystem *A*, we need only be concerned with errors that affect *A*. An error *E* in is detectable by subsystem *A* if and only if *E* is contained in the set . The distance of the code is defined asIf , then we define the distance of the code to be wt(*N*). A distance *d* subsystem code with dim *A*=*K*, dim *B*=*R* is often denoted as ((*n*, *K*, *R*, *d*))_{q} or [[*n*, *k*, *r*, *d*]]_{q} if *K*=*q*^{k} and *R*=*q*^{r}. We say that *N* is the *gauge group* of *Q* and *Z*(*N*) its *stabilizer*. The gauge group acts trivially on *A*.

In Klappenecker & Sarvepalli (2006), we showed that subsystem codes, much like the stabilizer codes, are related to the classical codes over or , but with one important difference. We no longer need the associated classical codes to be self-orthogonal, thereby extending the class of quantum codes. The gauge group *N* can be mapped to a classical code *C* over and (*N*) can be mapped to the trace-symplectic dual of *C*. The following theorem (Klappenecker & Sarvepalli 2006) shows how subsystem codes are related to classical codes.

*Let C be a classical additive subcode of* *such that C≠{*0*} and let D denote its subcode* . *If x=|C| and y=|D|, then there exists an operator quantum error-correcting code Q=A⊗B such that*

,

.

*The minimum distance of subsystem A is given by**if*;*if*.

*Thus, the subsystem A can detect all errors in* *of weight less than d, and can correct all errors in E of weight* .

We call codes constructed using theorem 2.1 as *Clifford subsystem codes*. Arguably, these codes cover the most important subsystem codes, including the recently proposed Bacon–Shor codes. In this paper, henceforth by a subsystem code, we will mean a Clifford subsystem code.

A further simplification of the above construction is possible, which takes any pair of classical codes to give a subsystem code. We will just recall the result here and study its application in §4.

*Let* *, be [n, k*_{i}]_{q} *linear codes where i∈{*1,2*}. Then, there exists an* [[*n, k, r, d*]]_{q} *Clifford subsystem code with*

,

,

*and*,

*where*.

The result follows from theorem 2.1 by defining *C*=*X*_{1}×*X*_{2}; it follows that and , and the parameters are easily obtained from these definitions (see Aly *et al.* (2006) for a detailed proof).

### (b) Pure and impure subsystem codes

We can extend the notion of purity to subsystem codes also in a straightforward manner. Let *N* be the gauge group of a subsystem code *Q* with distance . We say that *Q* is *pure to d*′ if there is no error of weight less than *d*′ in *N*. The code is said to be *exactly pure to d*′ if wt(*N*) is *d*′ and it is said to be pure if *d*′≥*d*. The code is said to be impure if it is exactly pure to *d*′<*d*. This refinement to the notion of purity was made in recognition of certain subtleties that had to be addressed when constructing other subsystem codes from existing subsystem codes (see Aly *et al.* (2006) for details).

In coding theoretic terms, this can be translated as follows. Let *C* be an additive subcode of and . By theorem 2.1, we can obtain an ((*n*,*K*,*R*,*d*))_{q} subsystem code *Q* from *C* that has minimum distance . If , then we say that the associated operator quantum error-correcting code is *pure to d*′.

Extending these ideas of purity to subsystem codes is useful because it facilitates the analysis of the parameters of the subsystem codes, as will become clear when we derive bounds in §3. If the codes are pure, then it will be very easy to see that the subsystem code with the parameters [[*n*, *k*, *r*, *d*]]_{q} satisfies *k*+*r*≤*n*−2*d*+2. This is because then the subsystem code can also be viewed as an [[*n*, *k*+*r*, *d*]]_{q} stabilizer code (see theorem 11 in Aly *et al.* (2006) for further details).

## 3. Quantum Singleton upper bound for _{q}-linear subsystem codes

### (a) An upper bound for subsystem codes

Recall that the quantum Singleton bound states that an [[*n*, *k*, *d*]]_{q} quantum code satisfies 2*d*≤*n*−*k*+2 (Knill & Laflamme 1997; Rains 1999). In this context, it is natural to ask whether subsystem codes also obey a similar relation. The usefulness of such a bound is obvious. Apart from establishing the bounds for optimal subsystem codes, they also make it possible to compare stabilizer and subsystem codes, as we shall see subsequently. We prove that the _{q}-linear subsystem codes with the parameters [[*n*, *k*, *r*, *d*]]_{q} satisfy a quantum Singleton-like bound *viz*. *k*+*r*≤*n*−2*d*+2. It will be seen that this reduces to the quantum Singleton bound if *r*=0. More interestingly, this reveals that there is a trade-off in the size of subsystem *A* and the gauge subsystem. One pays a price for the gains in error recovery. The cost is the reduction in the information to be stored.

Our proof for this result is very straightforward, though the intermediate details are a little involved. First, we show that a linear [[*n*, *k*, *r*>0, *d*]]_{q} subsystem code that is exactly pure to 1 can be punctured to an [[*n*−1, *k*, *r*−1, *d*]]_{q} code which retains the relationship between *n*, *k*, *r*, *d*. If *d*=2 by repeated puncturing, we arrive at either a pure subsystem code or a stabilizer code, both of which have upper bounds. For *d*>2, two cases can arise: if the code is exactly pure to 1, we simply puncture it to get a smaller code as in *d*=2 case; otherwise, we puncture it to get an [[*n*−1, *k*, *r*+1,*d*−1]]_{q} code. By repeatedly shortening, we get either a stabilizer code or a distance 2 code, both of which have an upper bound. Keeping track of the change in the parameters will give us an upper bound on the parameters of the original code.

Let . We denote by the vector obtained by deleting the first and the *n*+1th coordinates of *w*. Thus, we haveSimilarly, given a classical code , we denote the puncturing of *C* in the first and *n*+1 coordinates by *ρ*(*C*).

For _{q}-linear codes instead of considering the trace symplectic inner product, we can consider the relatively simpler symplectic product. The symplectic product of *u*=(*a*|*b*) and *v*=(*a*′|*b*′) in is defined as . The symplectic dual of a code is defined as . It will be seen that .

*Let* *be an* _{q}-*linear code with* *and* . *Then* , *if and only if* . *It follows that* .

If , then . Since *C* is linear, is also orthogonal to (*a*′|*b*′) for any . Hence, . However, tr is a non-degenerate function. It follows that . The converse is straightforward. The equality of follows immediately from the first part of the statement. ▪

As we shall be concerned with _{q}-linear codes in this paper, we will focus only on the symplectic inner product in the rest of the paper.

*Let* *be an* _{q}*-linear code. Then, C has an* _{q}-*linear basis of the form**where* *and* .

First, we choose a basis for a maximal isotropic subspace *C*_{0} of *C*. If *C*_{0}≠*C*, then we can choose a codeword *x*_{1} in *C* that is orthogonal to all of the *z*_{k} except one, say *z*_{1} (renumbering if necessary). We can scale *x*_{1} by an element in so that . If , then we repeat the process until we have a basis of the desired form. ▪

For the remainder of the section, we fix the following notation. By theorem 2.1, we can associate with an _{q}-linear [[*n*, *k*, *r*, *d*]]_{q} subsystem code two classical _{q}-linear codes , such that , , and . By lemma 3.2, we can also assume that *C* is generated bywhere *s*=*n*−*k*−*r* and the vectors *x*_{i}, *z*_{i} in satisfy the relations and . These relations on *x*_{i}, *z*_{i} imply that

*An* _{q}*-linear* [[*n, k, r>*0*, d≥*2]]_{q} *Clifford subsystem code exactly pure to* 1 *can be punctured to an* _{q}*-linear* [[*n−*1*, k, r−*1*, ≥d*]]_{q}*code*.

As mentioned above, we can associate with the subsystem code two classical codes . Two cases arise depending on swt(*D*).

If swt(

*D*)=1, then without loss of generality we can assume that swt(*z*_{1})=1. Further,*z*_{1}can be taken to be of the form (1, 0, …, 0|*a*, 0, …, 0), and for*i*≠1, owing to the_{q}-linearity of the codes we can choose every*x*_{i},*z*_{i}to be of the form . Further, as*x*_{i},*z*_{i}must satisfy the orthogonality relations with*z*_{1}*viz*. , for*i*>1 we can choose*x*_{i},*z*_{i}to be of the form . It follows that owing to the form of*x*_{i}and*z*_{i}puncturing the first and*n*+1th coordinate will not alter these orthogonality relations, in particular for .Letting , and observing that , we see that the code . Denoting by , it is immediate that

*D*_{p}is generated by while . Hence,*ρ*(*C*) defines an code.Next we show that . Let be in , then we can easily verify that is orthogonal to all

*z*_{i}, 1≤*i*≤*s*and hence it is in . It cannot be in*C*as that would imply that*u*is in*ρ*(*C*). However, . Therefore, , and*ρ*(*C*) defines an [[*n*−1,*k*,*r*, ≥*d*]]_{q}code. By choosing , we can conclude that there exists an code. Alternatively, apply theorem 16 in Aly*et al.*(2006).If , then we can assume that and form the code . It is clear that

*C*′ defines an [[*n*,*k*,*r*−1,*d*]]_{q}code that is pure to 1 with . However, this is just the previous case, from which we can conclude that there exists an [[*n*−1,*k*,*r*−1, ≥*d*]]_{q}code. ▪

Lemma 3.3 allows us to establish a bound for distance 2 codes which can then be used to prove the bound for arbitrary distances.

*An impure* _{q}*-linear* [[*n, k, r, d=*2]]_{q} *Clifford subsystem code satisfies*

Suppose that there exists an _{q}-linear [[*n*, *k*, *r*, *d*=2]] impure subsystem code such that ; in particular, this code must be pure to 1. By lemma 3.3, it can be punctured to give an subsystem code. If this code is pure, then holds, contradicting our assumption ; hence, the resulting code is once again impure and pure to 1.

Now we repeatedly apply lemma 3.3 to puncture the shortened codes until we get an subsystem code. However, this is a stabilizer code that must obey the Singleton bound , contradicting our initial assumption . Therefore, we can conclude that . ▪

If the codes are of distance greater than 2, then we puncture the code until either it has distance 2 or it is a pure code. The following result tells us how the parameters of the subsystem codes vary on puncturing.

*An impure* _{q}*-linear* [[*n, k, r, d≥*3]]_{q} *Clifford subsystem code exactly pure to d′≥*2 *implies the existence of an* _{q}*-linear* *subsystem code*.

Recall that the existence of an [[*n*, *k*, *r*, *d*≥3]]_{q} subsystem code implies the existence of _{q}-linear codes *C* and *D* such thatwith *s*=*n*−*k*−*r*, and (see above).

The stabilizer code defined by *D* satisfies , or equivalently *s*≥2*d*′−2; it follows that *s*≥2, since *d*>*d*′≥2. Without loss of generality, we can take *z*_{1} to be of the form for if no such codeword exists in *D*, then is contained in , contradicting the fact that . Consequently, we can choose *z*_{2} in *D* to be of the form , and we may further assume that *b*_{1}=0 in *z*_{1}. The form of *z*_{1} and *z*_{2} allows us to assume that any remaining generator of *C* is of the form .

Let *ρ* be the map defined by puncturing the first and (*n*+1)th coordinate of a vector in *C*. Define for all *i* the punctured vectors and . Then one easily checks that for all indices *i* and *j*, and if *i*≥*s*+1 or *j*≥3, and that .

Let us look at the punctured code *ρ*(*C*),Since we have , whence . As , it follows that . Thus, *ρ*(*C*) defines an subsystem code.

Recall that the code *D* is generated by *s*≥2 vectors; we will next show that our assumptions actually force *s*≥3. Indeed, if *s*=2, then |*D*|=*q*^{2} and . Under the assumption , it follows that . However, as this implies that . Since has 2*n*−2 independent codewords of symplectic weight 1, must have 2*n*−2 independent codewords of symplectic weight 2. However, this contradicts our assumptions on the minimum distance of the subsystem code.

If

*C*is a proper subspace of , then the minimum distance*d*is given by ; thus, the weight 2 vectors must all be contained in*C*, which shows that , contradicting .If , then the minimum distance is given by , contradicting our assumption that

*d*≥3.

Thus, from now on, we can assume that *s*≥3.

Before bounding the minimum distance of the punctured subsystem code, we are going to show that . Let be a vector in . For 3≤*i*≤*s*, the vectors *z*_{i} are of the form ; thus, it follows from that . Hence *ρ*(*w*) is in , which implies . We have , and we note that , because ; hence, .

Let be an arbitrary vector in . It follows that there exist some *α*, *β* in _{q} such that is in it is clear that *w* cannot be in *C*, since then *ρ*(*w*)=*w*′ would be in *ρ*(*C*); hence, . It immediately follows that . Hence *ρ*(*C*) defines an subsystem code. ▪

Now we are ready to prove the upper bound for an arbitrary subsystem code. Essentially, we reduce it to a pure code or distance 2 code by repeated puncturing and bound the parameters by carefully tracing the changes.

*An* _{q}-*linear* [[*n*, *k*, *r*, *d*≥2]]_{q} *Clifford subsystem code satisfies*(3.1)

The bound holds for all pure codes (see Aly *et al.* 2006). So assume that the code is impure. If *d*=2, then the relation holds by lemma 3.4; so let *d*≥3. If the code is exactly pure to 1, then it can be punctured using lemma 3.3 to give an code, otherwise it can be punctured using lemma 3.5 to obtain an code. If the punctured code is pure, then it follows that either or holds; in both cases, these inequalities imply that .

If the resulting code is impure, then if it is exactly pure to 1, we puncture the code again using lemma 3.3, if not we puncture using lemma 3.5, until we get a pure code or a code with distance 2. Assume that we punctured *i* times using lemma 3.3 and *j* times using lemma 3.5, then the resulting code is an subsystem code. Since pure subsystem codes and distance 2 subsystem codes satisfyit follows that holds. ▪

When the subsystem codes are over a prime alphabet, this bound holds for all codes over that alphabet. In the more general case where the code is not linear, numerical evidence indicates that it is unlikely that the additive subsystem codes have a different bound. We have shown that a large class of impure codes already satisfied this bound. This prompts the following conjecture.

*Any* [[*n, k, r, d*]]_{q} *Clifford subsystem code satisfies* .

### (b) Can subsystem codes improve upon MDS stabilizer codes?

In this subsection, we compare stabilizer codes with subsystem codes. We first need to establish the criteria for the comparison, since subsystem codes cannot be universally better than stabilizer codes. For example, it is known that a subsystem code can be converted to a stabilizer code (Poulin 2005; Kribs *et al.* 2006). See also lemma 10 in Aly *et al.* (2006) for a simple proof to convert an [[*n*, *k*, *r*, *d*]]_{q} code to an [[*n*, *k*, *d*]]_{q} code. This implies that no [[*n*, *k*, *r*, *d*]]_{q} subsystem code can beat an optimal [[*n*, *k*, *d*′]]_{q} stabilizer code in terms of minimum distance, as *d*′≥*d*. One of the attractive features of subsystem codes is a potential reduction of the number of syndrome measurements, and we use this criterion as the basis for our comparison.

First, we must highlight a subtle point on the required number of syndrome bits for an _{q}-linear [*n*, *k*, *d*]_{q} code. A complete decoder will require *n*−*k* syndrome bits. Complete decoders are also optimal decoders. A bounded distance decoder, on the other hand, can potentially decode with fewer syndrome bits. Bounded distance decoders typically decode up to ⌊(*d*−1)/2⌋. However, to the best of our knowledge, except for the lookup table decoding method, all bounded distance decoders also require *n*−*k* syndrome bits. As the complexity of decoding using a lookup table increases exponentially in *n*−*k*, it is highly impractical for long lengths. We therefore assume that for practical purposes we need *n*−*k* syndrome bits.

Similarly, for an _{q}-linear [[*n*, *k*, *r*, *d*]]_{q} subsystem code, a complete decoder will require *n*−*k*−*r* syndrome measurements, as is shown in appendix A. We are not aware of any quantum code, stabilizer or subsystem, for which there exists a bounded distance decoder that uses less than *n*−*k*−*r* syndrome measurements to perform bounded distance decoding. The work by Poulin (2005) prompts the following question: given an optimal MDS stabilizer code, is it possible to find an [[*n*, *k*, *r*, *d*]]_{q} subsystem code that uses fewer syndrome measurements?

There exist numerous known examples of subsystem codes that improve upon non-optimal stabilizer codes. The fact that the stabilizer code is assumed to be optimal makes this question interesting. The Singleton bound of an _{q}-linear [[*n*, *k*, *r*, *d*]]_{q} subsystem code implies that the number *n*−*k*−*r* of syndrome measurements is bounded by ; thus, for fixed minimum distance *d*, there exists a trade-off between the dimension *k* and the difference *n–r* between the length and number of gauge qudits.

*Under complete decoding, an* _{q}-*linear* *Clifford subsystem code cannot use fewer syndrome measurements than an* _{q}-*linear* *stabilizer code*.

Seeking a contradiction, we assume that there exists an subsystem code that requires fewer syndrome measurements than the optimal MDS stabilizer code. In other words, the number of syndrome measurements yields the inequality , which is equivalent to , but this contradicts the Singleton bound. ▪

Poulin (2005) showed by exhaustive computer search that a subsystem code does not exist. The above result confirms his computer search and shows further that not even allowing longer lengths and more gauge qudits can help in reducing the number of syndrome measurements. In fact, we conjecture that corollary 3.8 holds for bounded distance decoders also.

We wish to caution the reader that gains in error recovery cannot be quantified purely by the number of syndrome measurements. In practice, more complex measures such as the simplicity of the decoding algorithm or the resulting threshold in fault-tolerant quantum computing are more relevant. The drawback is that the comparison of large classes of codes becomes unwieldy when such complex criteria are used.

## 4. Subsystem codes on a lattice

Bacon (2006) gave the first family of subsystem codes generalizing the ideas of Shor's [[9, 1, 3]]_{2} code. Recently, he and Casaccino gave another construction that generalizes this further by considering a pair of classical codes (Bacon & Casaccino 2006). We show that this method is a special case of theorem 2.1. Since this construction is not limited to binary codes and our proofs remain essentially the same, we will immediately discuss a generalization to non-binary alphabets.

*For i∈{*1, 2*}, let* *be* _{q}*-linear codes with the parameters [n*_{i}*, k*_{i}*, d*_{i}*]*_{q}*. Then there exists a Clifford subsystem code with the parameters**that is pure to* , *where* *denotes the minimum distance of* .

Let *C* be the classical linear code given by . Then and . The symplectic dual of *C* is given byWe have . The code is given byand . It follows that and . Using corollary 2.2, we can get a subsystem code with the parametersthat is pure to . It remains to show that .

Since , we haveIn the last equality, we used the fact that vectors *u*_{1}⊗*u*_{2} and *v*_{1}⊗*v*_{2} are orthogonal if and only if or .

For *i*∈{1,2}, let *G*_{i} and *H*_{i}, respectively, denote the generator and parity check matrix of the code *C*_{i}. Without loss of generality, we may assume that these matrices are in standard formwhere is the transpose of *P*_{i}. Let . Using these notations, the generator matrices of *C* and can be written asIt follows that the minimum distance *d* is given byLet us computeIf minimum weight codeword is present in , it must be expressed as a linear combination of at least one row from , otherwise the codeword is entirely in *C*. Recall that and . Letting *P*_{1}=(*p*_{ij}), we can writeNow observe that any row below the line in the above matrix can have a weight of only one in each of the last *k*_{1} blocks of size *n*_{2}. And any linear combination of them involving less than *d*_{2} and at least one generator from the rows above must have a weight ≥*d*_{2}. On the other hand, if there are more than *d*_{2} rows involved, then the first columns will have a weight ≥*d*_{2}. Thus, in either case, the weight of an element that involves a generator from must have a weight ≥*d*_{2}. On the other hand, the minimum weight of the span of is , from which we can conclude thatOwing to the symmetry in the code, we can argue thatand consequently , which proves the theorem. ▪

### (a) Bacon–Shor codes

Bacon (2006) proposed one of the first families of subsystem codes based on square lattices. A trivial modification using rectangular lattices instead of square ones gives the following codes (see also Bacon & Casacinno 2006). The relevance of these codes will be seen later in §5. Using the same notation as in theorem 4.1, let and *H*_{i} be the matrix defined asand *C*, the additive code generated by the following matrix.Observe that *G*_{i} generates an [*i*,1,*i*]_{q} code with distance *i*. By theorem 4.1, and will give us the following family of codes.

*There exist* *Clifford subsystem codes*.

## 5. Subsystem codes and packing

We investigate whether subsystem codes lead to better codes with respect to the quantum Hamming bound. Since the early days of quantum codes, it has been recognized that the degeneracy of quantum codes could lead to a more efficient quantum code and allow for a much more compact packing of the subspaces in the Hilbert space. However, so far it has not been shown for stabilizer codes. We can derive a similar bound for subsystem codes. Aly *et al.* (2006) showed the following theorem for pure subsystem codes.

*A pure* *Clifford subsystem code satisfies*(5.1)

It is natural to ask whether impure subsystem codes also satisfy this bound. We show that they do not do so by giving an explicit counterexample. This counterexample comes from the codes proposed by Bacon (2006). Recall that the Bacon–Shor codes are subsystem codes. The [[9, 1, 4, 3]]_{2} is an interesting code. We can check whether it satisfies the Singleton bound for subsystem codes asSo it is an optimal code. More interestingly, substituting the parameters of the [[9, 1, 4, 3]]_{2} Bacon–Shor code in the above inequality, we getTherefore, the [[9, 1, 4, 3]]_{2} Bacon–Shor code beats the quantum Hamming bound for the pure subsystem codes proving the following result.

*There exist impure* *Clifford subsystem codes that do not satisfy*

An obvious question is why some impure codes can pack more efficiently than the pure codes. Let us understand this by looking at the [[9, 1, 4, 3]]_{2} code a little more closely. This code encodes information into a subspace *Q* where . As it is a subsystem code, *Q* can be decomposed as , with and . In a pure single error-correcting code, all single errors must take the code space into orthogonal subspaces. In an impure code this is not required; two or more distinct errors can take the code space to the same orthogonal space. In the Bacon–Shor code, a phase flip error on any of the first three qubits will take the code space to the same orthogonal subspace and owing to this we cannot distinguish between these errors. However, it is not a problem because we can restore the code space with respect to *A,* even though we cannot restore *B*. Thus, instead of requiring nine orthogonal subspaces as in a pure code, we only require three orthogonal subspaces to correct for any single phase flip error. Considering the bit flip errors and the combinations, we need only nine orthogonal subspaces. Thus, with the original code space, this means we need to pack ten 2^{5}-dimensional subspaces in the 2^{n}=2^{9} dimensional ambient space, which is achievable as 10.2^{5}<2^{9}.

More generally, in a sense, degeneracy allows distinct errors to share the same orthogonal subspace and thus pack more efficiently. It must be pointed out though that this better packing is attained at the cost of *r* gauge qudits compared with a stabilizer code.

In fact, there exists another code among the Bacon–Shor codes which also beats the Hamming bound for the subsystem codes. This is the [[16, 1, 9, 4]]_{2} code. The family of codes given in corollary 4.2 provides us with [[12, 1, 6, 3]]_{2} yet another example of a code that beats the quantum Hamming bound like the [[9, 1, 4, 3]]_{2} code. We can check thatHowever, note that unlike [[9, 1, 4, 3]]_{2} this code does not meet the Singleton bound for pure subsystem codes as 6+1<12−6+2. Naturally, we can ask whether there is a systematic method to construct codes that beat the quantum Hamming bound. At the moment we do not know. It appears unlikely that there exist long codes that beat the quantum Hamming bound.

## 6. Conclusion

We have proved that any _{q}-linear [[*n*, *k*, *r*, *d*]]_{q} Clifford subsystem code obeys the Singleton bound . Furthermore, we have shown earlier that pure Clifford subsystem codes satisfy this bound as well. Our results provide much evidence for the conjecture that the Singleton bound holds for arbitrary subsystem codes.

Pure Clifford subsystem codes obey the Hamming (or sphere packing) bound. In this paper, we have shown the amazing fact that there exist impure Clifford subsystem codes beating the Hamming bound. This is the first illustration of a case when impure codes pack more efficiently than their pure counterparts. One example of a code beating the Hamming bound is provided by the [[9, 1, 4, 3]]_{2} Bacon–Shor code; this remarkable example also illustrates the following noteworthy facts.

The [[9, 1, 4, 3]]

_{2}code requires 9−1−4=4 syndrome measurements just like the perfect [[5, 1, 3]]_{2}code.Since

*k*+*r*≤*n*−2*d*+2 for all prime alphabet codes, [[9, 1, 4, 3]]_{2}code is also an optimal subsystem code. This is interesting because the underlying classical codes are not MDS. In MDS stabilizer codes, the underlying classical codes are required to be MDS codes.The Bacon–Shor code is also impure. So unlike MDS stabilizer codes that must be pure, MDS subsystem codes can be impure.

The maximal length of a

*q*-ary stabilizer MDS code is 2*q*^{2}−2 (Ketkar*et al.*2006), whereas for subsystem codes it is larger as the [[9, 1, 4, 3]]_{2}code indicates.

The implication of (ii)–(iv) is that optimal subsystem codes can be derived from suboptimal classical codes, unlike stabilizer codes.

We conclude with a few open questions that seem to be interesting.

Do arbitrary subsystem codes also satisfy ?

Is the Hamming bound for subsystem codes obeyed asymptotically?

What is the maximal length of MDS subsystem codes?

The second question is motivated by the fact that binary stabilizer codes obey the quantum Hamming bound asymptotically (see corollary 2 in Ashikhmin & Litsyn (1999)).

## Acknowledgements

Part of this paper was presented at the BIRS workshop Operator Structures in Quantum Information Theory, Banff, Canada, 2007 and at the I^{2}Lab Workshop: Frontiers in Quantum and Biological Information Processing, Orlando, Florida 2006. We thank the organizers, particularly David Kribs, Mary Beth Ruskai and Pawel Wocjan, for inviting us to these fruitful workshops. We thank the referees for their comments which helped improve the presentation of the paper. This research was supported by NSF CAREER award CCF 0347310 and NSF grant CCF 0622201.

## Footnotes

- Received May 11, 2007.
- Accepted July 20, 2007.

- © 2007 The Royal Society