Metraipolis › archive › dc_d1cbcc237789

Metric Self-Dual Completion and Optimal Additive Hardness for Quantum and Graph-State Distance — arXiv:2609.22669

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.22669
License (as archived)
CC0-1.0
Archived
2026-10-09T21:57:30.972Z
SHA-256 of the archived text
8dc7f957f1a5febbc8f873213ecec4b0aea340878e0c088722efdebb056dcbdc
Stable URL of this page
https://metraipolis.com/documento/dc_d1cbcc237789

How to cite

Metric Self-Dual Completion and Optimal Additive Hardness for Quantum and Graph-State Distance — arXiv:2609.22669 — arXiv (en), https://arxiv.org/abs/2609.22669 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d1cbcc237789 (Metraipolis archive dc_d1cbcc237789, sha256 8dc7f957f1a5febbc8f873213ecec4b0aea340878e0c088722efdebb056dcbdc)
BibTeX
@misc{dcd1cbcc237789,
  title = {Metric Self-Dual Completion and Optimal Additive Hardness for Quantum and Graph-State Distance — arXiv:2609.22669},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.22669},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d1cbcc237789; sha256 8dc7f957f1a5febbc8f873213ecec4b0aea340878e0c088722efdebb056dcbdc},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.22669. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\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)$.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-22 in math.IT).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC); Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2609.22669 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T21:44:07.501Z dalla pagina https://arxiv.org/catchup/math.IT/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).