# Codes saturating the bound d=(n+1)/2

An $$n$$ qudit code always has distance bounded above by $$d \leq \frac{n+1}{2}$$ (Edit: the correct bound appears to be $$d \leq \frac{n}{2}+1$$ but the $$[[6,0,4]]$$ hexacode and the $$[[2,0,2]]$$ Bell state are the only qubit codes that violates the tighter bound $$d \leq \frac{n+1}{2}$$. Indeed even the even tighter bound $$d \leq \frac{n}{2}$$ appears to be only violated by a few codes namely $$[[6,0,4]], [[5,1,3]], [[3,0,2]],[[2,0,2]]$$). The $$5$$ qudit generalization of the Knill-Laflamme code with parameters $$[[5,1,3]]_q$$ ( $$q$$ denoting the size of the qudit) has stabilizer generators \begin{align*} & XZZ^\dagger X^\dagger I \\ & IXZZ^\dagger X^\dagger \\ & X^\dagger IXZZ^\dagger \\ & Z^\dagger X^\dagger IXZ \end{align*} and for any $$q$$ this code saturates the bound $$d \leq \frac{n+1}{2}$$ since $$3 = \frac{5+1}{2}$$ The three qutrit code with parameters $$[[3,1,2]]_3$$ also saturates this bound $$2 = \frac{3+1}{2}$$ Are there any other qudit codes that saturate this bound? Or are the $$[[5,1,3]]_q$$ and $$[[3,1,2]]_3$$ codes essentially unique in this respect?

The bound you are referring to is a special case of the quantum Singleton bound. This bound says that given a code $$((n,K,d))_q$$ we have $$K \leq q^{n-2(d-1)}.$$ In the special case that we encode $$k$$-qu$$q$$its into $$n$$-qu$$q$$its (i.e., $$K = q^k$$) we have $$d \leq \frac{n-k+2}{2}.$$ Thus the bound you provided is a special case of the quantum singleton bound when $$k = 1$$.

A code that satisfies the quantum Singleton bound with equality is called a quantum maximum-distance-separable code (or quantum MDS code). So your question is basically asking which MDS codes exist.

Qubit $$q=2$$ MDS codes are completely classified and there aren't that many of them. They are $$[[6,0,4]]_2$$, $$[[5,1,3]]_2$$, and the even length codes $$[[2m,2m-2,2]]_2$$ (also the trivial codes $$[[n,n,1]]_2$$ but those are sort of fake). For higher $$q$$, there are many more MDS codes, for example see Quantum MDS Codes over Small Fields .

• ah ok so it looks like the only qubit code with $d=(n+1)/2$ is indeed the $[[5,1,3]]$ code. But also looks like for different $q$ there are lots of these codes like for qutrits $q=3$ there is the $[[3,1,2]]_3$ code and the $[[5,1,3]]_3$ code but also this paper shows there is a $[[9,1,3]]_3$ code. Other codes with $d=(n+1)/2$ described in the paper have parameters $[[9,1,5]]_4, [[9,1,5]]_5, [[7,1,4]]_5, [[9,1,5]]_7, [[11,1,6]]_7, [[13,1,7]]_7, [[9,1,5]]_8$. In general it seems reasonable to believe that there are $[[9,1,5]]_q$ codes for $q \geq 3$. Feb 25 at 22:33
• just noticed a typo in my comment above it should say "there is a $[[9,1,5]]_3$" not "there is a $[[9,1,3]]_3$" May 16 at 14:10

Thinking about your first question regarding qubit codes, another bound that we know must apply (at least for non-degenerate codes) is the Quantum Hamming Bound, $$2^{n-k}\geq\sum_{w=0}^{t}3^w\binom{n}{w},$$ assuming that $$d=2t+1$$ is odd. We make this as loose as possible by setting $$k=1$$, and we take $$d=(n+1)/2$$ (and therefore $$n=4t+1$$). So now we can ask for what values of $$n$$ is the Hamming bound satisfied? We can explicitly check for small $$n$$: only $$n=5,9$$ work. For large enough $$n$$ (I didn't do this carefully, but $$n\geq 21$$ seemed to be about right), you can inductively prove that if the Hamming bound isn't satisfied for $$n$$, then it isn't for $$n+4$$ either.

Now, we know that $$n=5$$ is a valid solution, so what about $$n=9$$? According to codetables.de, the best code $$[[9,1,d]]$$ has $$d=3$$, not $$d=5$$. Thus, the 5-qubit code is the only odd distance non-degenerate qubit code satisfying that bound.

I've emphasised that I've put in a non-degenerate assumption. I don't think that's too big an assumption - it's tough to find examples of degenerate codes that beat the Hamming bound and, even then, the only ones I'm aware of do so by a very small amount. So, I suspect this conclusion still holds when you include degenerate codes.

I assume (without having tried) that you could construct something similar for $$q>2$$.

• Interesting! see Eric's answer for details but it seems like the lack of a $[[9,1,5]]$ qubit code is a bit exceptional as it appears $[[9,1,5]]_q$ codes exist for $q \geq 3$ Feb 25 at 22:36