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 require exponential length:
m=2^Omega(n). Previously this was known only for linear codes (Goldreich et al. 02). The proof proceeds by showing that a 2-query LDC can be decoded with a single quantum query, when defined in an appropriate sense. It goes on to establish an exponential lower bound on any `1-query locally quantum-decodable code'. This result is still the only exponential lower bound known for general LDCs. We also somewhat improve the polynomial lower bounds by Katz and Trevisan for LDCs with more than 2 queries.
This is joint work with Jordan Kerenidis from STOC 2003.
Copyright. All Rights Reserved.