Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2203.04262 · IEEE Transactions on Information Theory

On the Hardness of the Minimum Distance Problem of Quantum Codes

Upendra Kapshikar, Srijita Kundu

Published Jun 16, 2023• 11 citations
arXivHTMLPDF

Abstract

We study the hardness of the problem of finding the distance of quantum error-correcting codes. The analogous problem for classical codes is known to be NP-hard, even in approximate form. For quantum codes, various problems related to decoding are known to be NP-hard, but the hardness of the distance problem has not been studied before. In this work, we show that finding the minimum distance of stabilizer quantum codes exactly or approximately is NP-hard. This result is obtained by reducing the classical minimum distance problem to the quantum problem, using the CWS framework for quantum codes, which constructs a quantum code using a classical code and a graph. A main technical tool used for our result is a lower bound on the so-called graph state distance of 4-cycle free graphs. In particular, we show that for a 4-cycle free graph$G$, its graph state distance is either$\delta $or$\delta +1$, where$\delta $is the minimum vertex degree of$G$. Due to a well-known reduction from stabilizer codes to CSS codes, our results also imply that finding the minimum distance of CSS codes is also NP-hard.

DOI
10.1109/tit.2023.3286870

Related papers

Metric Self-Dual Completion and Optimal Additive Hardness for Quantum and Graph-State Distance

Rafail Ostrovsky

We prove that the quantum code distance is NP-hard to approximate within an additive error of $c N$, for some constant $c >0$, where $N$ is the number of qubits. Our reductions are deterministic. This improves the previous square-root additive gap to $Ω(N)$ and resolves the explicitly stated linear-gap question of Kapshikar and Kundu. Our result holds for CSS codes with identical $X$- and $Z$-check spaces, and with a constant rate and constant relative distance. For every fixed $λ>1$, there is a constant $c>0$ such that hardness still holds even when every nonidentity stabilizer has weight greater than $λ$ times the quantum distance. We also improve the hardness gap of graph state distance on $N$ vertices of Grigorescu, Jha, and Samperton from cube-root to $Ω(N)$, resolving their explicitly stated open question. Both hardness results are asymptotically optimal since both distances are at most $N$. Our graph state distance hardness result holds for balanced bipartite graphs with a binary adjacency matrix that is its own inverse (mod 2). Our main technique for both hardness bounds above is classical: we show how to convert any code $C$ of length $m$ into a self-dual code $A(C)$ of length $N=Θ(m)$ while exactly doubling the original coset metric. The conversion is deterministic and efficient. We call it the metric self-dual completion of $C$. It comes with a linear embedding $τ: \mathbb F_2^m \hookrightarrow \mathbb F_2^N$. The embedding doubles all Hamming distances between vectors in $\mathbb F_2^m$ and all pairwise distances between corresponding cosets. The embedding also guarantees that all codewords of $A(C)$ of weight at most $2m$ are exactly $τ(C)$.

quant-pharXiv:2609.22669•Sep 22, 2026•0 citations

On the Hardness of Approximating Distances of Quantum Codes

Elena Grigorescu, Jha, Vatsal, Eric Samperton

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 the hardness of these problems for non-degenerate quantum codes. As our first main result, 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. In particular, our proof uses arguably simpler constructions based on hypergraph product 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, which is a degenerate quantum code, when the adjacency matrix of the graph is the input. This establishes hardness for even degenerate quantum codes, which was not known before. Furthermore, 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.

arXiv:2509.21469•Leibniz international proceedings in informatics•Jan 1, 2025•0 citations

Hardness of Approximating Quantum Code Distance Beyond $\sqrt{N}$

Upendra Kapshikar

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(\sqrt{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 $\mathsf{NP} \subseteq \mathsf{coRP}$. In the fine-grained setting, for every $\varepsilon > 0$, no randomized $2^{(1-\varepsilon)κ}\,\mathrm{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.

quant-pharXiv:2609.33956•Sep 29, 2026•0 citations

The Diagonal Distance of CWS Codes

Upendra Kapshikar

Quantum degeneracy in error correction is a feature unique to quantum error correcting codes, unlike their classical counterpart. It allows a quantum error correcting code to correct errors even when they can not uniquely pinpoint the error. The diagonal distance of a quantum code is an important parameter that characterizes if the quantum code is degenerate or not. If code has a distance more than the diagonal distance, then it is degenerate, whereas if it is below the diagonal distance, then it is nondegenerate. We show that most of the CWS codes without a cycle of length four attain the upper bound of diagonal distance d+1, where d is the minimum vertex degree of the associated graph. Addressing the question of degeneracy, we give necessary conditions on CWS codes to be degenerate. We show that any degenerate CWS code with graph $G$ and classical code C will either have a short cycle in the graph $G$ or will be such that the classical code C has one of the coordinates trivially zero for all codewords.

arXiv:2107.11286•Jul 23, 2021•2 citations

On the hardness of decoding quantum stabilizer codes under the depolarizing channel

Kao-Yueh Kuo, Chung-Chin Lu

We classify the complexity classes of several important decoding problems for quantum stabilizer codes. First, regardless of the channel model, quantum bounded distance decoding is shown to be NP-hard, like what Berlekamp, McEliece and Tilborg did for classical binary linear codes in 1978. Then under the depolarizing channel, the decoding problems for finding a most likely error and for minimizing the decoding error probability are also shown to be NP-hard. Our results indicate that finding a polynomial-time decoding algorithm for general stabilizer codes may not be possible, but this, on the other hand, strengthens the foundation of quantum code-based cryptography.

International Symposium on Information Theory and its Applications•Oct 1, 2012•7 citations

On the Hardnesses of Several Quantum Decoding Problems

Kao-Yueh Kuo, Chung-Chin Lu

We classify the time complexities of three important decoding problems for quantum stabilizer codes. First, regardless of the channel model, quantum bounded distance decoding is shown to be NP-hard, like what Berlekamp, McEliece and Tilborg did for classical binary linear codes in 1978. Then over the depolarizing channel, the decoding problems for finding a most likely error and for minimizing the decoding error probability are also shown to be NP-hard. Our results indicate that finding a polynomial-time decoding algorithm for general stabilizer codes may be impossible, but this, on the other hand, strengthens the foundation of quantum code-based cryptography.

arXiv:1306.5173•Jun 21, 2013•6 citations
We study the hardness of the problem of finding the distance of quantum error-correcting codes. The analogous problem for classical codes is known to be NP-hard, even in approximate form. For quantum codes, various problems related to decoding are known to be NP-hard, but the hardness of the distance problem has not been studied before. In this work, we show that finding the minimum distance of stabilizer quantum codes exactly or approximately is NP-hard. This result is obtained by reducing the classical minimum distance problem to the quantum problem, using the CWS framework for quantum codes, which constructs a quantum code using a classical code and a graph. A main technical tool used for our result is a lower bound on the so-called graph state distance of 4-cycle free graphs. In particular, we show that for a 4-cycle free graphGGG, its graph state distance is eitherδ\delta δorδ+1\delta +1δ+1, whereδ\delta δis the minimum vertex degree ofGGG. Due to a well-known reduction from stabilizer codes to CSS codes, our results also imply that finding the minimum distance of CSS codes is also NP-hard.
We prove that the quantum code distance is NP-hard to approximate within an additive error of cNc NcN, for some constant c>0c >0c>0, where NNN is the number of qubits. Our reductions are deterministic. This improves the previous square-root additive gap to Ω(N)Ω(N)Ω(N) and resolves the explicitly stated linear-gap question of Kapshikar and Kundu. Our result holds for CSS codes with identical XXX- and ZZZ-check spaces, and with a constant rate and constant relative distance. For every fixed λ>1λ>1λ>1, there is a constant c>0c>0c>0 such that hardness still holds even when every nonidentity stabilizer has weight greater than λλλ times the quantum distance. We also improve the hardness gap of graph state distance on NNN vertices of Grigorescu, Jha, and Samperton from cube-root to Ω(N)Ω(N)Ω(N), resolving their explicitly stated open question. Both hardness results are asymptotically optimal since both distances are at most NNN. Our graph state distance hardness result holds for balanced bipartite graphs with a binary adjacency matrix that is its own inverse (mod 2). Our main technique for both hardness bounds above is classical: we show how to convert any code CCC of length mmm into a self-dual code A(C)A(C)A(C) of length N=Θ(m)N=Θ(m)N=Θ(m) while exactly doubling the original coset metric. The conversion is deterministic and efficient. We call it the metric self-dual completion of CCC. It comes with a linear embedding τ:F2m↪F2Nτ: \mathbb F_2^m \hookrightarrow \mathbb F_2^Nτ:F2m​↪F2N​. The embedding doubles all Hamming distances between vectors in F2m\mathbb F_2^mF2m​ and all pairwise distances between corresponding cosets. The embedding also guarantees that all codewords of A(C)A(C)A(C) of weight at most 2m2m2m are exactly τ(C)τ(C)τ(C).
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 the hardness of these problems for non-degenerate quantum codes. As our first main result, 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. In particular, our proof uses arguably simpler constructions based on hypergraph product 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, which is a degenerate quantum code, when the adjacency matrix of the graph is the input. This establishes hardness for even degenerate quantum codes, which was not known before. Furthermore, 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.
Hardness of Approximating Quantum Code Distance Beyond N\sqrt{N}N​
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)O(\sqrt{N})O(N​) gap in the block length NNN. 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αNαN, for a constant α>0α> 0α>0, unless NP⊆coRP\mathsf{NP} \subseteq \mathsf{coRP}NP⊆coRP. In the fine-grained setting, for every ε>0\varepsilon > 0ε>0, no randomized 2(1−ε)κ poly(N)2^{(1-\varepsilon)κ}\,\mathrm{poly}(N)2(1−ε)κpoly(N)-time algorithm computes the distance of a code with κκκ logical qubits unless SETH falls; and no randomized 2o(N)2^{o(N)}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.
Quantum degeneracy in error correction is a feature unique to quantum error correcting codes, unlike their classical counterpart. It allows a quantum error correcting code to correct errors even when they can not uniquely pinpoint the error. The diagonal distance of a quantum code is an important parameter that characterizes if the quantum code is degenerate or not. If code has a distance more than the diagonal distance, then it is degenerate, whereas if it is below the diagonal distance, then it is nondegenerate. We show that most of the CWS codes without a cycle of length four attain the upper bound of diagonal distance d+1, where d is the minimum vertex degree of the associated graph. Addressing the question of degeneracy, we give necessary conditions on CWS codes to be degenerate. We show that any degenerate CWS code with graph GGG and classical code C will either have a short cycle in the graph GGG or will be such that the classical code C has one of the coordinates trivially zero for all codewords.
We classify the complexity classes of several important decoding problems for quantum stabilizer codes. First, regardless of the channel model, quantum bounded distance decoding is shown to be NP-hard, like what Berlekamp, McEliece and Tilborg did for classical binary linear codes in 1978. Then under the depolarizing channel, the decoding problems for finding a most likely error and for minimizing the decoding error probability are also shown to be NP-hard. Our results indicate that finding a polynomial-time decoding algorithm for general stabilizer codes may not be possible, but this, on the other hand, strengthens the foundation of quantum code-based cryptography.
We classify the time complexities of three important decoding problems for quantum stabilizer codes. First, regardless of the channel model, quantum bounded distance decoding is shown to be NP-hard, like what Berlekamp, McEliece and Tilborg did for classical binary linear codes in 1978. Then over the depolarizing channel, the decoding problems for finding a most likely error and for minimizing the decoding error probability are also shown to be NP-hard. Our results indicate that finding a polynomial-time decoding algorithm for general stabilizer codes may be impossible, but this, on the other hand, strengthens the foundation of quantum code-based cryptography.