Maximal length of stabilizer quantum MDS codes

Problem

Is there a stabilizer quantum maximum-distance-separable code \([[n,k,d]]_q\) with \(k\geq1\) and \(d\geq3\) whose length \(n\) exceeds the conjectured limit \(b(q,d)\) of Eq. (2)? Let \(q=p^{m}\) with \(p\) prime and \(m\geq1\). A stabilizer code \([[n,k,d]]_q\) is a \(q^{k}\)-dimensional subspace of \((\mathbb{C}^{q})^{\otimes n}\) that is the joint \(+1\) eigenspace of an abelian subgroup of the \(n\)-qudit Pauli group containing no nontrivial multiple of the identity, and whose minimum distance is \(d\): it detects every Pauli error acting on fewer than \(d\) qudits and therefore exactly corrects an arbitrary error on any \(\lfloor(d-1)/2\rfloor\) qudits. No entanglement assistance or other side resource is allowed. Such a code is quantum maximum-distance-separable (QMDS) when it saturates the quantum Singleton bound,

\begin{equation} n-k=2(d-1). \tag{1} \end{equation}

Define the conjectured length limit

\begin{equation} b(q,d):= \begin{cases} q^{2}+2, & q\text{ even and }d=4,\\ q^{2}+1, & \text{otherwise}. \end{cases} \tag{2} \end{equation}

The question is whether some stabilizer code satisfying Eq. (1) with \(k\geq1\) and \(d\geq3\) has

\begin{equation} n>b(q,d). \tag{3} \end{equation}

A complete answer is either an explicit stabilizer code satisfying Eqs. (1) and (3), or a proof that Eq. (3) fails for every prime power \(q\), every \(d\geq3\), and every \(k\geq1\), which establishes the quantum MDS conjecture for codes with at least one logical qudit.

Source

Huber and Grassl state the quantum MDS conjecture explicitly as Conjecture 12 and attribute it to Corollary 65 of Ketkar, Klappenecker, Kumar, and Sarvepalli, where the length bound appears as a consequence of the classical MDS conjecture [HG20], [KKKS06]. The conjecture bounds the length of every stabilizer QMDS code with \(d\geq3\) by Eq. (2); this record asks for its proof or a stabilizer counterexample and restricts attention to codes with \(k\geq1\).

Progress

Huber and Grassl prove, for every QMDS code \(((n,q^{k},d))_q\) with \(d\geq3\), stabilizer or not, the unconditional bound

\begin{equation} n\leq q^{2}+d-2, \qquad\text{equivalently}\qquad n+k\leq 2(q^{2}-1), \tag{4} \end{equation}

Theorem 10 of [HG20]. For \(d=3\) it gives \(n\leq q^{2}+1=b(q,3)\), and for \(d=4\) with \(q\) even it gives \(n\leq q^{2}+2=b(q,4)\), so Eq. (3) is impossible in these cases. Eq. (4) exceeds \(b(q,d)\) by one for \(d=4\) with \(q\) odd and by \(d-3\) for every \(d\geq5\); Huber and Grassl state that Conjecture 12 is otherwise unresolved for \(d>3\). For stabilizer codes the odd-\(q\), \(d=4\) window is closed by the orthogonal-array bound of Eq. (5) below.
For \(k\geq1\) the stabilizer of a QMDS code is itself an additive MDS code: by Theorem 2 of [Rai99], restated as Lemma 59 and Corollary 60 of [KKKS06], every QMDS code \([[n,n-2(d-1),d]]_q\) with \(k\geq1\) is pure to weight \(n-d+2\), so Lemma 61 of [KKKS06] identifies its stabilizer with an additive code \(C\subseteq\mathbb{F}_{q^{2}}^{\,n}\), \(|C|=(q^{2})^{d-1}\), of minimum Hamming distance \(n-d+2\). A code, linear or not, with \(s^{t}\) words and minimum distance \(n-t+1\) over an alphabet of size \(s\) is an orthogonal array of strength \(t\) and index one: two words agreeing on \(t\) coordinates would be at distance at most \(n-t\), so every \(t\)-tuple of symbols occurs exactly once in every set of \(t\) coordinates. Hence \(C\) is an orthogonal array of strength \(d-1\) and index one on \(q^{2}\) symbols. Bush’s bound for such arrays, [Bus52], allows at most \(s+t-1\) coordinates when \(s\) is even and \(t\leq s\), and at most \(s+t-2\) when \(s\) is odd and \(3\leq t\leq s\). With \(s=q^{2}\) and \(t=d-1\) this gives

\begin{equation} n\leq q^{2}+d-3 \qquad(q\text{ odd},\ 4\leq d\leq q^{2}+1), \tag{5} \end{equation}

one less than Eq. (4), while for even \(q\) it reproduces Eq. (4); Theorem 63 of [KKKS06] obtains only the latter value from the MacWilliams identities. For \(d=4\) and odd \(q\), Eq. (5) reads \(n\leq q^{2}+1=b(q,4)\), so Eq. (3) is impossible; together with the previous item the conjecture therefore holds for every \(q\) when \(d\leq4\). This consequence is a deduction from the cited results and is not stated in [HG20]; it uses the stabilizer structure and does not extend to nonstabilizer QMDS codes.
The even-alphabet exception in Eq. (2) is necessary. Grassl and Rötteler construct, for every \(q=2^{m}\), stabilizer QMDS codes with parameters

\begin{equation} [[q^{2}+2,\;q^{2}-4,\;4]]_q, \tag{6} \end{equation}

Theorem 14 of [GR15], which Huber and Grassl cite as the family meeting their \(d=4\) bound [HG20]. For \(q\geq4\) these codes have \(k\geq1\) and length \(q^{2}+2>q^{2}+1\); for \(q=2\) the family gives the one-dimensional code \([[6,0,4]]_2\), outside the scope of this record.
Ball, Gamboa, and Lavrauw classify additive MDS codes over small fields, including \(\mathbb{F}_{4}\) and \(\mathbb{F}_{9}\), and deduce that the quantum MDS conjecture holds for

\begin{equation} q\in\{2,3\} \tag{7} \end{equation}

[BGL23]. The classification covers additive codes, not only codes linear over \(\mathbb{F}_{q^{2}}\), as the stabilizer correspondence requires; it does not extend to other prime powers. For \(q=4\) they show, Section 7 there, that a stabilizer counterexample would have to come from an additive \((18,16^{k},19-k)_{16}\) MDS code that is not linear over \(\mathbb{F}_{4}\), since additive MDS codes over \(\mathbb{F}_{16}\) that are linear over \(\mathbb{F}_{4}\) obey the MDS conjecture.
By Theorem 5.4 of [BCH23], a stabilizer code \([[n,k,d]]_q\) exists exactly when there is an additive code \(C\subseteq\mathbb{F}_{q}^{2n}\) with \(|C|=q^{n-k}\) contained in its symplectic dual \(C^{\perp_a}\), with \(d\) the minimum symplectic weight of \(C^{\perp_a}\setminus C\). QMDS codes are pure, Section 6.1 there, so the normalizer code \(C^{\perp_a}\) itself has minimum symplectic weight \(d\). Under the coordinatewise identification of \(\mathbb{F}_{q}^{2n}\) with \(\mathbb{F}_{q^{2}}^{\,n}\) used in the proof of Theorem 5.7 there, symplectic weight becomes Hamming weight, so a stabilizer QMDS code yields an additive code \(D\subseteq\mathbb{F}_{q^{2}}^{\,n}\), closed under addition but not necessarily \(\mathbb{F}_{q^{2}}\)-linear, with

\begin{equation} |D|=q^{n+k}=(q^{2})^{\,n-d+1}, \qquad d_{\mathrm{H}}(D)=d, \tag{8} \end{equation}

where \(d_{\mathrm{H}}\) is the minimum Hamming distance; \(D\) is an additive MDS code over \(\mathbb{F}_{q^{2}}\). Ball, Centelles, and Huber point out that Corollary 65 of [KKKS06] claims the quantum conjecture for stabilizer codes would follow from the classical MDS conjecture for linear codes, and correct it: the MDS conjecture for additive codes over \(\mathbb{F}_{q^{2}}\) is what the argument needs, Section 6.2 and Research Problem 6 of [BCH23].

Comment

Any unresolved case must have \(d\geq5\). In this range, for odd \(q\), Eq. (5) leaves the window \(q^{2}+1<n\leq q^{2}+d-3\), and for even \(q\), Eq. (4) leaves \(q^{2}+1<n\leq q^{2}+d-2\). These are necessary candidate ranges, not claims that every parameter choice remains open. The bounds in Progress exclude \(n>b(q,d)\) for \(d\leq4\). For even \(q\) and \(d=4\), the allowed exception \(n=q^{2}+2=b(q,4)\) is attained by the known family in Progress; it is not a counterexample. Only the alphabets in Eq. (7) are settled for every \(d\). A stabilizer counterexample would give, through Eq. (8), an additive MDS code over \(\mathbb{F}_{q^{2}}\) longer than the additive MDS conjecture permits, so a proof of that classical conjecture would settle this problem; it is open beyond small fields. This record excludes one-dimensional code spaces, \(k=0\), whose stabilizer QMDS codes are absolutely maximally entangled stabilizer states; the catalog’s records on absolutely maximally entangled states concern that case for arbitrary, not necessarily stabilizer, states. The record also does not extend the conjecture to nonstabilizer QMDS codes, which Huber and Grassl note could violate it even if the classical conjecture holds [HG20].

References

[HG20]: F. Huber and M. Grassl, “Quantum Codes of Maximal Distance and Highly Entangled Subspaces,” Quantum 4, 284 (2020).DOI arXiv
[KKKS06]: A. Ketkar, A. Klappenecker, S. Kumar, and P. K. Sarvepalli, “Nonbinary stabilizer codes over finite fields,” IEEE Transactions on Information Theory 52, 4892–4914 (2006).DOI arXiv
[Rai99]: E. M. Rains, “Nonbinary quantum codes,” IEEE Transactions on Information Theory 45, 1827–1832 (1999).DOI arXiv
[GR15]: M. Grassl and M. Rötteler, “Quantum MDS codes over small fields,” in 2015 IEEE International Symposium on Information Theory (ISIT), pp. 1104–1108 (2015).DOI arXiv
[BGL23]: S. Ball, G. Gamboa, and M. Lavrauw, “On additive MDS codes over small fields,” Advances in Mathematics of Communications 17, 828–844 (2023).DOI arXiv
[BCH23]: S. Ball, A. Centelles, and F. Huber, “Quantum error-correcting codes and their geometries,” Annales de l’Institut Henri Poincaré D 10, 337–405 (2023).DOI arXiv
[Bus52]: K. A. Bush, “Orthogonal arrays of index unity,” The Annals of Mathematical Statistics 23, 426–434 (1952).DOI

Maximal length of stabilizer quantum MDS codes

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems