aiqbench analysis
This research establishes the computational hardness of approximating minimum distances for graph states and hypergraph product codes, confirming that these problems remain NP-hard even under specific error constraints. By simplifying previous proofs via direct reductions to CSS codes, the study clarifies fundamental limits on decoding efficiency in both quantum and classical coding theory. These findings are critical for understanding the theoretical boundaries of fault-tolerant quantum computing architectures.
On the hardness of approximating minimum distances of quantum codes
arXiv:2509.21469v2 Announce Type: replace Abstract: The problem of computing distances of error-correcting codes is fundamental in both the classical and quantum settings. While hardness for the classical version of these problems has been known for some time (in both the exact and approximate settings), it was only recently that Kapshikar and Kundu showed these problems are also hard in the quantum setting. As our first main result, we reprove this using arguably simpler arguments based on hypergraph product codes. In particular, we get a direct reduction to CSS codes, the most commonly used type of quantum code, from the minimum distance problem for classical linear codes. Our second set of results considers the distance of a graph state, which is a key parameter for quantum codes obtained via the codeword stabilized formalism. We show that it is NP-hard to compute/approximate the distance of a graph state when the adjacency matrix of the graph is the input. In fact, we show this is true even if we only consider X-type errors of a graph state. Our techniques moreover imply an interesting classical consequence: the hardness of computing or approximating the distance of classical codes with rate equal to 1/2. One of the main motivations of the present work is a question raised by Kapshikar and Kundu concerning the NP-hardness of approximation when there is an additive error proportional to a quantum code's length. We show that no such hardness can hold for hypergraph product codes. These observations suggest the possibility of a new kind of square root barrier.
Abstract:The problem of computing distances of error-correcting codes is fundamental in both the classical and quantum settings. While hardness for the classical version of these problems has been known for some time (in both the exact and approximate settings), it was only recently that Kapshikar and Kundu showed these problems are also hard in the quantum setting. As our first main result, we reprove this using arguably simpler arguments based on hypergraph product codes. In particular, we get a direct reduction to CSS codes, the most commonly used type of quantum code, from the minimum distance problem for classical linear codes. Our second set of results considers the distance of a graph state, which is a key parameter for quantum codes obtained via the codeword stabilized formalism. We show that it is NP-hard to compute/approximate the distance of a graph state when the adjacency matrix of the graph is the input. In fact, we show this is true even if we only consider X-type errors of a graph state. Our techniques moreover imply an interesting classical consequence: the hardness of computing or approximating the distance of classical codes with rate equal to 1/2. One of the main motivations of the present work is a question raised by Kapshikar and Kundu concerning the NP-hardness of approximation when there is an additive error proportional to a quantum code's length. We show that no such hardness can hold for hypergraph product codes. These observations suggest the possibility of a new kind of square root barrier.
Quantum Physics (quant-ph); Information Theory (cs.IT)
arXiv:2509.21469 [quant-ph]
(or arXiv:2509.21469v2 [quant-ph] for this version)
https://doi.org/10.48550/arXiv.2509.21469 Focus to learn more arXiv-issued DOI via DataCite
https://doi.org/10.4230/LIPIcs.FSTTCS.2025.34 Focus to learn more DOI(s) linking to related resources
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 357 words
Related coverage
Hybrid quantum-classical algorithm matches best code solvers
Quantum Zeitgeist · Oct 13, 2026
Lattice-Based Cryptography Explained
Quantum Zeitgeist · Aug 15, 2026
Hardness of Approximating Quantum Code Distance Beyond $\sqrt{N}$
arXiv · Sep 30, 2026
Bringing Classical LDPC Code Design Theory to Quantum Computers
The Quantum Insider · Sep 9, 2026