Hardness of Approximating Quantum Code Distance Beyond √N
Abstract
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(√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 αN, for a constant α> 0, unless NP ⊆ coRP. In the fine-grained setting, for every ε > 0, no randomized 2(1−ε)κ poly(N)-time algorithm computes the distance of a code with κ logical qubits unless SETH falls; and no randomized 2o(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.
Related
- Metric Self-Dual Completion and Optimal Additive Hardness for Quantum and Graph-State Distance
- Quantum Topological Data Analysis Beyond Betti Numbers: Complexity Hardness & An Algorithm for Torsion Witness
- Code-space recovery for sample-based quantum diagonalization beyond native symmetry constraints
- Phantom Codes: Hardness, Rate Optimal qLDPC Constructions, and Distance Limits
- Correlated decoding loses the surface code's effective distance below threshold
BibTeX
@misc{kapshikar2026hardness,
title = {{Hardness of Approximating Quantum Code Distance Beyond $\sqrtN$}},
author = {Upendra Kapshikar},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.33956},
eprint = {2609.33956},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33956},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Hardness of Approximating Quantum Code Distance Beyond √N
AU - Upendra Kapshikar
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2609.33956
UR - https://arxiv.org/abs/2609.33956
AB - 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(√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 αN, for a constant α> 0, unless NP ⊆ coRP. In the fine-grained setting, for every ε > 0, no randomized 2^(1−ε)κ poly(N)-time algorithm computes the distance of a code with κ 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.
ER -