News and Events: Upcoming Events

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

Speaker: Ronald de Wolf (CWI)
Date: Thursday 24 October 2002
Time: 16:00
Location: CWI portacabins downstairs seminar room (C001)

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.