BEGIN:VCALENDAR
VERSION:2.0
PRODID:ILLC Website
X-WR-TIMEZONE:Europe/Amsterdam
BEGIN:VTIMEZONE
TZID:Europe/Amsterdam
X-LIC-LOCATION:Europe/Amsterdam
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:19700329T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:19701025T030000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:/NewsandEvents/Archives/2002/newsitem/298/24-O
 ctober-2002-Quantum-computing-and-locally-decodabl
 e-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;TZID=Europe/Amsterdam:20021024T160000
DTEND;TZID=Europe/Amsterdam: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      <p>\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).</p>\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      </p>\n    \n      <p>\n        The paper is
  available at\n<a target="_blank" href="http://www
 .cwi.nl/~rdewolf/publ/qc/qldc.ps.gz">http://www.cw
 i.nl/~rdewolf/publ/qc/qldc.ps.gz</a>\n        For 
 more information, see\n<a target="_blank" href="ht
 tp://www.cwi.nl/~roehrig/quantum-seminar.html">htt
 p://www.cwi.nl/~roehrig/quantum-seminar.html</a>.\
 n      </p>\n    
URL:/NewsandEvents/Archives/2002/newsitem/298/24-O
 ctober-2002-Quantum-computing-and-locally-decodabl
 e-codes-Ronald-de-Wolf
END:VEVENT
END:VCALENDAR