Metric Self-Dual Completion and Optimal Additive Hardness for Quantum and Graph-State Distance

We prove that the quantum code distance is NP-hard to approximate within an additive error of $cN$, 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 $\Omega (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 $\lambda >1$, there is a constant $c>0$ such that hardness still holds even when every nonidentity stabilizer has weight greater than $\lambda$ times the quantum distance. We also improve the hardness gap of graph state distance on $N$ vertices of Grigorescu, Jha, and Samperton from cube-root to $\Omega (N)$, resolving their explicitly stated open question. Both hardness results are asymptotically optimal since both distances are at most $N$. Our graph state distance hardness result holds for balanced bipartite graphs with a binary adjacency matrix that is its own inverse (mod 2). Our main technique for both hardness bounds above is classical: we show how to convert any code $C$ of length $m$ into a self-dual code $A(C)$ of length $N=\Theta (m)$ while exactly doubling the original coset metric. The conversion is deterministic and efficient. We call it the metric self-dual completion of $C$. It comes with a linear embedding $\tau :{\mathbb{F}}_2^m\hookrightarrow {\mathbb{F}}_2^N$. The embedding doubles all Hamming distances between vectors in ${\mathbb{F}}_2^m$ and all pairwise distances between corresponding cosets. The embedding also guarantees that all codewords of $A(C)$ of weight at most $2m$ are exactly $\tau (C)$.