Our task of quantum list decoding for a classical block code is to recover from a given quantumly corrupted codeword a short list containing all messages whose codewords have high 'presence' in this quantumly corrupted codeword. All known families of efficiently quantum list decodable codes, nonetheless, have exponentially-small message rate. We show that certain generalized Reed-Solomon codes concatenated with Hadamard codes of polynomially-small rate and constant codeword alphabet size have efficient quantum list decoding algorithms, provided that target codewords should have relatively high presence in a given quantumly corrupted codeword. |
| Cite as: Yamakami, T. (2007). Quantum List Decoding from Quantumly Corrupted Codewords for Classical Block Codes of Polynomially Small Rate. In Proc. Thirteenth Computing: The Australasian Theory Symposium (CATS2007), Ballarat, Australia. CRPIT, 65. Gudmundsson, J. and Jay, B., Eds. ACS. 153-162. |
 (from crpit.com)
(local if available)
|