Exponential lower bound for 2-query locally decodable codes via a quantum argument

ABSTRACT

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^Ω(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.

REFERENCES

• 1: Andris Ambainis, Upper Bound on Communication Complexity of Private Information Retrieval, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.401-407, July 07-11, 1997
• 2: László Babai , Lance Fortnow , Leonid A. Levin , Mario Szegedy, Checking computations in polylogarithmic time, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.21-32, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103428]
• 3: László Babai , Lance Fortnow , Noam Nisan , Avi Wigderson, BPP has subexponential time simulations unless EXPTIME has publishable proofs, Computational Complexity, v.3 n.4, p.307-318, Oct. 1993 [doi>10.1007/BF01275486]
• 4: Donald Beaver , Joan Feigenbaum, Hiding Instances in Multioracle Queries, Proceedings of the 7th Annual Symposium on Theoretical Aspects of Computer Science, p.37-48, February 22-24, 1990
• 5: R. Beigel, L. Fortnow, and W. Gasarch. Nearly tight bounds for private information retrieval systems. Technical Note 2002-L001N, NEC Laboratories America, 2002.
• 6: Amos Beimel , Yuval Ishai , Eyal Kushilevitz , Jean-François Raymond, Breaking the O(n1/(2k-1)) Barrier for Information-Theoretic Private Information Retrieval, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.261-270, November 16-19, 2002
• 7: H. Buhrman , P. B. Miltersen , J. Radhakrishnan , S. Venkatesh, Are bitvectors optimal?, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.449-458, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335357]
• 8: Benny Chor , Eyal Kushilevitz , Oded Goldreich , Madhu Sudan, Private information retrieval, Journal of the ACM (JACM), v.45 n.6, p.965-981, Nov. 1998 [doi>10.1145/293347.293350]
• 9: Richard Cleve , Wim van Dam , Michael Nielsen , Alain Tapp, Quantum Entanglement and the Communication Complexity of the Inner Product Function, Selected papers from the First NASA International Conference on Quantum Computing and Quantum Communications, p.61-74, February 17-20, 1998
• 10: Wim van Dam, Quantum Oracle Interrogation: Getting All Information for Almost Half the Price, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.362, November 08-11, 1998
• 11: Amit Deshpande , Rahul Jain , T. Kavitha , Jaikumar Radhakrishnan , Satyanarayana V. Lokam, Better Lower Bounds for Locally Decodable Codes, Proceedings of the 17th IEEE Annual Conference on Computational Complexity, p.184, May 21-24, 2002
• 12: Joan Feigenbaum , Lance Fortnow, Random-self-reducibility of complete sets, SIAM Journal on Computing, v.22 n.5, p.994-1005, Oct. 1993 [doi>10.1137/0222061]
• 13: Peter Gemmell , Richard Lipton , Ronitt Rubinfeld , Madhu Sudan , Avi Wigderson, Self-testing/correcting for polynomials and for approximate functions, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.33-42, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103429]
• 14: Peter Gemmell , Madhu Sudan, Highly resilient correctors for polynomials, Information Processing Letters, v.43 n.4, p.169-174, Sept. 28, 1992 [doi>10.1016/0020-0190(92)90195-2]
• 15: Oded Goldreich , Howard Karloff , Leonard J. Schulman , Luca Trevisan, Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval, Proceedings of the 17th IEEE Annual Conference on Computational Complexity, p.175, May 21-24, 2002
• 16: Jonathan Katz , Luca Trevisan, On the efficiency of local decoding procedures for error-correcting codes, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.80-86, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335315]
• 17: Hartmut Klauck , Ashwin Nayak , Amnon Ta-Shma , David Zuckerman, Interaction in quantum communication and the complexity of set disjointness, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.124-133, July 2001, Hersonissos, Greece [doi>10.1145/380752.380786]
• 18: R. Lipton. New directions in testing. In Proceedings of DIMACS Workshop on Distributed Computing and Cryptography, 1989
• 19: Chi-Jen Lu , Omer Reingold , Salil Vadhan , Avi Wigderson, Extractors: optimal up to constant factors, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780630]
• 20: Ashwin Nayak, Optimal Lower Bounds for Quantum Automata and Random Access Codes, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.369, October 17-18, 1999
• 21: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 22: Kenji Obata, Optimal Lower Bounds for 2-Query Locally Decodable Linear Codes, Proceedings of the 6th International Workshop on Randomization and Approximation Techniques, p.39-50, September 13-15, 2002
• 23: Alexander Polishchuk , Daniel A. Spielman, Nearly-linear size holographic proofs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.194-203, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195132]
• 24: J. Radhakrishnan , P. Sen , S. Venkatesh, The quantum complexity of set membership, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.554, November 12-14, 2000
• 25: Pranab Sen , S. Venkatesh, Lower Bounds in the Quantum Cell Probe Model, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.358-369, July 08-12, 2001
• 26: M. Sipser and D. A. Spielman. Expander codes. IEEE Transactions on Information Theory, 42:1710--1722, 1996. Earlier version in FOCS'94.
• 27: Madhu Sudan , Luca Trevisan , Salil Vadhan, Pseudorandom generators without the XOR Lemma (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.537-546, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301397]

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Error control codes

General Terms:
Algorithms, Theory

Keywords:
locally decodable codes, private information retrieval, quantum computing