Please note that this newsitem has been archived, and may contain outdated information or links.
24 October 2002, Quantum computing and locally decodable codes, Ronald de Wolf
A locally decodable code is an error-correcting code (encoding an n-bit x in m-bit codeword C(x)) that allows one to recover any bit x_i from a corrupted version of C(x) while querying only a few positions in the corrupted codeword. We use a quantum argument to prove that 2-query LDCs need exponential length. Previously this was known only for linear codes (Goldreich et al 02).
Our proof shows that a 2-query LDC can be decoded with only 1 quantum query, and then proves an exponential lower bound for such 1-query locally quantum-decodable codes. We also show that q quantum queries allow more succinct LDCs than the best known LDCs with q classical queries. Finally, we give new classical lower bounds and quantum upper bounds for the setting of private information retrieval. In particular, we exhibit a quantum 2-server PIR scheme with O(n^{0.3}) qubits of communication, beating the O(n^{1/3})communication of the best known classical 2-server PIR. This is joint work with Iordanis Kerenidis (UC Berkeley).
The paper is available at http://www.cwi.nl/~rdewolf/publ/qc/qldc.ps.gz For more information, see http://www.cwi.nl/~roehrig/quantum-seminar.html.
Please note that this newsitem has been archived, and may contain outdated information or links.