NP-hardness of decoding quantum error-correction codes
Open accessAbstract
Although the theory of quantum error correction is intimately related to classical coding theory and, in particular, one can construct quantum error-correction codes (QECCs) from classical codes with the dual-containing property, this does not necessarily imply that the computational complexity of decoding QECCs is the same as their classical counterparts. Instead, decoding QECCs can be very much different from decoding classical codes due to the degeneracy property. Intuitively, one expects degeneracy would simplify the decoding since two different errors might not and need not be distinguished in order to correct them. However, we show that general quantum decoding problem is NP-hard regardless of the quantum codes being degenerate or nondegenerate. This finding implies that no considerably fast decoding algorithm exists for the general quantum decoding problems and suggests the existence of a quantum cryptosystem based on the hardness of decoding QECCs.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
MLE is only an NP-hard problem.
“However, its computational complexity is lower: MLE is only an NP-hard problem.”
From Quantum error correction and fault tolerance: A comprehensive tutorial (2026) · cites this paper as [175]
The Main Results (p. 3) state that both quantum maximum-likelihood decoding problems studied are NP-hard. But “only” and the claimed lower computational complexity go beyond that result: the Conclusion (p. 5) leaves open whether the problems are QMA-hard as well. (LLM, conf=0.88)
Experimental — accuracy not yet measuredMLE takes in the worst case exponential time to solve, but is still relatively easier to compute than QMLD, which is a more difficult #P-complete problem.
“While this implies that MLE takes in the worst case exponential time to solve, it is still relatively easier to compute than the QMLD which is a more difficult #P-complete problem [174, 175].”
From Quantum error correction and fault tolerance: A comprehensive tutorial (2026) · cites this paper as [175]
In III. MAIN RESULTS (p. 3), the paper describes an intuitive search through 2^k solutions for classical maximum-likelihood decoding and proves that QMLD is NP-hard. It does not establish that QMLD is #P-complete or compare its computational difficulty with MLE; the exponential search description is not a worst-case time bound for every algorithm. (LLM, conf=0.88)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
No references could be resolved yet.
Research works printed but not linked: 1
- [17]J. Watrous. Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science , (2000).
Cited by
Sorted by citations
Quantum computation vs. firewalls
Harlow, D., & Hayden, P. (2013) · Journal of High Energy Physics · doi:10.1007/jhep06(2013)085 · Cited by 310 · see citing works
PyMatching: A Python Package for Decoding Quantum Codes with Minimum-Weight Perfect Matching
Higgott, O. (2022) · ACM Transactions on Quantum Computing · doi:10.1145/3505637 · Cited by 181 · see citing works
Triangular color codes on trivalent graphs with flag qubits
Chamberland, C., Kubica, A., Yoder, T. J., & Zhu, G. (2020) · New Journal of Physics · doi:10.1088/1367-2630/ab68fd · Cited by 105 · see citing works
Ising model formulation for highly accurate topological color codes decoding
Takada, Y., Takeuchi, Y., & Fujii, K. (2024) · Physical Review Research · doi:10.1103/physrevresearch.6.013092 · Cited by 10 · see citing works
Quantum error correction and fault tolerance: A comprehensive tutorial
Spencer, D. J., Jain, S. P., Tanggara, A., Sun, Z., Haug, T., Khu, D., & Bharti, K. (2026) · arXiv
- Authors
- Hsieh, M.-H., & Le Gall, F.
- Affiliations
- University of Cambridge (GB)
- ORCID
- Hsieh, Min-Hsiu
- Venue
- Physical Review A
- Publisher
- American Physical Society (APS)
- Published
- 2011-05-31
- Volume
- 83
- Issue
- 5
- ISSN
- 0556-2791 (ISSN-L)
- 1050-2947
- 1094-1622
- OpenAlex
- W2085970623
- Cited by
- 71
- References
- 0
- Citations by year
- 2026: 11 · 2025: 12 · 2024: 6 · 2023: 4 · 2022: 9 · 2021: 4 · 2020: 7 · 2019: 3 · 2018: 1 · 2017: 1 · 2015: 3 · 2014: 3 · 2013: 3 · 2012: 4
- FWCI
- 2.95
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Physical Review A (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- OPUS - Open Publications of UTS Scholars (University of Technology Sydney) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Japan Society for the Promotion of Science (22800006)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Coding theory and cryptography
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Keywords
- quantum error correction, quantum decoding, NP-hardness, computational complexity, dual-containing codes, quantum cryptography, decoding algorithms
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
