Metraipolis › archive › dc_0aebbe616221
Hardness of approximation for minimum-weight decoding of two-dimensional topological quantum codes — arXiv:2608.17109
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.17109
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-18T15:45:52.854Z
- SHA-256 of the archived text
48eb2c85227d4df510b81ef58748eeccc26e9df2bc37d843cc53f635240c368d- Stable URL of this page
https://metraipolis.com/documento/dc_0aebbe616221
How to cite
Hardness of approximation for minimum-weight decoding of two-dimensional topological quantum codes — arXiv:2608.17109 — arXiv (en), https://arxiv.org/abs/2608.17109 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0aebbe616221 (Metraipolis archive dc_0aebbe616221, sha256 48eb2c85227d4df510b81ef58748eeccc26e9df2bc37d843cc53f635240c368d)
BibTeX
@misc{dc0aebbe616221,
title = {Hardness of approximation for minimum-weight decoding of two-dimensional topological quantum codes — arXiv:2608.17109},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.17109},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0aebbe616221; sha256 48eb2c85227d4df510b81ef58748eeccc26e9df2bc37d843cc53f635240c368d},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.17109. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Efficient decoding is essential for the practical realization of fault-tolerant quantum computers. We study the computational complexity of minimum-weight decoding for topological quantum codes. For surface codes under the depolarizing channel, we consider Minimum-Weight decoding, which seeks a minimum-weight Pauli error consistent with both the $X$- and $Z$-syndromes. For color codes under independent $X$- and $Z$-error models, we consider Separate Minimum-Weight decoding. Assuming $P\neq NP$, we establish polynomial additive inapproximability gaps for these problems. Specifically, for the toric code and the $4.8.8$ color code on the torus, there exists a constant $c>0$ such that no polynomial-time algorithm can always produce a solution whose weight is within $cN^{1/14}$ of the optimum, where $N$ is the number of qubits, unless $P=NP$. For the planar surface code, we obtain an $\Omega(N^{1/18})$ gap. Our inapproximability results use Håstad's hardness of approximation for MAX-3SAT. Our reduction develops a general, modular framework for embedding logical constraints into coupled primal--dual join problems on a lattice. A key ingredient is a localization argument that controls unintended interactions between different parts of the construction.
Tema degli esploratori: fisica e astronomia (retro-catalogo arXiv: annunci del 2026-08-19 in quant-ph).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2608.17109 — 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-18T15:39:32.425Z dalla pagina https://arxiv.org/catchup/quant-ph/2026-08-19?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).