On the Hardnesses of Several Quantum Decoding Problems

DOI10.1007/S11128-020-02622-8MaRDI QIDQ6242830arXivFDO

Authors Kao-Yueh Kuo, Chung-Chin Lu

Publication date 21 June 2013

Published in arXiv

Full work available at URL https://doi.org/10.1007/S11128-020-02622-8

Mathematics Subject Classification ID

Computational stability and error-correcting codes for quantum computation and communication processing (81P73) Quantum cryptography (quantum-theoretic aspects) (81P94) Cryptography (94A60)

arXiv classification

cs.ITmath.ITquant-ph

Abstract: 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.

This page was built for publication: On the Hardnesses of Several Quantum Decoding Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6242830)