On the hardnesses of several quantum decoding problems
Copyright policy )On the hardnesses of several quantum decoding problems
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.
There are six pages in this paper. Part of this paper was presented in the 2012 International Symposium on Information Theory and its Applications (ISITA 2012), Hawaii, USA, October 28--31, 2012
FOS: Computer and information sciences, Quantum cryptography (quantum-theoretic aspects), Quantum Physics, computational complexity, Computational stability and error-correcting codes for quantum computation and communication processing, degeneracy property, quantum error correction codes, Computer Science - Information Theory, Information Theory (cs.IT), FOS: Physical sciences, Cryptography, decoding hardness, quantum cryptography, Quantum Physics (quant-ph), quantum stabilizer codes
FOS: Computer and information sciences, Quantum cryptography (quantum-theoretic aspects), Quantum Physics, computational complexity, Computational stability and error-correcting codes for quantum computation and communication processing, degeneracy property, quantum error correction codes, Computer Science - Information Theory, Information Theory (cs.IT), FOS: Physical sciences, Cryptography, decoding hardness, quantum cryptography, Quantum Physics (quant-ph), quantum stabilizer codes
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).12 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!