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.
Hardness of Approximating Quantum Code Distance Beyond 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) 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.
We prove that the quantum code distance is NP-hard to approximate within an additive error of cN, 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 τ:F2m↪F2N. The embedding doubles all Hamming distances between vectors in F2m 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).
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.
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 graphG, its graph state distance is either$\delta or\delta +1,where\delta istheminimumvertexdegreeofG$. 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.
Random classical linear codes are widely believed to be hard to decode. While slightly sub-exponential time algorithms exist when the coding rate vanishes sufficiently rapidly, all known algorithms at constant rate require exponential time. By contrast, the complexity of decoding a random quantum stabilizer code has remained an open question for quite some time. This work closes the gap in our understanding of the algorithmic hardness of decoding random quantum versus random classical codes. We prove that decoding a random stabilizer code with even a single logical qubit is at least as hard as decoding a random classical code at constant rate--the maximally hard regime. This result suggests that the easiest random quantum decoding problem is at least as hard as the hardest random classical decoding problem, and shows that any sub-exponential algorithm decoding a typical stabilizer code, at any rate, would immediately imply a breakthrough in cryptography.
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=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 cN1/14 of the optimum, where N is the number of qubits, unless P=NP. For the planar surface code, we obtain an Ω(N1/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.
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.