Exponential Lower Bound for 2-Query Locally Decodable Codes via a Quantum Argument
<|reference_start|>Exponential Lower Bound for 2-Query Locally Decodable Codes via a Quantum Argument: 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.<|reference_end|>
@article{kerenidis2002exponential,
    title={Exponential Lower Bound for 2-Query Locally Decodable Codes via a
  Quantum Argument},
    author={Iordanis Kerenidis (UC Berkeley) and Ronald de Wolf (CWI, Amsterdam)},
    journal={arXiv preprint arXiv:quant-ph/0208062},
    year={2002},
    archivePrefix={arXiv},
    eprint={quant-ph/0208062},
    primaryClass={quant-ph cs.CC}
}