Distance hardness and addressable transversal T (09/29/26)

TL;DR Approximating the minimum distance of a stabilizer code—the Pauli weight of its lightest nontrivial logical operator—to within any constant-fraction additive gap $\alpha N$ in the block length $N$ is NP-hard for randomized algorithms (unless $\mathsf{NP}\subseteq \mathsf{coRP}$), matching the classical linear-gap hardness that prior quantum reductions only reached at $O(\sqrt{N})$. Fine-grained lower bounds under SETH (the Strong Exponential Time Hypothesis, that $k$-SAT needs essentially $2^n$ time) and Gap-ETH further rule out substantially sub-$2^{\kappa }$ exact algorithms and subexponential linear-gap approximation on linear-parameter instances.

• Main result: No randomized algorithm approximates stabilizer-code distance to within an additive $\alpha N$ for any constant $\alpha >0$ unless $\mathsf{NP}\subseteq \mathsf{coRP}$ (NP problems admit efficient randomized one-sided error refutation).
• Prior barrier closed: Earlier quantum hardness reductions stopped at an additive $O(\sqrt{N})$ gap; this work lifts the gap to a linear fraction of the block length $N$, matching the classical linear-code setting.
• SETH exact bound: For every $\epsilon >0$, no randomized $2^{(1-\epsilon )\kappa }\mathrm{poly}(N)$-time algorithm computes the distance of a code with $\kappa$ logical qubits unless SETH fails.
• Gap-ETH approximation bound: No randomized $2^{o(N)}$-time algorithm approximates distance to within a linear additive gap on instances where $N$, $\kappa$, and the gap are all linear, unless non-uniform Gap-ETH (a gapped exponential-time hardness hypothesis for SAT) fails.

TL;DR An explicit family of binary CSS codes—stabilizer codes built from a pair of classical linear codes—achieves constant rate and linear distance while supporting fully addressable transversal $T$ gates: any prescribed tensor product of logical powers of the non-Clifford phase gate $T=\mathrm{diag}(1,e^{i\pi /4})$ is realized by a matching tensor product of physical $T$ powers, with no corrective Clifford afterward. Algebraic-geometry codes plus a binary embedding yield generalized divisibility (a weight-divisibility condition on the classical codes that licenses transversal non-Clifford gates), closing a long-standing gap between asymptotic goodness and logical addressability for $T$.

• Main result: The construction gives an explicit infinite family of binary CSS codes with constant rate $k/n=\Theta (1)$ and linear distance $d=\Theta (n)$ that implement any chosen logical $T^{a_1}\otimes \cdots \otimes T^{a_k}$ by a purely transversal physical $T$ pattern, without a follow-up correction.
• Mechanism: Algebraic-geometry codes with a suitable multiplication property are mapped into binary codes via embedding so that the resulting classical codes satisfy generalized divisibility; that divisibility is what licenses fully addressable transversal $T$.
• Optimization: The minimum binary embedding length is cast as a minimum-weight problem over an affine space, and numerical solutions tighten the asymptotic constants in the rate and relative-distance bounds.
• Why it matters: Prior asymptotically good codes with transversal non-Cliffords typically lacked per-logical addressability, while addressable $T$ constructions often sacrificed constant rate or linear distance; this family combines both.