BEGIN:VCALENDAR
VERSION:2.0
PRODID:ILLC Website
BEGIN:VEVENT
UID:/NewsandEvents/Events/Upcoming-Events/newsitem
/298/24-October-2002-Quantum-computing-and-locally
-decodable-codes-Ronald-de-Wolf
DTSTAMP:20021017T000000
SUMMARY:Quantum computing and locally decodable co
des, Ronald de Wolf
ATTENDEE;ROLE=Speaker:Ronald de Wolf (CWI)
DTSTART:20021024T160000
DTEND:20021024T000000
LOCATION:CWI portacabins downstairs seminar room (
C001)
DESCRIPTION:A locally decodable code is an error-c
orrecting code (encoding an n-bit x in m-bit codew
ord C(x)) that allows one to recover any bit x_i f
rom a corrupted version of C(x) while querying onl
y a few positions in the corrupted codeword. We us
e a quantum argument to prove that 2-query LDCs ne
ed exponential length. Previously this was known o
nly for linear codes (Goldreich et al 02). Our p
roof shows that a 2-query LDC can be decoded with
only 1 quantum query, and then proves an exponenti
al lower bound for such 1-query locally quantum-de
codable 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 cl
assical lower bounds and quantum upper bounds for
the setting of private information retrieval. In p
articular, we exhibit a quantum 2-server PIR schem
e with O(n^{0.3}) qubits of communication, beating
the O(n^{1/3})communication of the best known cla
ssical 2-server PIR. This is joint work with Iorda
nis Kerenidis (UC Berkeley). The paper is avail
able at http://www.cwi.nl/~rdewolf/publ/qc/qldc.ps
.gz For more information, see http://www.cwi.nl/~r
oehrig/quantum-seminar.html.
X-ALT-DESC;FMTTYPE=text/html:\n \n
A locally decodable code is an error-correcting co
de (encoding an n-bit\nx in m-bit codeword C(x)) t
hat allows one to recover any bit x_i from a\ncorr
upted version of C(x) while querying only a few po
sitions in the corrupted\ncodeword. We use a quan
tum argument to prove that 2-query LDCs need \nexp
onential length. Previously this was known only f
or linear codes \n(Goldreich et al 02).

\n <
p>\nOur proof shows that a 2-query LDC can be deco
ded with only 1 quantum query, \nand then proves a
n exponential lower bound for such 1-query locally
\nquantum-decodable codes. We also show that q qu
antum queries allow more\nsuccinct LDCs than the b
est known LDCs with q classical queries. \nFinall
y, we give new classical lower bounds\nand quantum
upper bounds for the setting of private informati
on retrieval. In\nparticular, we exhibit a quantum
2-server PIR scheme with O(n^{0.3}) qubits of\nco
mmunication, beating the O(n^{1/3})communication o
f the best known classical\n2-server PIR. This is
joint work with Iordanis Kerenidis (UC Berkeley).\
n \n \n \n The paper is
available at\nhttp://www.cw
i.nl/~rdewolf/publ/qc/qldc.ps.gz\n For
more information, see\nhtt
p://www.cwi.nl/~roehrig/quantum-seminar.html.\
n

\n
URL:/NewsandEvents/Events/Upcoming-Events/newsitem
/298/24-October-2002-Quantum-computing-and-locally
-decodable-codes-Ronald-de-Wolf
END:VEVENT
END:VCALENDAR