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

arXiv:quant-ph/0208062 · 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• 141 citations
arXivHTMLPDF
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•69 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•199 citations

Two Families of Optimal Quantum Locally Recoverable Codes

Dengcheng Xie, Shixin Zhu, Zhonghua Sun

International Journal of Theoretical Physics•Mar 21, 2025•8 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

Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case

Srinivasan Arunachalam, João Fernando Doriguello

We prove a hypercontractive inequality for matrix-valued functions defined over large alphabets. In order to do so, we prove a generalization of the powerful 2-uniform convexity inequality for trace norms of Ball, Carlen, Lieb (Inventiones Mathematicae’94). Using our hypercontractive inequality, we present upper and lower bounds for the communication complexity of the Hidden Hypermatching problem defined over large alphabets. We then consider streaming algorithms for approximating the value of Unique Games on a hypergraph with t -size hyperedges. By using our communication lower bound, we show that every streaming algorithm in the adversarial model achieving an \((r-\varepsilon)\) -approximation of this value requires \(\Omega (n^{1-2/t})\) quantum space, where r is the alphabet size. We next present a lower bound for locally decodable codes ( \(\mathsf {LDC}\) ) \(\mathbb {Z}_r^n\rightarrow \mathbb {Z}_r^N\) over large alphabets with recoverability probability at least \(1/r + \varepsilon\) . Using hypercontractivity, we give an exponential lower bound \(N= 2^{\Omega (\varepsilon ^4 n/r^4)}\) for 2-query (possibly non-linear) \(\mathsf {LDC}\) s over \(\mathbb {Z}_r\) and using the non-commutative Khintchine inequality we prove an improved lower bound of \(N= 2^{\Omega (\varepsilon ^2 n/r^2)}\) .

arXiv:2109.02600•ACM Transactions on Computation Theory•Aug 27, 2024•3 citations

Quantum Locally Recoverable Codes With Asymmetric Locality

Jiang Li, Lingfei Jin, Chaoping Xing

IEEE Transactions on Information Theory•Jun 22, 2026•1 citation
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 a hypercontractive inequality for matrix-valued functions defined over large alphabets. In order to do so, we prove a generalization of the powerful 2-uniform convexity inequality for trace norms of Ball, Carlen, Lieb (Inventiones Mathematicae’94). Using our hypercontractive inequality, we present upper and lower bounds for the communication complexity of the Hidden Hypermatching problem defined over large alphabets. We then consider streaming algorithms for approximating the value of Unique Games on a hypergraph with t -size hyperedges. By using our communication lower bound, we show that every streaming algorithm in the adversarial model achieving an (r−ε)(r-\varepsilon)(r−ε) -approximation of this value requires Ω(n1−2/t)\Omega (n^{1-2/t})Ω(n1−2/t) quantum space, where r is the alphabet size. We next present a lower bound for locally decodable codes ( LDC\mathsf {LDC}LDC ) Zrn→ZrN\mathbb {Z}_r^n\rightarrow \mathbb {Z}_r^NZrn​→ZrN​ over large alphabets with recoverability probability at least 1/r+ε1/r + \varepsilon1/r+ε . Using hypercontractivity, we give an exponential lower bound N=2Ω(ε4n/r4)N= 2^{\Omega (\varepsilon ^4 n/r^4)}N=2Ω(ε4n/r4) for 2-query (possibly non-linear) LDC\mathsf {LDC}LDC s over Zr\mathbb {Z}_rZr​ and using the non-commutative Khintchine inequality we prove an improved lower bound of N=2Ω(ε2n/r2)N= 2^{\Omega (\varepsilon ^2 n/r^2)}N=2Ω(ε2n/r2) .