Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.30088

The strengthened quantum Hamming bound of Yu, Lai, and Oh

Valery, Grishin, Aryeh Lev Zabokritskiy

quant-phSubmitted Oct 21, 2026• Announced Oct 22, 2026• 0 citations• Revised Oct 22, 2026 (v2)
v1 · Oct 21, 2026v2 · Oct 22, 2026
arXivHTMLPDF

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.

No sign of AI-generated text

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

Related papers

The Quantum Hamming Bound in Arbitrary Local Dimension

Yu-Xuan Zhang, Jing-Ling Chen

The quantum Hamming bound arises from a direct dimension estimate for exact quantum error-correcting codes. For nondegenerate codes, distinct correctable errors map the code space into orthogonal subspaces, so dimension counting directly gives the bound; degeneracy allows these subspaces to overlap and invalidates the argument. Although linear-programming, asymptotic, and structural approaches have advanced the problem from several directions, the general local-dimension case has remained open. Here we prove the quantum Hamming bound for every local dimension $q\ge3$. Building on the exact two-center Fourier reduction, we develop new overlap estimates for nonbinary Hamming spaces. For $q\ge4$, Jacobi estimates and monotonicity give a uniform gap; qutrits form the boundary case where the gap vanishes and are handled by a filtered correction. This completes the finite-length nonbinary case; together with the existing qubit result, it establishes the quantum Hamming bound for arbitrary local dimension.

quant-pharXiv:2606.22538•Jun 23, 2026•2 citations

Strengthened quantum Hamming bound

Sixia Yu, Lai, C. H., Changhun Oh

We report two analytical bounds for quantum error-correcting codes that do not have preexisting classical counterparts. Firstly the quantum Hamming and Singleton bounds are combined into a single tighter bound, and then the combined bound is further strengthened via the well-known Lloyd's theorem in classical coding theory, which claims that perfect codes, codes attaining the Hamming bound, do not exist if the Lloyd's polynomial has some non-integer zeros. Our bound characterizes quantitatively the improvement over the Hamming bound via the non-integerness of the zeros of the Lloyd's polynomial. In the case of 1-error correcting codes our bound holds true for impure codes as well, which we conjecture to be always true, and for stabilizer codes there is a 1-logical-qudit improvement for an infinite family of lengths.

arXiv:1005.4758•May 26, 2010•3 citations

Strengthened quantum Hamming bound

Lijuan Xing, Zhuo Li, Zhang Wu-Jun

By studying sets of operators with constant weight we present for the first time an analytical upper bound on the pure quantum stabilizer codes whose underlying quantum system can be of arbitrary dimension, which outperforms the so far well-known quantum Hamming bound, the optimal analytical upper bound for small code length.

Acta Physica Sinica•Jan 1, 2011•1 citation

A Hamming-Like Bound for Degenerate Stabilizer Codes

Andrew Nemec, Theerapat Tansuwannont

The quantum Hamming bound was originally put forward as an upper bound on the parameters of nondegenerate quantum codes, but over the past few decades much work has been done to show that many degenerate quantum codes must also obey this bound. In this paper, we show that there is a Hamming-like bound stricter than the quantum Hamming bound that applies to degenerate $t$-error-correcting stabilizer codes of length greater than some positive integer $N(t)$. We show that this bound holds for all single-error-correcting degenerate stabilizer codes, forcing all but a handful of optimal distance-3 stabilizer codes to be nondegenerate.

arXiv:2306.00048•May 31, 2023•5 citations

Infinite Families of Quantum-Classical Hybrid Codes

Andrew Nemec, Andreas Klappenecker

Hybrid codes simultaneously encode both quantum and classical information into physical qubits. We give several general results about hybrid codes, most notably that the quantum codes comprising a genuine hybrid code must be impure and that hybrid codes can always detect more errors than comparable quantum codes. We also introduce the weight enumerators for general hybrid codes, which we then use to derive linear programming bounds. Finally, inspired by the construction of some families of nonadditive codes, we construct several infinite families of genuine hybrid codes with minimum distance two and three.

arXiv:1911.12260•IEEE Transactions on Information Theory•Jan 13, 2021•12 citations

Upper bounds on the size of quantum codes

Alexei Ashikhmin, S. Litsyu

This paper is concerned with bounds for quantum error-correcting codes. Using the quantum MacWilliams (1972, 1977) identities, we generalize the linear programming approach from classical coding theory to the quantum case. Using this approach, we obtain Singleton-type, Hamming-type, and the first linear-programming-type bounds for quantum codes. Using the special structure of linear quantum codes, we derive an upper bound that is better than both Hamming and the first linear programming bounds on some subinterval of rates.

IEEE Transactions on Information Theory•May 1, 1999•77 citations
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>1K>1K>1, including impure and nonadditive codes. The result covers every integer local dimension p≥2p\ge2p≥2, not necessarily a prime power, every integer t≥1t\ge1t≥1, both distances 2t+12t+12t+1 and 2t+22t+22t+2, and every interpolation parameter e∈{0,…,t}e\in\{0,\ldots,t\}e∈{0,…,t}. The case e=0e=0e=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≥2p\ge2p≥2 and every quantum code of length nnn, dimension K>1K>1K>1 and distance d≥3d\ge3d≥3, we prove Kf(0)≤pnEf(X)Kf(0)\le p^n\mathbb{E} f(X)Kf(0)≤pnEf(X), where X∼Bin⁡(n,1−p−2)X\sim\operatorname{Bin}(n,1-p^{-2})X∼Bin(n,1−p−2), for every real polynomial fff of degree less than ddd that is nonnegative on {0,…,n}\{0,\ldots,n\}{0,…,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.
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>1K>1K>1, every integer local dimension p≥2p\ge2p≥2 (including non-prime powers), and all interpolation parameters and distance parities.
The main result is a more general polynomial inequality: if a length-nnn code has distance at least d≥3d\ge3d≥3, then every real polynomial fff with deg⁡f<d\deg f<ddegf<d, f(0)>0f(0)>0f(0)>0, and f(j)≥0f(j)\ge0f(j)≥0 for j=0,…,nj=0,\ldots,nj=0,…,n satisfies Kf(0)≤pnEf(X)Kf(0)\le p^n\mathbb E f(X)Kf(0)≤pnEf(X), where X∼Bin⁡(n,1−p−2)X\sim\operatorname{Bin}(n,1-p^{-2})X∼Bin(n,1−p−2). Applying this to rounded Lloyd-root polynomials proves the strengthened bounds for distances 2t+1+σ2t+1+\sigma2t+1+σ, σ∈{0,1}\sigma\in\{0,1\}σ∈{0,1}, and every e=0,…,te=0,\ldots,te=0,…,t. These include refinements of the ordinary Hamming bound and the Singleton endpoint K≤pn−2(d−1)K\le p^{n-2(d-1)}K≤pn−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=1K=1K=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.
The quantum Hamming bound arises from a direct dimension estimate for exact quantum error-correcting codes. For nondegenerate codes, distinct correctable errors map the code space into orthogonal subspaces, so dimension counting directly gives the bound; degeneracy allows these subspaces to overlap and invalidates the argument. Although linear-programming, asymptotic, and structural approaches have advanced the problem from several directions, the general local-dimension case has remained open. Here we prove the quantum Hamming bound for every local dimension q≥3q\ge3q≥3. Building on the exact two-center Fourier reduction, we develop new overlap estimates for nonbinary Hamming spaces. For q≥4q\ge4q≥4, Jacobi estimates and monotonicity give a uniform gap; qutrits form the boundary case where the gap vanishes and are handled by a filtered correction. This completes the finite-length nonbinary case; together with the existing qubit result, it establishes the quantum Hamming bound for arbitrary local dimension.
We report two analytical bounds for quantum error-correcting codes that do not have preexisting classical counterparts. Firstly the quantum Hamming and Singleton bounds are combined into a single tighter bound, and then the combined bound is further strengthened via the well-known Lloyd's theorem in classical coding theory, which claims that perfect codes, codes attaining the Hamming bound, do not exist if the Lloyd's polynomial has some non-integer zeros. Our bound characterizes quantitatively the improvement over the Hamming bound via the non-integerness of the zeros of the Lloyd's polynomial. In the case of 1-error correcting codes our bound holds true for impure codes as well, which we conjecture to be always true, and for stabilizer codes there is a 1-logical-qudit improvement for an infinite family of lengths.
The quantum Hamming bound was originally put forward as an upper bound on the parameters of nondegenerate quantum codes, but over the past few decades much work has been done to show that many degenerate quantum codes must also obey this bound. In this paper, we show that there is a Hamming-like bound stricter than the quantum Hamming bound that applies to degenerate ttt-error-correcting stabilizer codes of length greater than some positive integer N(t)N(t)N(t). We show that this bound holds for all single-error-correcting degenerate stabilizer codes, forcing all but a handful of optimal distance-3 stabilizer codes to be nondegenerate.
Hybrid codes simultaneously encode both quantum and classical information into physical qubits. We give several general results about hybrid codes, most notably that the quantum codes comprising a genuine hybrid code must be impure and that hybrid codes can always detect more errors than comparable quantum codes. We also introduce the weight enumerators for general hybrid codes, which we then use to derive linear programming bounds. Finally, inspired by the construction of some families of nonadditive codes, we construct several infinite families of genuine hybrid codes with minimum distance two and three.
This paper is concerned with bounds for quantum error-correcting codes. Using the quantum MacWilliams (1972, 1977) identities, we generalize the linear programming approach from classical coding theory to the quantum case. Using this approach, we obtain Singleton-type, Hamming-type, and the first linear-programming-type bounds for quantum codes. Using the special structure of linear quantum codes, we derive an upper bound that is better than both Hamming and the first linear programming bounds on some subinterval of rates.