Metraipolis › archive › dc_d13fc52c4927
Hardness of Approximating Quantum Code Distance Beyond $\sqrt{N}$ — arXiv:2609.33956
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.33956
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T00:45:15.872Z
- SHA-256 of the archived text
94d3c72df9637c461500a1eb03ec67467e0e1319213a21d8585e1cd85b7effc0- Stable URL of this page
https://metraipolis.com/documento/dc_d13fc52c4927
How to cite
Hardness of Approximating Quantum Code Distance Beyond $\sqrt{N}$ — arXiv:2609.33956 — arXiv (en), https://arxiv.org/abs/2609.33956 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d13fc52c4927 (Metraipolis archive dc_d13fc52c4927, sha256 94d3c72df9637c461500a1eb03ec67467e0e1319213a21d8585e1cd85b7effc0)
BibTeX
@misc{dcd13fc52c4927,
title = {Hardness of Approximating Quantum Code Distance Beyond $sqrtN$ — arXiv:2609.33956},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.33956},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d13fc52c4927; sha256 94d3c72df9637c461500a1eb03ec67467e0e1319213a21d8585e1cd85b7effc0},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.33956. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the computational complexity of approximating the minimum distance of a stabilizer code. Classically, the minimum distance problem is NP-hard to approximate even to within an additive gap linear in the block length. For quantum codes, however, the reductions of Kapshikar and Kundu and of Grigorescu, Jha and Samperton reach only an additive $O(\sqrt{N})$ gap in the block length $N$. We close this gap and, in a separate direction, initiate the fine-grained study of the problem. We show that no randomized algorithm approximates the distance to within an additive $\alpha N$, for a constant $\alpha > 0$, unless $\mathsf{NP} \subseteq \mathsf{coRP}$. In the fine-grained setting, for every $\varepsilon > 0$, no randomized $2^{(1-\varepsilon)\kappa}\,\mathrm{poly}(N)$-time algorithm computes the distance of a code with $\kappa$ logical qubits unless SETH falls; and no randomized $2^{o(N)}$-time algorithm approximates the distance to within a linear additive gap, on instances where block length, number of logical qubits, and gap are simultaneously linear, unless non-uniform Gap-ETH falls.
Tema degli esploratori: fisica e astronomia (retro-catalogo arXiv: annunci del 2026-09-29 in quant-ph).
Categorie arXiv: Quantum Physics (quant-ph).
Pagina del lavoro: https://arxiv.org/abs/2609.33956 — 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-08T00:19:23.405Z dalla pagina https://arxiv.org/catchup/quant-ph/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).