Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Journal of Computer and System Sciences

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

Iordanis Kerenidis, Ronald de Wolf

Published Aug 4, 2004• 105 citations
Publisher
DOI
10.1016/j.jcss.2004.04.007

Related papers

Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval

Stephanie Wehner, Ronald de Wolf

arXiv:quant-ph/0403140•Lecture notes in computer science•Jan 1, 2005•52 citations

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

Iordanis Kerenidis, Ronald de Wolf

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 xi 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(n3/10) qubits of communication, improving upon the O(n1/3) bits of communication of the best known classical 2-server PIR.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 2003•25 citations

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

Iordanis Kerenidis, Ronald de Wolf

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 xi 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(n3/10) qubits of communication, improving upon the O(n1/3) bits of communication of the best known classical 2-server PIR.

ACM Symposium on Theory of Computing (STOC)•Jun 9, 2003•194 citations

Two Families of Optimal Quantum Locally Recoverable Codes

Dengcheng Xie, Shixin Zhu, Zhonghua Sun

International Journal of Theoretical Physics•Mar 21, 2025•3 citations

Exponential Lower Bound for 2-Query Locally Decodable Codes

Iordanis Kerenidis, Ronald de Wolf

We prove exponential lower bounds on the length of 2-query locally decodable codes. Goldreich et al. recently proved such bounds for the special case of linear locally decodable codes. Our proof shows that a 2-query locally decodable code 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 exhibit q-query locally quantum-decodable codes that are much shorter than the best known q-query classical codes. Finally, we give some new lower bounds for (not necessarily linear) private information retrieval systems.

arXiv:quant-ph/0208062•Electronic colloquium on computational complexity•Jan 1, 2002•4 citations

Quantum Locally Recoverable Codes With Asymmetric Locality

Jiang Li, Lingfei Jin, Chaoping Xing

IEEE Transactions on Information Theory•Jun 22, 2026•0 citations
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 xi 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(n3/10) qubits of communication, improving upon the O(n1/3) bits of communication of the best known classical 2-server PIR.
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 xi 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(n3/10) qubits of communication, improving upon the O(n1/3) bits of communication of the best known classical 2-server PIR.
We prove exponential lower bounds on the length of 2-query locally decodable codes. Goldreich et al. recently proved such bounds for the special case of linear locally decodable codes. Our proof shows that a 2-query locally decodable code 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 exhibit q-query locally quantum-decodable codes that are much shorter than the best known q-query classical codes. Finally, we give some new lower bounds for (not necessarily linear) private information retrieval systems.