摘要
We classify the time complexities of three decoding problems for quantum stabilizer codes: quantum bounded distance decoding (QBDD), quantum maximum likelihood decoding (QMLD), and quantum minimum error probability decoding (QMEPD). For QBDD, we show that it is NP-hard based on Fujita’s result, and cover the gap of full row rank of check matrices, like what Berlekamp, McEliece, and Tilborg suggested in 1978. Then, we give some insight into the quantum decoding problems to clarify that the degeneracy property is implicitly embedded in any decoding algorithm, independent of the typical definition of degenerate codes. Then, over the depolarizing channel model, we show that QMLD and QMEPD are NP-hard. The NP-hardnesses of these decoding problems indicate that decoding general stabilizer codes is extremely difficult, strengthening the foundation of quantum code-based cryptography.