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