Physics – Quantum Physics
Scientific paper
2002-08-09
Physics
Quantum Physics
16 pages Latex. 2nd version: title changed, large parts rewritten, some results added or improved
Scientific paper
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.
Kerenidis Iordanis
Wolf Ronald de
No associations
LandOfFree
Exponential Lower Bound for 2-Query Locally Decodable Codes via a Quantum Argument does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Exponential Lower Bound for 2-Query Locally Decodable Codes via a Quantum Argument, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exponential Lower Bound for 2-Query Locally Decodable Codes via a Quantum Argument will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-666923