Exponential Lower Bound for 2-Query Locally Decodable Codes via a Quantum Argument
| dc.creator | Kerenidis, Iordanis | |
| dc.creator | de Wolf, Ronald | |
| dc.date | 2002-08-09 | |
| dc.date | 2002-11-05 | |
| dc.date.accessioned | 2026-07-07T06:04:44Z | |
| dc.date.available | 2026-07-07T06:04:44Z | |
| dc.description | A locally decodable code encodes n-bit strings x in m-bit codewords C(x), in such a way that one can recover any bit x_i from a corrupted codeword by querying only a few bits of that word. We use a quantum argument to prove that LDCs with 2 classical queries need exponential length: m=2^{Omega(n)}. 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^{3/10}) qubits of communication, improving upon the O(n^{1/3}) bits of communication of the best known classical 2-server PIR. | |
| dc.description | 16 pages Latex. 2nd version: title changed, large parts rewritten, some results added or improved | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0208062 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0208062 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/90410 | |
| dc.subject | Quantum Physics | |
| dc.subject | Computational Complexity | |
| dc.title | Exponential Lower Bound for 2-Query Locally Decodable Codes via a Quantum Argument | |
| dc.type | text |