arXiv:2610.30088
The strengthened quantum Hamming bound of Yu, Lai, and Oh
Valery, Grishin, Aryeh Lev Zabokritskiy
Abstract
We prove a conjecture of Yu, Lai, and Oh: their strengthened quantum Hamming bounds, a family that interpolates between Hamming-type bounds and the Singleton bound, hold for all quantum codes of dimension $K>1$, including impure and nonadditive codes. The result covers every integer local dimension $p\ge2$, not necessarily a prime power, every integer $t\ge1$, both distances $2t+1$ and $2t+2$, and every interpolation parameter $e\in\{0,\ldots,t\}$. The case $e=0$ implies the ordinary quantum Hamming bound for general codes, recently proved by Zhang and Chen. Yu, Lai, and Oh proved their bounds for pure codes and for general codes of distance three or four. More generally, for every integer $p\ge2$ and every quantum code of length $n$, dimension $K>1$ and distance $d\ge3$, we prove $Kf(0)\le p^n\mathbb{E} f(X)$, where $X\sim\operatorname{Bin}(n,1-p^{-2})$, for every real polynomial $f$ of degree less than $d$ that is nonnegative on $\{0,\ldots,n\}$ and positive at zero. For pure codes this inequality is implicit in the argument of Yu, Lai, and Oh. The proof uses the linear-programming method with quantum weight enumerators.
AI Summary
The paper addresses whether the strengthened quantum Hamming–Singleton bounds, previously established for pure codes and general codes of distance three or four, hold for impure and nonadditive codes. It proves the conjectured extension for every exact quantum subspace code of dimension $K>1$, every integer local dimension $p\ge2$ (including non-prime powers), and all interpolation parameters and distance parities. The main result is a more general polynomial inequality: if a length-$n$ code has distance at least $d\ge3$, then every real polynomial $f$ with $\deg f<d$, $f(0)>0$, and $f(j)\ge0$ for $j=0,\ldots,n$ satisfies $Kf(0)\le p^n\mathbb E f(X)$, where $X\sim\operatorname{Bin}(n,1-p^{-2})$. Applying this to rounded Lloyd-root polynomials proves the strengthened bounds for distances $2t+1+\sigma$, $\sigma\in\{0,1\}$, and every $e=0,\ldots,t$. These include refinements of the ordinary Hamming bound and the Singleton endpoint $K\le p^{n-2(d-1)}$. The proof uses quantum weight enumerators and linear programming, reducing the polynomial statement to an extremal grid-nonnegative polynomial. Root-location and Krawtchouk-coefficient estimates handle one parameter region; invariant-enumerator dimension bounds handle large relative distances. The binary argument additionally uses Rains’s shadow length bound. The proof is computer-assisted, with finite certificates checked using exact rational or outward-rounded interval arithmetic. The results concern exact codes, exclude $K=1$, and are not claimed for arbitrary feasible solutions of the quantum linear program. The stronger conjecture that optimal qubit linear-programming solutions are pure remains unresolved.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 180 pages, including appendices. Computational certificates: https://doi.org/10.5281/zenodo.23552688