Exponential lower bound for 2-query locally decodable codes via a quantum argument.
A locally decodable code (LDC) 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 require exponential 2(n). Previously, this was known only for linear codes (Goldreich et al., in: Proceedings of 17th IEEE Conference on Computation Complexity, 2002, pp. 175-183). 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 'l-query locally quantum-decodable code'. We extend our lower bounds to non-binary alphabets and also somewhat improve the polynomial lower bounds by Katz and Trevisan for LDCs with more than 2 queries. Furthermore, we 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 private information retrieval (PIR) scheme with O(n3/10) qubits of communication, beating the O(n1/3) bits of communication of the best known classical 2-server PIR.
Introduction
1.1 Setting
correcting codes allow one to encode an n-bit string x into an m-bit codeword C(x) in
such a way that x can still be recovered even if the codeword is corrupted in a number of places.
For example, codewords of length already su-ce to recover from errors in a constant
fraction of the bitpositions of the codeword, even in linear time [33]. One disadvantage of such
\standard" error correction is that one usually needs to consider all or most of the (corrupted)
A preliminary version of this paper appeared in STOC'03 [22].
y Supported by DARPA under agreement number F 30602{01-2{0524. Part of this work was done when visiting
CWI.
z Most of this work was done while a postdoc at UC Berkeley, supported by Talent grant S 62{565 from the
Netherlands Organization for Scientic Research (NWO). Also (partially) funded by projects QAIP (IST{1999{
and RESQ (IST-2001-37559) of the IST-FET programme of the EC.
codeword to recover anything about x. If one is only interested in recovering one or a few of the
bits of x, then more e-cient schemes are possible, which allow us to extract small parts of encoded
information from a corrupted codeword, while looking at (\querying") only a few positions of
that word. Such schemes are called locally decodable codes (LDCs). They have found various
applications in complexity theory and cryptography, such as self-correcting computations [5, 24,
17, 16, 18], Probabilistically Checkable Proofs [2], worst-case to average-case reductions [3, 34],
private information retrieval [11], and extractors [25]. Informally, LDCs are described as follows:
A (q; -locally decodable code encodes n-bit strings x into m-bit codewords C(x),
such that, for each i, the bit x i can be recovered with probability making only
q queries, even if the codeword is corrupted in -m of the bits.
For example, the Hadamard code is a locally decodable code where two queries su-ce for predicting
any bit with constant advantage, even with a constant fraction of errors. The code has
and . Recovery from a corrupted codeword y is possible
by picking a random j 2 f0; 1g n , querying y j and y je i , and computing the XOR of those two
bits as our guess for x i . If neither of the two queried bits has been corrupted, then we output
as we should. If C(x) has been corrupted in at most
-m positions, then a fraction of at least 1 2- of all (j; j  e i ) pairs of indices is uncorrupted, so
the recovery probability is at least 1 2-. This is > 1=2 as long as - < 1=4. The main drawback
of the Hadamard code is its exponential length.
Clearly, we would like both the codeword length m and the number of queries q to be small.
The main complexity question about LDCs is how large m needs to be, as a function of n, q, -,
and ". For et al. [2] showed how to achieve almost linear size codes, for some
xed - and ". Beimel et al. [8] recently improved the best known upper bounds for constant q to
log q=q log q) , with some more precise bounds for small q.
The study of lower bounds on m was initiated by Katz and Trevisan [21]. They proved that
for do not exist if n is larger than some constant depending on - and ". For q  2,
they proved a bound of
if the q queries are made non-adaptively; this bound
was generalized to the adaptive case by Deshpande et al. [14]. This establishes superlinear (but at
most quadratic) lower bounds on the length of LDCs with a constant number of queries. There
is still a large gap between the best known upper and lower bounds. In particular, it is open
achievable with constant q. Goldreich et al. [20] examined the case
and showed that m  2 -"n=8 if C is a linear code. Obata [29] subsequently strengthened the
dependence on " to m  2
which is essentially optimal. Very recently, Ben-Sasson et
al. [9] studied a relaxed notion of LDCs where the decoder is allowed to output \don't know" for a
constant fraction of the indices. They construct relaxed LDCs with a constant number of queries
Katz and Trevisan, and Goldreich et al. established a close connection between locally decodable
codes and private information retrieval (PIR) schemes. A PIR scheme allows a user to extract a
" from an n-bit database x that is replicated over some k  1 servers,
without the server(s) learning which i the user wants. The main complexity measure of a PIR
scheme is its communication complexity, i.e., the sum of the lengths of the queries that the user
sends to each server, and the length of the servers' answers. Roughly, the queries in an LDC
correspond to the servers in a PIR scheme. In fact, the best known LDCs for constant q are derived
from PIR schemes.
If there is only one server privacy can be maintained by letting the server send
the whole n-bit database to the user. This takes n bits of communication and is optimal. If
the database is replicated over k  2 servers, then there exist protocols with signicantly less
communication. Chor et al. [11] exhibited a 2-server PIR scheme with communication complexity
O(n 1=3 ) and one with O(n 1=k ) for k > 2. Ambainis [1] improved the latter to O(n 1=(2k 1) ). Beimel
et al. [8] improved the communication complexity to O(n 2 log log k=k log k ). Their results improve the
previous best bounds for all k  3 but not for 2.
lower bounds better than
an n) are known for PIRs with k  2 servers. For the
case of 2 servers, the best known lower bound is 4 log n, due to Mann [26]. A PIR scheme is linear
if for every query that the user makes, the answer bits are linear combinations of the bits of x.
Goldreich et al. [20] proved that linear 2-server PIRs with t-bit queries and a-bit answers where
the user looks only at k predetermined positions in each answer require
1.2 Results: Locally Decodable Codes
The main result of this paper is an exponential lower bound for general 2-query LDCs:
Theorem 4 If C : f0; 1g n ! f0; 1g m is a (2; -locally decodable code, then
for
This is the rst superpolynomial lower bound on general LDCs with more than one query. Our
constant c in the exponent is somewhat worse than those of Goldreich et al. [20] and of Obata [29],
but our proof establishes the exponential lower bound for all LDCs, not just linear ones.
Our proof introduces one radically new ingredient: quantum computing. We show that if
two classical queries can recover x i with probability can also be recovered with
probability 1=2+4"=7 using only one \quantum query". In other words, a (2; -locally decodable
code is a (1; -; 4"=7)-locally quantum-decodable code. We then prove an exponential lower bound
for 1-query LQDCs by showing, roughly speaking, that a 1-query LQDC of length m induces a
quantum random access code for x of length about log m. Such a code enables its user to recover
each bit x i of his choice. Nayak's [27] linear lower bound on the length of such codes nishes
the proof. For the sake of completeness, we include a proof of his result in Appendix B.
This lower bound for classical LDCs is one of the very few examples where tools from quantum
computing enable one to prove new results in classical computer science. We know only a few
other examples of this. 1 Radhakrishnan et al. [30] proved lower bounds for the set membership
data structure that hold for quantum algorithms, but are in fact stronger than the previous classical
lower bounds of Buhrman et al. [10]. Sen and Venkatesh did the same for data structures for the
predecessor problem [32, quant-ph version]. Klauck et al. [23] proved lower bounds for the k-round
quantum communication complexity of the tree-jumping problem that are somewhat stronger than
the previous best classical lower bounds. In cryptography, Gisin, Renner, and Wolf [19] used an
analogy with \quantum bound entanglement" to provide evidence against the conjecture that the
\intrinsic information" in a random variable shared by Alice, Bob, and eavesdropper Eve always
equals the amount of secret key that Alice and Bob can extract from this; later this conjecture was
indeed disproved [31], though without using quantum methods. In all these cases, the underlying
proof techniques easily yield a classical proof: one just replaces quantum notions like von Neumann
entropy and trace distance by their classical analogues to get a classical proof for the classical
1 The quantum lower bound on the communication complexity of the inner product function of Cleve et al. [12]
provides new insight in a classical result, but does not establish a new result for classical computer science.
case. In contrast, our proof seems to be more \inherently quantum" since there is no classical
analog of our 2-classical-queries-to-1-quantum-query reduction (2-query LDCs exist but 1-query
don't).
While Section 3 focuses only on codes over the binary alphabet, in Section 4.1 we extend our
result to the case of larger alphabets, using a classical reduction due to Trevisan [35]. In Section 4.2
we look at LDCs with q  3 queries and improve the polynomial lower bounds of Katz and Trevisan
[21]. Our bounds are still polynomial and far from the best known upper bounds. In Section 4.3
we observe that our construction implies the existence of 1-query quantum-decodable codes for
all n. The Hadamard code is an example of this. Here the codewords are still classical, but the
decoder is quantum. As mentioned before, if we only allow one classical query, then LDCs do not
exist for n larger than some constant depending on - and " [21]. For larger q, it turns out that
the best known (2q; -LDCs, due to Beimel et al. [8], are actually (q; -LQDCs. Hence for
xed number of queries q, we obtain LQDCs that are signicantly shorter than the best known
LDCs. In particular, Beimel et al. give a 4-query LDC with length which is a 2-query
LQDC. This is signicantly shorter than the that 2-query LDCs need. We summarize
the situation in Table 1, where our contributions are indicated by boldface.
Queries Length of LDC Length of LQDC
exist 2 (n)

Table

1: Best known bounds on the length of LDCs and LQDCs with q queries
1.3 Results: Private Information Retrieval
In the private information retrieval setting, our techniques allow us to reduce classical 2-server PIR
schemes with 1-bit answers to quantum 1-server PIRs, which in turn can be reduced to a random
access code [27]. Thus in Section 5.1 we obtain an
n) lower bound on the communication
complexity for all classical 2-server PIRs with 1-bit answers. In Section 5.2 we extend our lower
bound to PIR schemes with larger answers. Previously, such a bound was known only for linear
PIRs (rst proven in [11, Section 5.2] for 1-bit answers and extended to constant-length answers
in [20]). Furthermore, our results combined with those of Katz and Trevisan give a 4:4 log n lower
bound for the general 2-server PIR. This is the rst, very modest improvement on the bound of
Mann [26]. Subsequently to our work, Beigel, Fortnow, and Gasarch [7] found a classical proof
that a 2-server PIR with perfect recovery answers needs query length  n 2.
However, their proof does not seem to extend to the case " < 1=2, or to larger answers.
Apart from giving new lower bounds for classical PIR, we can also use our 2-to-1 reduction to
obtain quantum PIR schemes that beat the best known classical PIRs. In particular, Beimel et
al. [8, Example 4.2] exhibit a classical 4-server PIR scheme with 1-bit answers and communication
complexity O(n 3=10 ). We can reduce this to a quantum 2-server PIR with O(n 3=10 ) qubits of
communication. This beats the best known classical 2-server PIR, which has complexity O(n 1=3 ).
We can similarly give quantum improvements over the best known k-server PIR schemes for k > 2.
However, this does not constitute a true classical-quantum separation in the PIR setting yet, since
no good lower bounds are known for classical PIR. We summarize the best known bounds for
classical and quantum PIR in Table 2.
Servers PIR complexity QPIR complexity

Table

2: Best known bounds on the communication complexity of classical and quantum PIR
Preliminaries
2.1 Quantum
Below we give more precise denitions of locally decodable codes, PIR schemes, and related notions,
but we rst explain the standard notation of quantum computing.
Let H denote a 2-dimensional complex vector space, equipped with the standard inner product.
We pick an orthonormal basis for this space, label the two basis vectors j0i and j1i, and for simplicity
identify them with the vectors
and
, respectively. A qubit is a unit length vector in
this space, and so can be expressed as a linear combination of the basis states:
Here are complex amplitudes, and
An m-qubit system is a unit vector in the m-fold tensor space
H. The 2 m basis states
of this space are the m-fold tensor products of the states j0i and j1i. For example, the basis states
of a 2-qubit system are the four 4-dimensional unit vectors
j0i,
j1i,
j0i, and
j1i.
We abbreviate, e.g.,
j0i to j0ij1i, or j1; 0i, or j10i, or even j2i (since 2 is 10 in binary). With
these basis states, an m-qubit state ji is a 2 m -dimensional complex unit vector
We use to denote the conjugate transpose of the vector ji, and hj for the
inner product between states ji and j i. These two states are orthogonal if hj
of ji is k
hji.
A mixed state fp i ig is a classical distribution over pure quantum states, where the system
is in state j i i with probability p i . We can represent a mixed quantum state by the density matrix
which is dened as
j. Note that  is a positive semidenite operator with trace
(sum of diagonal entries) equal to 1. The density matrix of a pure state ji is
A quantum system is called bipartite if it consists of two subsystems. We can describe the state
of each of these subsystems separately with the reduced density matrix. For example, if a quantum
state has the form
then the state of a system holding only the second part of
ji is described by the (reduced) density matrix
A quantum state can evolve by a unitary operation or by a measurement. A unitary transformation
is a linear mapping that preserves the ' 2 norm. If we apply a unitary U to a state ji, it
evolves to U ji. A mixed state  evolves to UU y .
The most general measurement allowed by quantum mechanics is specied by a family of positive
semidenite operators
subject to the condition that
Given
a density matrix , the probability of observing the ith outcome under this measurement is given
by the trace
are nonnegative because E i and  are positive
semidenite. They also sum to 1, as they should:
If the measurement yields outcome i, then the resulting quantum state is M i M
In
particular, if and the resulting state is M i ji=k M i ji k.
A special case is where forms an orthonormal basis of the m-qubit space.
\Measuring in the B-basis" means that we apply the measurement given by
Applying this to a pure state ji gives resulting state j i i with probability
Finally, a word about quantum queries. A query to an m-bit string y is commonly formalized
as the following unitary transformation, where j 2 [m], and b 2 f0; 1g is called the target bit :
A quantum computer may apply this to any superposition. An equivalent formalization that we
will be using here, is:
Here c is a control bit that controls whether the phase ( 1) y j is added or not. Given some extra
workspace, one query of either type can be simulated exactly by one query of the other type.
We refer to Nielsen and Chuang [28] for more details.
2.2 Codes
Below, by a 'decoding algorithm' we mean an algorithm (quantum or classical depending on context)
with oracle access to the bits of some (possibly corrupted) codeword y for x. The algorithm gets
input i and is supposed to recover x i , making only few queries to y. We want to emphasize that we
speak of an 'algorithm' merely as a convenient way to formalize the decoding process. Our focus is
not the algorithmics of the decoding but its information-theoretic aspects, i.e., the tradeo between
the number q of queries allowed for decoding and the required codelength m.
Denition is a (q; -locally decodable code (LDC) if there is a classical
randomized decoding algorithm A such that
1. A makes at most q queries to m-bit string y, non-adaptively.
2. For all x and i, and all y 2 f0; 1g m with Hamming distance d(C(x); y)  -m we have
Pr[A y
The LDC is called linear if C is a linear function over GF (2) (i.e., C(x
By allowing A to be a quantum computer and to make queries in superposition, we can similarly
dene (q; -locally quantum-decodable codes (LQDCs).
It will be convenient to work with non-adaptive queries, as used in the above denition, so the
distribution on the queries that A makes is independent of y. However, our main lower bound also
holds for adaptive queries, see the rst remark at the end of Section 3.3.
2.3 Private Information Retrieval
Next we dene private information retrieval schemes.
Denition 2 A one-round, (1 -secure, k-server private information retrieval (PIR) scheme with
recovery probability t, and answer size a, consists of a randomized algorithm
(the user), and k deterministic algorithms S (the servers), such that
1. On input i 2 [n], the user produces k t-bit queries q sends these to the respective
servers. The jth server sends back an a-bit string a The user outputs a bit b
depending on his randomness.
2. For all x and i, the probability (over the user's randomness) that is at least 1=2
3. For all x and j, the distributions on q j (over the user's randomness) are -close (in total
variation distance) for dierent i.
The scheme is called linear if, for every j and q j , the jth server's answer S j (x; q j ) is a linear
combination over GF (2) of the bits of x.
We can straightforwardly generalize these denitions to quantum PIR for the case where
(the server's state after the query should be independent of i). That is the only case we need here.
All known upper bounds on PIR have one round of communication, (perfect recovery) and
servers get no information whatsoever about i). Below we will assume one round and
mentioning this further.
3 Lower Bound for 2-Query Locally Decodable Codes
Our proof has two parts, each with a clear intuition but requiring quite a few technicalities:
1. A 2-query LDC is a 1-query LQDC, because one quantum query can compute the same
Boolean functions as two classical queries (albeit with slightly worse error probability).
2. The length m of a 1-query LQDC must be exponential, because a uniform superposition over
all indices contains only log m qubits, but induces a quantum random access code for x, for
which a linear lower bound is already known [27].
3.1 From 2 Classical to 1 Quantum Query
The key to the rst step is the following lemma:
suppose we can make queries to the bits of some input
string There exists a quantum algorithm that makes only one query (one that is
independent of f) and outputs f(a) with probability exactly 11=14, and outputs 1 f(a) otherwise.
Proof. If we could construct the state
with one quantum query then we could determine a with certainty, since the four possible states
an orthonormal basis. We could also see these states as the Hadamard
encoding of the strings b 2 f0; 1g 2 . Unfortunately we cannot construct j a i perfectly with one
query. Instead, we approximate this state by making the queryp(j0ij1i
where the rst bit is the control bit, and the appropriate phase ( 1) a j is put in front of jji if the
control bit is 1. The result of the query is the state
The algorithm then measures this state ji in the orthonormal basis consisting of the four states
i. The probability of getting outcome a is jhj a ij and each of the other 3 outcomes has
probability 1=12. The algorithm now determines its output based on f and on the measurement
outcome b. We distinguish 3 cases for f :
1. completely analogous, with 0 and 1 reversed). If
then the algorithm outputs 1 with probability 1. If outputs 0 with
probability 6=7 and 1 with probability 1=7. Accordingly, if then the probability of
output 1 is then the
probability of output 0 is
2. 2. Then If the algorithm outputs f(b) with
probability 13=14 and outputs 1 f(b) with probability 1=14, then its probability of output
f(a) is exactly 11=14.
3. f is constant. In that case the algorithm just outputs that value with probability 11=14.
Thus we always output f(a) with probability 11=14. 2
Peter Hyer (personal communication) recently improved the 11=14 in the lemma to 9=10. We
describe his algorithm in Appendix A and show that this success probability is best possible if we
have only one quantum query.
Using our lemma we can prove:
Theorem 1 A (2; -LDC is a (1; -; 4"=7)-LQDC.
Proof. Consider i, x, and y such that d(C(x); y)  -m. The 1-query quantum decoder will use
the same randomness as the 2-query classical decoder. The random string of the classical decoder
determines two indices and an f : f0; 1g 2 ! f0; 1g such that
where the probability is taken over the decoder's randomness. We now use Lemma 1 to obtain a
1-query quantum decoder that outputs some bit b such that
The success probability of this quantum decoder is: 2
4"
as promised. 2
3.2 Lower Bound for 1-Query LQDCs
A quantum random access code is an encoding x 7!  x of n-bit strings x into m-qubit states  x ,
possibly mixed, such that any bit x i can be recovered with some probability p  " from  x .
The following lower bound is known on the length of such quantum codes [27] (see Appendix B).
Theorem 2 (Nayak) An encoding x 7!  x of n-bit strings into m-qubit states with recovery probability
at least p, has m  (1 H(p))n.
This allows us to prove an exponential lower bound for 1-query LQDCs:
Theorem 3 If is a (1; -LQDC, then
for
Proof. Our goal below is to show that we can recover each x i with good probability from a
number of copies of the uniform log(m) + 1-qubit state
The intuitive reason for this is as follows. Since C is an LQDC, it is able to recover x i even from a
codeword that is corrupted in many (up to -m) places. Therefore the \distribution" of queries of the
decoder must be \smooth", i.e., spread out over almost all the positions of the codeword|otherwise
an adversary could choose the corrupted bits in a way that makes the recovery probability too low.
The uniform distribution provides a reasonable approximation to such a \smooth" distribution.
Since the uniform state jU(x)i is independent of i, we can actually recover any bit x i with good
probability, so it constitutes a quantum random access code for x. Applying Theorem 2 then gives
the result.
Here we use the 'exactly' part of Lemma 1. To see what could go wrong if the `exactly' were 'at least', suppose the
classical decoder outputs AND(y1 ; y2
it outputs x i with probability 3=5 > 1=2. However, if our quantum procedure computes AND(y1 ; y2) with success
probability 11=14 but XOR(y3 ; y4 ) with success probability 1, then its recovery probability is (3=5)(11=14) < 1=2.
Let us be more precise. The most general query that the quantum decoder could make to
recover x i , is of the form
where the j cj i are pure states in the decoder's workspace and the  cj are non-negative reals (any
phases could be put in the j cj i). This workspace can also incorporate any classical randomness
used. However, the decoder could equivalently add these workspace states after the query, using
the unitary map jcijjij0i 7! jcijjij cj i. Hence we can assume without loss of generality that the
actual query is
cj jcijji;
and that the decoder just measures the state resulting from this query. Let D and I D be the
two measurement operators that the decoder uses for this measurement, corresponding to outputs
1 and 0, respectively. Its probability of giving output 1 on query-result jRi is
clarity we don't write the ji inside the p()).
Inspired by the smoothing technique of [21], we split the amplitudes  j of the query jQ i i into
small and large ones:
1=-mg. Since the
query does not aect the j0ijji-states, we can assume without loss of generality that  0j is the
same for all j, so  0j  1=
-m and hence (0; A. Let a =
cj be the norm
of the \small-amplitude" part. Since
cj  1, we have jBj < -m. Dene non-normalized
states
(c;j)2A
cj jcijji:
The pure states jA(x)i + jBi and jA(x)i jBi each correspond to a y 2 f0; 1g m that is corrupted
(compared to C(x)) in at most jBj  -m positions, so the decoder can recover x i from each of
these states. If x has x
averaging the previous two inequalities gives
Similarly, if x 0 has x 0
Hence, for the normalized states 1
a jA(x)i and 1
a jA(x 0 )i:
a
a
Since this holds for every x; x 0 with x
there are constants q
, such that p( 1
a
a
If we had a copy of the state 1
a jA(x)i, then we could run the procedure below to recover x i .
Here we assume that q 1  1=2 not, then we must have q 0  1=2 "=a 2 and we can use
the same argument with 0 and 1 reversed), and that q 1
we're already done).
Output 0 with probability
and otherwise output the result of the decoder's 2-outcome measurement on 1
a jA(x)i.
then the probability that this procedure outputs 1 is
a
then the probability that the procedure outputs 0 is
a A(x)
Thus we can recover x i with good probability if we have the state 1
a jA(x)i (which depends on i as
well as x).
It remains to show how we can obtain 1
a jA(x)i from jU(x)i with reasonable probability. This
we do by applying a measurement with operators M y M and I M y M to jU(x)i, where
-m
(c;j)2A  cj jc; jihc; jj. Both M y M and I M y M are positive operators (as required for a
-m cj  1 for all (c; A. The measurement gives the rst
outcome with probability
cj2A
In this case we have obtained the normalized version of M jU(x)i, which is 1
a jA(x)i. Suppose we
have copies of jU(x)i and we do the measurement separately on each of them. Then
with probability 1 (1 -a 2 =2) r  1=2, one of those will give the rst outcome, in which case we
can predict x i with probability
. If all measurements give the second outcome then we just
output a fair coin
ip as our guess for x i . Overall, our recovery probability is now
Accordingly, r copies of the (log(m) + 1)-qubit state jU(x)i form a quantum random access code
with recovery probability p. Using Theorem 2,
hence
log m  -" 2 n
3.3 Lower Bound for 2-Query LDCs
Theorem 4 If C : f0; 1g n ! f0; 1g m is a (2; -locally decodable code, then
for
Proof. The theorem combines Theorem 1 and 3. Straightforwardly, this would give a constant
of -" 2 =(49 ln 2). We get the better constant claimed here by observing that the 1-query LQDC
derived from the 2-query LDC actually has 1=3 of the overall squared amplitude on queries where
the control bit c is zero (and all those  0j are in A). Hence in the proof of Theorem 3, we can
redene \small amplitude" to  cj
2=(3-m), and still B will have at most -m elements because
cj  2=3. This in turns allows us to make M a factor
3=2 larger, which improves the
probability of getting 1
a jA(x)i from jU(x)i to 3-a 2 =4 and allows us to decrease r to 4=(3-a 2 ). This
translates to a lower bound log m  3-" 2 n=(32 ln 2) 1. Combining that with Theorem 1 (which
makes " a factor 4=7 smaller) gives
Remarks:
(1) Note that a (2; -LDC with adaptive queries gives a (2; -; "=2)-LDC with non-adaptive
queries: if query q 1 would be followed by query q 0
2 or q 1
2 depending on the outcome of q 1 , then we
can just guess in advance whether to query q 1 and q 0
2 , or q 1 and q 1
2 . With probability 1/2, the
second query will be the one we would have made in the adaptive case and we're ne, in the other
case we just
ip a coin, giving overall recovery probability 1=2(1=2
Thus we also get slightly weaker but still exponential lower bounds for adaptive 2-query LDCs.
(2) The constant 3=(98 ln 2) can be optimized a bit further by choosing the number r of copies
a bit larger in the proof of Theorem 3 and by using Peter Hyer's 9/10-algorithm (Appendix
instead of our 11/14-algorithm from Lemma 1. More interesting, however, is the question whether
the quadratic dependence on " can be improved.
(3) For a (2; -LDC where the decoder's output is the XOR of its two queries, we can give
a better reduction than in Theorem 1. Now the quantum decoder can query 1
and extract a 1 a 2 from this with certainty. Thus the recovery probability remains
of going down to 1=2+4"=7. Accordingly, we also get better lower bounds for 2-query LDCs where
the output is the XOR of the two queries, with in the exponent.
(4) The second part of our proof is a reduction from a Locally Quantum-Decodable Code to a
\smooth" quantum code and then to a code where the distribution of the queries is uniform. This
reduction is known for classical codes as well (see the next section). Hence, an alternative way to
get the exponential lower bound on m would be rst to invoke the result by Katz and Trevisan
that reduces an LDC to a code with a uniform query distribution. We can reduce further to the
case where the decoder outputs the XOR of the q queried bits. Starting with such a uniformly
smooth code, we can then use our reduction from 2 classical queries to 1 quantum query without
any loss in recovery probability (see Remark 3). After this reduction we immediately end up with
a quantum random access code of log m qubits and we are done. However, this proof would give a
worse dependence on - and " than our current result.
Extensions
In this section we give various extensions and variations of the lower bound of the previous section.
4.1 Non-Binary Alphabets
Here we extend our lower bounds for binary 2-query LDCs to the case of 2-query LDCs over larger
alphabets. For simplicity we assume the alphabet is so a query to position j now returns
an '-bit string C(x) j . The denition of (q; -LDC from Section 2.2 carries over immediately, with
now measuring the Hamming distance between C(x)
We will need the notion of smooth codes and their connection to LDCs as stated in [21].
Denition is a (q; c; ")-smooth code if there is a classical randomized decoding
algorithm A such that
1. A makes at most q queries, non-adaptively.
2. For all x and i we have Pr[A C(x)
3. For all x, i, and j, the probability that on input i machine A queries index j is at most c=m.
Note that smooth codes only require good decoding on codewords C(x), not on y that are close
to C(x). Katz and Trevisan [21, Theorem 1] established the following connection:
Theorem 5 (Katz & Trevisan) A (q; -LDC is a (q; q=-smooth code.
A converse to Theorem 5 also holds: a (q; c; ")-smooth code is a (q; -; " c-LDC, because
the probability that the decoder queries one of -m corrupted positions is at most
Hence LDCs and smooth codes are essentially equivalent, for appropriate choices of the parameters.
To prove the exponential lower bound for LDCs over non-binary alphabet , we will reduce a
smooth code over  to a somewhat longer binary smooth code that works well averaged over x.
Then, we will show a lower bound on such average-case binary smooth codes in a way very similar
to the proof of Theorem 4. The following key lemma was suggested to us by Luca Trevisan [35].
be a (2; c; ")-smooth code. Then there exists a
that is good on average, i.e., there is a decoder
A such that for all
Proof. We form the new binary code C 0 by replacing each symbol C(x) j 2  of the old code by
its Hadamard code, which consists of 2 ' bits. The length of C 0 (x) is m  2 ' bits. The new decoding
algorithm uses the same randomness as the old one. Let us x the two queries and the
output of the old decoder. We will describe a new decoding algorithm
that is good for an average x and looks only at one bit of the Hadamard codes of each of a
First, if for this specic j; k; f we have Pr x [f(a; then the new decoder just outputs
a random bit, so in this case it is at least as good as the old one for an average x. Now consider
the case Pr x [f(a; Switching from the f0; 1g-notation to the
1g-notation enables us to say that 2. Viewing a and b as two '-bit strings, we
can represent f by its Fourier representation (see e.g. [6]): f(a;
s2S a s
and hence
a s
Y
Y
a s
Y
2:
Averaging and using that
it follows that there exist subsets S
a s
Y
a s
Y
Returning to the f0; 1g-notation, we must have either
Pr x
or
Pr x
products mod 2 of '-bit strings. Accordingly, either the XOR of
the two bits S 0 a and T 0 b, or its negation, predicts x i with average probability  1=2+=2 2' . Both
of these bits are in the binary code C 0 (x). The c-smoothness of C translates into c  2 ' -smoothness
of C 0 . Averaging over the classical randomness (i.e. the choice of j; k, and f) gives the lemma. 2
This lemma enables us to modify our proof of Theorem 4 so that it works for non-binary
Theorem 6 If -locally decodable code, then
for
Proof. Using Theorem 5 and Lemma 2, we turn C into a binary (2; 2 '+1 =-; "=2 2' )-smooth code
C 0 that has average recovery probability bits. Since its decoder
XORs its two binary queries, we can reduce this to one quantum query without any loss in the
average recovery probability (see the third remark following Theorem 4).
We now reduce this quantum smooth code to a quantum random access code, by a modied
version of the proof of Theorem 4. The smoothness of C 0 implies that all amplitudes  j (which
depend on i) in the one quantum query satisfy  j
. Hence there is no need to split
the set of j's into A and B. Also, the control bit c will always be 1, so we can ignore it.
Consider the states
jji, and the
2-outcome measurement with operators
I M . The probability
that the measurement takes us from jU(x)i to the renormalized M jU(x)i (= jA(x)i) is equal to
Hence copies of jU(x)i forms a quantum random access
code with average success probability
The (1 H(p))n lower bound for a quantum random access code holds even if the recovery probability
p is only an average over x, which gives
which implies the statement of the theorem. 2
4.2 Bounds for More Than 2 Queries
Here we address the case of LDCs over the binary alphabet where the decoder asks more than 2
queries. There is no obvious way to extend our 2-to-1 reduction to more than 2 classical queries,
since a quantum computer needs dq=2e queries to compute the parity of q bits with any advantage [4,
15]. In particular, it needs 2 quantum queries to compute the parity of 3 bits, and we don't have
any lower bounds for 2-query LQDCs. Still, for LDCs with q  3 queries we were able to improve
the polynomial lower bounds
of Katz and Trevisan [21] somewhat:
Theorem 7 If is a (q; -locally decodable code, then
log n
where the constant under
the
) depends on q, - and ".
Proof. Suppose for simplicity that q is even and m is a multiple of q. By Theorem 5, it su-ces
to prove a bound for a (q; c; ")-smooth code, with We will use the following result to make
the smooth code uniform.
Fact (Katz & Trevisan [21, discussion in Section 4]): A (q; c; ")-smooth code is a (q; q; " 2 =2c)-
smooth code that is good on average. For every i, the new q-query decoder has a xed partition
M i of [m] into m=q q-tuples; it just picks a random q-tuple (j outputs a Boolean
function of the q bits
. For every i, the decoding of x i will be correct with
probability at least 1=2 averaged over all x.
By a proof analogous to Lemma 2, we can ensure that the decoder actually computes the XOR
of the q queried bits (or its negation). The average correctness probability will still be at least
We will derive a quantum random access code from this uniform smooth code. Let
jjihjj be the projector on the states jii and jji. Suppose (i 1
partition of all the q-tuples in M i into pairs. By measuring the uniform state
with operators P
for random 1  '  m=2. From this we can obtain C(x) so we can generate the XOR
of a random pair from the partition. In order to recover x i we need to nd q=2 dierent pairs that
come from the same q-tuple.
Each state jU(x)i gives us a random pair out of the possible m=2. By the Birthday Paradox, if
we have O(m 1 2=q ) copies of the log m-qubit state jU(x)i, then with high probability we will nd
q=2 dierent pairs that come from the same q-tuple and hence be able to recover x i . In other words,
copies of the log m-qubit state jU(x)i constitute an (average) random access code. The
random access code lower bound (Appendix B) now gives
which implies m
For example, for queries our lower bound is m
3 n= log n) 2 ) while Katz and Trevisan
have
4.3 Locally Quantum-Decodable Codes with Few Queries
The third remark of Section 3.3 immediately generalizes to:
Theorem 8 A (2q; -LDC where the decoder's output is the XOR of the 2q queried bits, is a
(q; -LQDC.
LDCs with q queries can be obtained from q-server PIR schemes with 1-bit answers by concatenating
the answers that the servers give to all possible queries of the user. Beimel et al. [8,
Corollary 4.3] recently improved the best known upper bounds on q-query LDCs, based on their
improved PIR construction. They give a general upper bound
for q-query
LDCs, for some constant depending on - and ", as well as more precise estimates for small q. In
particular, for construct an LDC of length are of the
XOR-type, so we can reduce the number of queries by half when allowing quantum decoding. For
instance, their 4-query LDC is a 2-query LQDC with length In contrast, any 2-query
LDC needs length
n) as proved above.
For general LDCs we can do something nearly as good, using van Dam's result that a q-bit
oracle can be recovered with probability nearly 1 using q=2 +O( p q) quantum queries [13]:
Theorem 9 A (q; -LDC is a (q=2 +O( p q); -; "=2)-LQDC.
4.4 Locally Decodable Erasure Codes
Recently, the notion of a Locally Decodable Erasure Code (LDEC) was used in the construction of
extractors [25, Section 3.1]. This is a code where, even if (1 ")m of all positions of the codeword
are erased, we can still recover each x i using only q queries to the remaining positions.
Denition 4 Consider a map We say that message position i is decodable
from codeword positions there exists a function f such that f(C(x) j 1
for all x. C is a (q; ")-LDEC, if for every i, in every "-fraction of the positions of the codeword,
there exists a q-tuple of positions from which i is decodable.
Here we show that LDECs are equivalent to smooth codes, as dened in Section 4.1, and hence
to LDCs. Consider some LDEC with codewords of length m. This equivalence shows that our
lower bounds also hold for LDECs. In particular, (2; ")-LDECs need exponential length.
First consider some LDEC. Take S to be the set of an "-fraction of positions of the codeword. By
denition, there exists a \good" q-tuple in S, i.e., one from which we can decode message position
i. Remove these q positions of the codeword from S and replace them by some other q positions.
Now in this new set S 0 of positions there should still be a \good" q-tuple. Remove it and go on.
You can repeat this substitution (1 ")m=q times, where m is the size of the code. Therefore, there
are
m) disjoint q-tuples that are \good" for x i and so the code is a smooth code: the smooth
decoder just picks one of these tuples at random and queries it positions.
The converse is also true. A smooth code
contains
m) disjoint q-tuples, say m of them, that
are \good" for x i . Hence, in any subset of the positions of the codeword of size (1 )m+ 1, there
exists a \good" q-tuple and therefore the code is an LDEC with "  1 .
5 Private Information Retrieval
As mentioned, there is a close connection between locally decodable codes and private information
retrieval. In this section we use a variant of our 2-to-1 reduction to prove new lower bounds for
PIR and new upper bounds for QPIR.
5.1 Lower Bounds for Binary 2-Server PIR
To get lower bounds for 2-server PIRs with 1-bit answers, we again give a 2-step proof: a reduction
of 2 classical servers to 1 quantum server, combined with a lower bound for 1-server quantum PIR.
Theorem 10 If there exists a classical 2-server PIR scheme with t-bit queries, 1-bit answers, and
recovery probability ", then there exists a quantum 1-server PIR scheme with
recovery probability
Proof. The proof is analogous to the proof for locally decodable codes (Theorem 1). If we let
the quantum user employ the same randomness as the classical one, the problem boils down to
computing some f(a 1 ; a 2 ), where a 1 is the rst server's 1-bit answer to query q 1 , and a 2 is the
second server's 1-bit answer to query q 2 . However, in addition we now have to hide i from the
quantum server. This we do by making the quantum user set up the (4
where '0 t ' is a string of t 0s. The user sends everything but the rst register to the server. The
state of the server is now a uniform mixture of j0; 0 t i, j1; q 1 i, and j2; q 2 i. By the security of the
classical protocol, j1; q 1 i contains no information about i (averaged over the user's randomness),
and the same holds for j2; q 2 i. Hence the server gets no information about i.
The quantum server then puts ( 1) a j in front of jj; q j i (j 2 f1; 2g), leaves j0; 0 t i alone, and
sends everything back. Note that we need to supply the name of the classical server j 2 f1; 2g to
tell the server in superposition whether it should play the role of server 1 or 2. The user now
From this we can compute f(a 1 ; a 2 ) with success probability exactly 11=14, giving overall recovery
probability as in Theorem 1. 2
Combining the above reduction with the quantum random access code lower bound, we obtain
the
rst
n) lower bound that holds for all 1-bit-answer 2-server PIRs, not just for linear ones.
Theorem 11 A classical 2-server PIR scheme with t-bit queries, 1-bit answers, and recovery probability
2.
Proof. We rst reduce the 2 classical servers to 1 quantum server in the way of Theorem 10.
Now consider the state of the quantum PIR scheme after the user sends his
r
Here the p r are the classical probabilities of the user (these depend on i) and q j (r; i) is the t-bit
query that the user sends to server j in the classical 2-server scheme, if he wants x i and has random
string r. Letting be the server's basis states, we can write j i i as:
Here the ja ib i are pure states that do not depend on x. The coe-cients  b are non-negative reals
that do not depend on i, for otherwise a measurement of b would give the server information about
contradicting privacy. The server then tags on the appropriate phase s bx , which is 1 for
2g. This gives
b ja ib is bx jbi:
Now the following pure state will be a random access code for x
because a user can unitarily map j0ijbi 7! ja ib ijbi to map j0ij x i 7! j ix i, from which he can get
by completing the quantum PIR protocol. The state j x i has
qubits, hence from Theorem 2 we obtain t  (1 H(p))n 2. 2
For the special case where the classical PIR outputs the XOR of the two answer bits, we can
improve our lower bound to t  (1 H(1=2 "))n 1. In particular, t  n 1 in case of perfect
recovery which is tight.
5.2 Lower Bounds for 2-Server PIR with Larger Answers
We can also extend our linear lower bound on 2-server PIR schemes with answer length
(Theorem 11) to the case of 2-server PIR larger answer length. We use the translation from PIR
to smooth codes given by Lemma 7.1 of Goldreich et al. [20]:
Lemma 3 (GKST) If there is a classical 2-server PIR scheme with query length t, answer length
a, and recovery probability ", then there is a (2; 3; ")-smooth code
Going through roughly the same steps as for the proof of Theorem 6, we obtain:
Theorem 12 A classical 2-server PIR scheme with t-bit queries, a-bit answers, and recovery probability
5.3 Lower Bounds for General 2-Server PIR
The previous lower bounds on the query length of 2-server PIR schemes were signicant only for
protocols with short answer length. Here we slightly improve the best known bound of 4 log n [26]
on the overall communication complexity of 2-server PIR schemes, by combining our Theorem 12
and Theorem 6 of Katz and Trevisan [21]. We restate their theorem here for the PIR setting. For
the remainder of this section, we assume " to be some xed positive constant.
Theorem 13 (Katz & Trevisan) Every 2-server PIR scheme with t-bit queries and a-bit answers
has
a
We now prove the following lower bound on the total communication a) of any
2-server PIR scheme with t-bit queries and a-bit answers:
Theorem 14 Every 2-server PIR scheme has total communication
C  (4:4 o(1)) log n:
Proof. We distinguish three cases, depending on the answer length of the scheme. Let
log log n= log n.
case 1: a  (0:2 -) log n. Then from Theorem 12 we get that C
4648 n) 5 ).
case 2: (0:2 -) log n < a < 2:2 log n. Then from Theorem 13 we have
case 3: a  2:2 log n. Then obviously log n.5.4 Upper Bounds for Quantum PIR
The best known LDCs are derived from classical PIR schemes with 1-bit answers where the output
is the XOR of the 1-bit answers that the user receives. By allowing quantum queries, we can
reduce the number of queries by half to obtain more e-cient LQDCs. Similarly, we can also turn
the underlying classical k-server PIRs directly into quantum PIRs with k=2 servers.
Most interestingly, there exists a 4-server PIR with 1-bit answers and communication complexity
O(n 3=10 ) [8, Example 4.2]. This gives us a quantum 2-server PIR scheme with O(n 3=10 )
communication, improving upon the communication required by the best known classical 2-server
PIR scheme, which has been O(n 1=3 ) ever since the introduction of PIR by Chor et al. [11]. In the
introduction we mentioned also some quantum upper bounds for k > 2 servers, which are obtained
similarly.
6 Conclusion and Open problems
This paper is the rst where a new classical result is proved using techniques from quantum computing
in an apparently essential way (at least, we don't know a classical proof of the same result).
Clearly, it would be very interesting to nd other such applications. This would much broaden
the relevance of quantum computing and make it less conditional on whether an actual quantum
computer will ever be built.
There are also many interesting open questions related to the tradeos between the various
parameters in LDCs. In particular, it is still open whether one can achieve using
only a constant (or even sublogarithmic) number of queries. We would like to obtain better lower
bounds for q > 2 queries and explore the connections of LDCs to other combinatorial constructions.
Similarly, the main complexity questions about general PIR schemes are still wide open, even
for the 2-server case if we don't restrict the answer size. The O(n 1=3 )-protocol of [11] has been the
best known for a long time for the 2-server case, and it would be very nice to show that this is
close to optimal. Finally, we exhibited 2-server quantum PIR schemes that are more e-cient than
the best known classical ones. It would be very interesting to improve these further, and to prove
that QPIR is more e-cient than the best (rather than the best known) classical PIR schemes.

Acknowledgments

We would like to thank Luca Trevisan for many insightful comments throughout this work and
also for allowing us to include Lemma 2 in Section 4.1. We also thank Harry Buhrman, Richard
Gill, Peter Hyer, Hartmut Klauck, Ashwin Nayak, Kenji Obata, Pranab Sen (and via him also
Rahul Jain), Mario Szegedy, Ashish Thapliyal, John Tromp, and Stephanie Wehner for helpful
discussions. We thank Amos Beimel for sending us a version of [8], Bill Gasarch for sending us
a version of [7], Claude Crepeau and Nicolas Gisin for references to [19, 31], and the anonymous
JCSS referee for many comments that improved the presentation of the paper.



--R

Upper bound on communication complexity of private information retrieval.
Checking computations in polylogarithmic time.
BPP has subexponential time simulations unless EXPTIME has publishable proofs.
Quantum lower bounds by polynomials.
Hiding instances in multioracle queries.
The polynomial method in circuit complexity.
Nearly tight bounds for private information retrieval systems.
Breaking the O(n 1
Robust PCPs of proximity
Are bitvectors optimal?
Private information retrieval.
Quantum entanglement and the communication complexity of the inner product function.
Quantum oracle interrogation: Getting all information for almost half the price.
Better lower bounds for locally decodable codes.
A limit on the speed of quantum computation in determining parity.


Highly resilient correctors for polynomials.
Linking classical and quantum key agreement: Is there a classical analog to bound entanglement?

On the e-ciency of local decoding procedures for error-correcting codes
Exponential lower bound for 2-query locally decodable codes via a quantum argument
Interaction in quantum communication and the complexity of set disjointness.
New directions in testing.
Extractors: Optimal up to constant factors.
Private access to distributed information.
Optimal lower bounds for quantum automata and random access codes.
Quantum Computation and Quantum Information.
Optimal lower bounds for 2-query locally decodable linear codes
The quantum complexity of set membership.
New bounds in secret-key agreement: The gap between formation and secrecy extraction
Lower bounds in the quantum cell probe model.
Expander codes.
Pseudorandom generators without the XOR lemma.
Personal communication
--TR
Hiding instances in multioracle queries
Checking computations in polylogarithmic time
Self-testing/correcting for polynomials and for approximate functions
Highly resilient correctors for polynomials
Random-self-reducibility of complete sets
BPP has subexponential time simulations unless EXPTIME has publishable proofs
Private information retrieval
Pseudorandom generators without the XOR Lemma (extended abstract)
On the efficiency of local decoding procedures for error-correcting codes
Are bitvectors optimal?
Interaction in quantum communication and the complexity of set disjointness
Quantum lower bounds by polynomials
Breaking the O(n1/(2k-1)) Barrier for Information-Theoretic Private Information Retrieval
Quantum Entanglement and the Communication Complexity of the Inner Product Function
Lower Bounds in the Quantum Cell Probe Model
Upper Bound on Communication Complexity of Private Information Retrieval
Optimal Lower Bounds for 2-Query Locally Decodable Linear Codes
Exponential lower bound for 2-query locally decodable codes via a quantum argument
Extractors
Quantum Oracle Interrogation
Optimal Lower Bounds for Quantum Automata and Random Access Codes
The quantum complexity of set membership
Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval
Better Lower Bounds for Locally Decodable Codes
Robust pcps of proximity, shorter pcps and applications to coding

--CTR
Richard Beigel , Lance Fortnow , William Gasarch, A tight lower bound for restricted PIR protocols, Computational Complexity, v.15 n.1, p.82-91, January 2006
Sergey Yekhanin, Towards 3-query locally decodable codes of subexponential length, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
Ashwin Nayak , Julia Salzman, Limits on the ability of quantum states to convey classical messages, Journal of the ACM (JACM), v.53 n.1, p.184-206, January 2006
locally decodable codes;private information retrieval;quantum computing