Physics – Quantum Physics
Scientific paper
2006-10-23
Physics
Quantum Physics
A4 size, 24 pages. A complete version of an early paper that appeared in the Proceedings of the 13th Computing: The Australasi
Scientific paper
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. The code rates of all known families of efficiently quantum list-decodable codes, unfortunately, are 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 codeword presence becomes arbitrarily smaller, however, 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: noisy polynomial interpolation problems and bounded distance vector problems. Moreover, assuming that NP is not included in BQP, we prove that there is no efficient quantum list decoder for the generalized Reed-Solomon codes.
No associations
LandOfFree
Quantum List Decoding of Classical Block Codes of Polynomially Small Rate from Quantumly Corrupted Codewords does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quantum List Decoding of Classical Block Codes of Polynomially Small Rate from Quantumly Corrupted Codewords, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum List Decoding of Classical Block Codes of Polynomially Small Rate from Quantumly Corrupted Codewords will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-277504