Source-linked AI summary
Alphabet-Dependent Bounds for Pure Quantum $(r,ρ)$-Locally Recoverable Codes
Vijay Kumar, Ramakrishna Bandi
TL;DR
Existing Singleton-like bounds for pure (r,ρ)-qLRCs are alphabet independent, leaving finite-qudit-dimension effects unaccounted for. The paper derives three alphabet-dependent bounds through the Hermitian CSS construction and establishes their asymptotic hierarchy and relative tightness regions.
Problem
Known Singleton-like and GG Singleton-like bounds for pure (r,ρ)-qLRCs do not explicitly incorporate the qudit dimension q.
Method
The paper derives Griesmer-like, Plotkin-like, and sphere-packing-like upper bounds for pure (r,ρ)-qLRCs obtained through the Hermitian CSS construction.
Results
For r≥3, the asymptotic pure Plotkin-like bound is strictly tighter than the Griesmer-like bound, which is strictly tighter than the Singleton-like and GG Singleton-like bounds.
Takeaways & Limitations
The bounds provide alphabet-dependent rate constraints and identify relative-distance regions where each bound is tightest.
Abstract
from arXiv · showhide
A quantum $(r,ρ)$-locally recoverable code ($(r,ρ)$-qLRC) is a quantum code in which every qudit can be recovered from at most $r+ρ-1$ other qudits, even after $ρ-1$ additional erasures inside the recovery set. The bounds currently known for this class, namely the Singleton-like and the GG Singleton-like bounds, are alphabet independent and are therefore loose for small-to-moderate qudit dimensions. In this letter, we derive three alphabet-dependent upper bounds for pure $(r,ρ)$-qLRCs obtained through the Hermitian CSS construction: a Griesmer-like, a Plotkin-like, and a sphere-packing-like bound. We further establish the asymptotic hierarchy among these bounds and identify the relative-distance regions in which each of them yields the tightest rate constraint.
I. INTRODUCTION
Classical and quantum locally recoverable codes offer recovery from small subsets, but existing quantum Singleton-like bounds do not capture finite-alphabet effects. The letter addresses this gap with three alphabet-dependent bounds for pure (r,ρ)-qLRCs derived through the Hermitian CSS construction.
- (r,ρ)-LRCs recover erased symbols using at most r+ρ−1 symbols while tolerating ρ−1 erasures in each recovery set.
- Quantum (r,ρ)-LRCs extend this framework to qudit erasure correction and include stabilizer and CSS constructions.
- Existing Singleton-like bounds for qLRCs depend on code parameters but do not explicitly incorporate the qudit dimension q.
- The letter derives quantum Griesmer-like, sphere-packing-like, and Plotkin-like bounds for pure (r,ρ)-qLRCs via the Hermitian CSS construction.
- The paper analyzes the asymptotic behavior and relative tightness of the new bounds against the Singleton-like and GG Singleton-like bounds.
A. Classical (𝑟, 𝜌)-LRCs
This section defines q-ary linear codes and (r,ρ)-locality, then recalls alphabet-dependent bounds for classical (r,ρ)-LRCs. The bounds use shortened codes with effective length and dimension parameters.
- An [n,k,d]_q linear code is a k-dimensional subspace of F_q^n with minimum Hamming distance d.
- A coordinate has (r,ρ)-locality when it belongs to a recovery set of size at most r+ρ−1 whose punctured code has minimum distance at least ρ.
- An (r,ρ)-LRC requires this locality condition for every coordinate.
- The classical alphabet-dependent bounds apply to q-ary (r,ρ)-LRCs with parameters [n,k,d] and use τ_max=⌈k/r⌉−1.
- The bounds are expressed through shortened codes whose effective length is n−τ(r+ρ−1), with corresponding dimension reduction k−τr.
1) Griesmer-like bound:
The Griesmer-like derivation applies classical bounds to shortened effective parameters. The shortening range is constrained by requiring the residual length to remain positive.
- The sphere-packing step applies to effective length n′=n−τ(r+ρ−1) and dimension k′=k−τr.
- The classical sphere-packing bound yields k−τr≤n′−log_q V, where V is the relevant Hamming-ball volume.
- The requirement n′≥1 restricts shortening to τ≤⌊(n−1)/(r+ρ−1)⌋.
- The Plotkin-like assertion is obtained by applying the classical Plotkin bound to the same effective parameters.
B. Quantum (𝑟, 𝜌)-LRCs
This section introduces quantum (r,ρ)-LRCs and the Hermitian CSS route for constructing them from dual-containing classical codes. The resulting qLRC preserves locality, and purity is determined by whether its quantum distance equals the classical distance.
- A q-ary QECC [[n,κ,δ]]_q corrects arbitrary errors on up to ⌊(δ−1)/2⌋ qudits and satisfies 2δ≤n−κ+2.
- The Hermitian CSS construction combines [n,k_1,d_1]_{q^2} and [n,k_2,d_2]_{q^2} codes under a Hermitian dual-containment condition to produce an [[n,k_1+k_2−n,δ]]_q quantum code.
- A quantum (r,ρ)-LRC provides each qudit with a recovery set of size at most r+ρ−1 that tolerates any ρ−1 erasures within that set.
- A Hermitian dual-containing [n,k,d]_{q^2} code with (r,ρ)-locality and d_H^⊥≥ρ yields an [[n,κ,δ]]_q qLRC with κ=2k−n and the same locality.
- The constructed qLRC is pure when δ=d and impure otherwise.
III. ALPHABET-DEPENDENT BOUNDS FOR PURE
This section derives three alphabet-dependent bounds for pure (r,ρ)-qLRCs and states the theorem guaranteeing them for codes obtained through the Hermitian construction.
- The section derives alphabet-dependent bounds for pure (r,ρ)-qLRCs and analyzes their asymptotic behaviour.
- The construction assumes n+κ is even, so (n+κ)/2 is an integer and the resulting expressions are well defined.
- Theorem 3 applies to pure [[n,κ,δ]]_q qLRCs with (r,ρ)-locality obtained from the Hermitian construction.
3) Pure Plotkin-like bound:
The Plotkin-like quantum bound is obtained by translating a pure qLRC through the Hermitian CSS construction into a classical Hermitian dual-containing code and applying the classical Plotkin-like bound.
- A pure [[n,κ,δ]]_q qLRC with (r,ρ)-locality implies a classical Hermitian dual-containing linear code over F_q2 with corresponding locality.
- The locality constraint gives r≤(n+κ)/2, ensuring the admissible index ranges used in the bound are nonempty.
- Applying the classical Plotkin-like bound to this code yields the quantum Plotkin-like bound.
A. Asymptotic Analysis
The asymptotic analysis establishes a strict hierarchy among the Plotkin-like, Griesmer-like, Singleton-like, and GG Singleton-like bounds, while the sphere-packing-like bound changes with relative distance and locality scaling.
- Hierarchy: For r≥3, the asymptotic pure Plotkin-like bound is strictly tighter than the Griesmer-like bound, which is tighter than the Singleton-like and GG Singleton-like bounds.
- Sphere-packing-like bound: When the shortening parameter τ remains bounded, the locality-dependent term vanishes and the sphere-packing-like bound reduces to the standard asymptotic quantum sphere-packing bound.
- Sphere-packing-like bound: For linearly scaling shortening ratios, the analysis optimizes a strictly concave function over asymptotically admissible ratios.
- Sphere-packing-like bound: The critical relative distance is Δcrit=2(1−β), with the maximizing ratio at zero when Δ≥Δcrit.
- Sphere-packing-like bound: For 0<Δ<Δcrit, the sphere-packing-like asymptotic expression is obtained by evaluating at a positive stationary point.
- Sphere-packing-like bound: The entropy-based analysis covers Δ=0 continuously and requires Δ/2≤1−q^-2.
- Numerical comparison: For (r,ρ)=(280,17) over F2 with t=2, the numerical comparison confirms the theorem’s ordering and shows that the sphere-packing-like bound can be tightest for some parameters.
IV. CONCLUSION
The letter derives three alphabet-dependent upper bounds for pure (r,ρ)-qLRCs and establishes their asymptotic ordering relative to existing bounds.
- The authors derive Griesmer-like, sphere-packing-like, and Plotkin-like upper bounds from Hermitian dual-containing classical (r,ρ)-LRCs via the CSS construction.
- For r≥3, the Plotkin-like bound is asymptotically strictly tighter than the Griesmer-like bound.
- The Griesmer-like bound is asymptotically strictly tighter than the existing Singleton-like and GG Singleton-like bounds.
- The sphere-packing-like bound is numerically compared with this hierarchy over the (R, Δ) plane in Fig. 1.
- Constructions attaining bounds (13), (14), and (15) are left to the extended version of the work.