Technical Summary: Impure Codes Exceeding the Pure Bounds for Quantum Local Recovery

Problem Statement

Quantum local recovery (QLR) aims to reduce the number of measured qubits required for error or erasure correction by allowing the recovery of lost information using only a small subset of neighboring codeword symbols. While several Singleton-like bounds have been established for quantum locally recoverable codes (QLRCs), these bounds generally apply to pure quantum codes. A quantum code is defined as "pure" if all errors of weight less than the code distance are detectable; conversely, a code is impure if it contains non-trivial undetectable errors with weight less than the distance.

The central problem addressed in this paper is the lack of understanding regarding the role of impurity in quantum local recovery. Specifically, it was unknown whether impure codes could achieve parameters (length $n$, dimension $k$, distance $d$, and locality $r$) that violate the established upper bounds derived for pure quantum codes. Existing literature provides bounds for pure QRLCs, such as the bound for multiple erasures in pure stabilizer codes (Eq. 4), and bounds for pure codes constructed via the Hermitian inner product (Eqs. 5 and 6). The authors investigate whether constructing impure CSS (Calderbank–Shor–Steane) codes can yield parameters that exceed these pure bounds.

Methodology

The authors construct a specific family of impure quantum locally recoverable codes using the CSS construction based on classical linear codes derived from J-affine variety codes. The methodology involves the following steps:

1. Code Construction:

   • The authors define a family of classical linear codes $C(\mathcal{G}_{H,V,a,b})$ residing in the intersection of J-affine variety codes (with empty set $J$), weighted Reed–Muller codes, and decreasing monomial-Cartesian codes.
   • The codes are defined over a finite field $\mathbb{F}_q$ on a grid of points $P_{H,V} \subseteq \mathbb{F}_q^2$.
   • The set of monomials $\mathcal{G}_{H,V,a,b}$ is carefully chosen to ensure that the classical code $C$ contains its dual $C^\perp$ (a requirement for the CSS construction) while maintaining specific locality properties.

2. Determining Parameters:

   • Locality: The locality $(r, \delta)$ of the classical code is determined by its structure as a monomial-Cartesian code.
   • Distance: The minimum Hamming distance of the classical code $d_H(C)$ is determined using properties of weighted Reed–Muller codes.
   • Quantum Distance and Impurity: The distance of the resulting quantum code is determined by the minimum Hamming weight of vectors in $C \setminus C^\perp$. The authors utilize the Feng–Rao bound on the coset distance to establish a lower bound for this weight.
   • Impurity Condition: The code is proven to be impure if $d_H(C \setminus C^\perp) > d_H(C)$. The authors demonstrate that for specific choices of parameters ($H, V, a, b$), the minimum weight of $C \setminus C^\perp$ strictly exceeds the minimum weight of $C$, creating undetectable errors of weight less than the quantum distance.

3. Theoretical Verification:

   • The authors analytically compare the parameters of their constructed impure codes against the pure bounds (Eqs. 4, 5, and 6).
   • They prove that for specific parameter ranges (e.g., $V$ is an odd integer, $b=0$), the inequality defining the pure bound is violated.

Key Contributions and Results

1. Existence of Impure QRLCs Exceeding Pure Bounds

The primary contribution is the explicit construction of a family of impure CSS codes that violate several established bounds for pure quantum locally recoverable codes:

• Violation of Bound (4): Theorem 10 demonstrates that for $V$ odd and $b=0$, the constructed codes violate the pure Singleton-like bound for multiple erasures. The authors show that the difference between the left-hand side and right-hand side of the bound can be made arbitrarily large by increasing the field size $q$.
• Violation of Bound (5): Theorem 12 shows that for $V=3$, the parameters violate the pure bound derived for Hermitian inner product codes (Eq. 5).
• Violation of Bound (6): Theorem 13 proves that for $V=3$ and specific odd $H$, the parameters violate the pure Plotkin-like bound (Eq. 6).

2. Connection Between Local Recovery and Stabilizer Weights

The paper clarifies the relationship between quantum local recovery and weight-constrained stabilizers.

• Remark 1: It is noted that a stabilizer code with maximum generator weight $w$ implies a local recovery capability of $r = 2(w-1)$ for single erasures.
• Remark 3 & Lemma 2: The authors prove the converse is false. They construct a family of binary codes with locality $r=3$ where the stabilizer weights must grow linearly with the code length (specifically, at least $2m$ for length $4m$). This demonstrates that high locality does not necessarily imply low-weight stabilizers, and conversely, impure codes can achieve high locality without satisfying the weight constraints assumed in some pure-bound derivations.

3. Asymptotic Behavior

Remark 7 highlights that the proposed family of codes can achieve asymptotically positive information rate, relative distance, and relative locality simultaneously. Specifically, as the code length $n \to \infty$, the rate and relative distance approach $1/6$, while the relative locality approaches $1/4$.

4. Specific Examples

The paper provides concrete examples (Examples 4, 5, 15, and 16) where the violation is explicit:

• Example 15: A $[[15, 1, 6]]_5$ impure code with locality $(2,2)$ violates the pure Singleton bound (reducing $17 \leq 16$), the pure Griesmer bound ($15 \geq 16$), and the pure Plotkin bound ($6 \leq 75/13$).
• Example 16: A $[[64, 4, 16]]_8$ impure code violates the pure Singleton bound ($68 \leq 65$).

Significance and Claims

The paper claims that impurity is a resource that can improve the parameters of quantum locally recoverable codes beyond what is achievable by any pure Quantum Error Correcting Code (QECC).

• Limitations of Pure Bounds: The authors emphasize that existing bounds (4, 5, 6) are strictly applicable only to pure codes. The existence of this impure family proves that these bounds cannot be universally applied to all QECCs, even those with local recovery properties.
• Impossibility of Simple Correction: In Remark 11, the authors argue that simply adding a constant to the right-hand side of the pure Singleton-like bound (Eq. 4) cannot make it applicable to impure codes, as the violation can be made arbitrarily large.
• Open Problems: The paper modestly concludes that while they have identified a specific family of impure codes, generalizing this construction to arbitrary parameters remains an open research problem. Furthermore, they identify the lack of upper bounds for impure stabilizer codes correcting multiple erasures ($\delta \geq 3$) as a significant open challenge. Without such bounds, the optimality of their proposed family cannot be fully assessed.

In summary, the paper establishes that the restriction to "pure" codes in the derivation of quantum local recovery bounds is a significant limitation, and that impure CSS codes constructed from J-affine variety codes can achieve parameters that are theoretically impossible for pure codes.