Universiteit van Amsterdam

Events

Institute for Logic, Language and Computation

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.