{"id":"arxiv/2609.22669","url":"https://arxiv.org/abs/2609.22669","tags":["quant-ph","cs.CC","cs.IT"],"score":0,"title":"Metric Self-Dual Completion and Optimal Additive Hardness for Quantum and Graph-State Distance","domain":"quant-ph","source":"arxiv","authors":["Rafail Ostrovsky"],"reviews":0,"subject":"quant-ph","summary":"We prove that the quantum code distance is NP-hard to approximate within an additive error of $c N$, for some constant $c >0$, where $N$ is the number of qubits. Our reductions are deterministic. This improves the previous square-root additive gap to $Ω(N)$ and resolves the explicitly stated linear-gap question of Kapshikar and Kundu. Our result holds for CSS codes with identical $X$- and $Z$-check spaces, and with a constant rate and constant relative distance. For every fixed $λ>1$, there is a constant $c>0$ such that hardness still holds even when every nonidentity stabilizer has weight…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-19","reactions":{}}