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