dorsal/arxiv
View SchemaQuantum List Decoding of Classical Block Codes of Polynomially Small Rate from Quantumly Corrupted Codewords
| Authors | Tomoyuki Yamakami |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0610200 |
| URL | https://arxiv.org/abs/quant-ph/0610200 |
| DOI | 10.22364/bjmc.2016.4.4 |
| Journal | Baltic Journal of Modern Computing, Vol. 4 (2016), No. 4, pp. 753-788 |
| License | http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
Abstract
Given a classical error-correcting block code, the task of quantum list decoding is to produce from any quantumly corrupted codeword a short list containing all messages whose codewords exhibit high "presence" in the quantumly corrupted codeword. Efficient quantum list decoders have been used to prove a quantum hardcore property of classical codes. However, the code rates of all known families of efficiently quantum list-decodable codes are, unfortunately, too small for other practical applications. To improve those known code rates, we prove that a specific code family of polynomially small code rate over a fixed code alphabet, obtained by concatenating generalized Reed-Solomon codes as outer codes with Hadamard codes as inner codes, has an efficient quantum list-decoding algorithm if its codewords have relatively high codeword presence in a given quantumly corrupted codeword. As an immediate application, we use the quantum list decodability of this code family to solve a certain form of quantum search problems in polynomial time. When the codeword presence becomes smaller, in contrast, we show that the quantum list decodability of generalized Reed-Solomon codes with high confidence is closely related to the efficient solvability of the following two problems: the noisy polynomial interpolation problem and the bounded distance vector problem. Moreover, assuming that NP is not included in BQP, we also prove that no efficient quantum list decoder exists for the generalized Reed-Solomon codes.
{
"annotation_id": "1eb1659b-3a3b-46b6-a99c-d8ecc29dba2b",
"date_created": "2026-03-02T18:02:31.193000Z",
"date_modified": "2026-03-02T18:02:31.193000Z",
"file_hash": "e97edb94f711a983049b9a37c87eba56cc4d76ac7d497ef77cbe16f2d10a7f3f",
"private": false,
"record": {
"abstract": "Given a classical error-correcting block code, the task of quantum list\ndecoding is to produce from any quantumly corrupted codeword a short list\ncontaining all messages whose codewords exhibit high \"presence\" in the\nquantumly corrupted codeword. Efficient quantum list decoders have been used to\nprove a quantum hardcore property of classical codes. However, the code rates\nof all known families of efficiently quantum list-decodable codes are,\nunfortunately, too small for other practical applications. To improve those\nknown code rates, we prove that a specific code family of polynomially small\ncode rate over a fixed code alphabet, obtained by concatenating generalized\nReed-Solomon codes as outer codes with Hadamard codes as inner codes, has an\nefficient quantum list-decoding algorithm if its codewords have relatively high\ncodeword presence in a given quantumly corrupted codeword. As an immediate\napplication, we use the quantum list decodability of this code family to solve\na certain form of quantum search problems in polynomial time. When the codeword\npresence becomes smaller, in contrast, we show that the quantum list\ndecodability of generalized Reed-Solomon codes with high confidence is closely\nrelated to the efficient solvability of the following two problems: the noisy\npolynomial interpolation problem and the bounded distance vector problem.\nMoreover, assuming that NP is not included in BQP, we also prove that no\nefficient quantum list decoder exists for the generalized Reed-Solomon codes.",
"arxiv_id": "quant-ph/0610200",
"authors": [
"Tomoyuki Yamakami"
],
"categories": [
"quant-ph",
"cs.CC",
"cs.IT",
"math.IT"
],
"doi": "10.22364/bjmc.2016.4.4",
"journal_ref": "Baltic Journal of Modern Computing, Vol. 4 (2016), No. 4, pp.\n 753-788",
"license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
"title": "Quantum List Decoding of Classical Block Codes of Polynomially Small Rate from Quantumly Corrupted Codewords",
"url": "https://arxiv.org/abs/quant-ph/0610200"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "c4efa526-7896-4479-85ac-7f2d21ae99a2",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}