arXiv:2609.22669
Metric Self-Dual Completion and Optimal Additive Hardness for Quantum and Graph-State Distance
Rafail Ostrovsky
Abstract
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 greater than $λ$ 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 $Ω(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=Θ(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 $τ: \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 $τ(C)$.
AI Summary
The paper addresses whether quantum-code distance and graph-state distance admit NP-hardness of approximation with a linear additive gap. It establishes deterministic Karp reductions giving gaps $\Omega(N)$ for both problems, improving previous gaps of $N^{1/2}$ and $N^{1/3}$, respectively, and resolving the stated linear-gap questions. These gaps are asymptotically optimal in their dependence on size because both distances are at most $N$. The central construction converts any binary linear code $C\leq\mathbb F_2^m$ into a self-dual code $A$ of length $N=\Theta(m)$. A linear embedding $\tau$ doubles Hamming weights and all corresponding coset distances, while the codewords of $A$ of weight at most $2m$ are exactly $\tau(C)$. Thus $d(A)=2d(C)$ for nonzero $C$. The construction starts with a deterministically constructible, high-distance self-dual host, retains the host subspace orthogonal to $\tau(C)$, and adds $\tau(C)$; dimension counting establishes self-duality and weight separation excludes unwanted short words. Using the retained subspace as both CSS check spaces gives $k=2\dim C$ and quantum distance $2d(C)$. Combining this with classical distance hardness yields linear-gap hardness even at constant rate and relative distance, with every nonidentity stabilizer heavier than $\lambda d(Q)$ for any fixed $\lambda>1$. A code-to-graph reduction yields graph-state hardness for balanced bipartite graphs with binary adjacency matrix satisfying $\Gamma^2=I$. The construction does not guarantee sparse checks, so it does not establish hardness for quantum LDPC codes.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.