format: text

text:
# The role of body rotation in bacterial flagellar bundling

(January 28, 2002)

## Abstract

In bacterial chemotaxis, E. coli cells drift up chemical gradients by a series of runs and tumbles. Runs are periods of directed swimming, and tumbles are abrupt changes in swimming direction. Near the beginning of each run, the rotating helical flagellar filaments which propel the cell form a bundle. Using resistive-force theory, we show that the counter-rotation of the cell body necessary for torque balance is sufficient to wrap the filaments into a bundle, even in the absence of the swirling flows produced by each individual filament.

Although bacteria are among the simplest systems for the study of cell motility, many puzzles remain. Chief among these is the mechanics of the bundling and unbundling of flagellar filaments in the chemotaxis behavior of bacteria such as E. coli and Salmonella macnab\_ornston1977 ; bray1992 . These cells move toward higher concentrations of favorable chemicals by executing a series of runs and tumbles berg1993 . The runs are periods of directed swimming. At the end of each run, the cell randomizes its direction by tumbling. If the cell happens to head in a favorable direction, the likelihood of tumbling reduces, making runs in this direction longer on average compared to runs in the unfavorable direction. Propulsion during a run is generated by the rotation of several helical propellers, known as flagellar filaments. Unlike eukaryotic flagella bray1992 , bacterial flagellar filaments are passive elements driven by rotary motors embedded in the cell wall. Near the beginning of a run, the motors turn in a counter-clockwise direction (when viewed from the outside of the cell), and the left-handed filaments come together to form a bundle. At the end of a run, one or more of the motors reverses, and one or more of the filaments fly out of the bundle and cause the cell to tumble. This process is complex and involves changes in filament handedness and pitch. The cell soon sets out on a new course but regains its initial speed only after the aberrant motors have reversed again and their filaments have regained their normal conformation and rejoined the bundle turner\_ryu\_berg2000 .

Although qualitative partial explanations for bundle formation have appeared in the literature anderson1975 ; macnab1977 ; lighthill1975 , a mathematical theory has not. In this note we begin to construct this theory with a quantitative treatment of one aspect of the bundling phenomenon: the role of the cell body rotation. This rotation and the accompanying hydrodynamic resistance arise to balance the torque exerted by the rotating bundle on the cell body. Thus, in the body-fixed frame, there are two kinds of flows which contribute to bundling: the flow due to frame rotation, and the swirling flows set up by each individual filament. Here we focus on the flow due to rotation of the body-fixed frame; the swirling flows and interactions among flagellar filaments will be treated in a separate publication promise . Our treatment is in the spirit of Machin machin1958 , who used a similar approach to argue that eukaryotic flagella could not be passive elements driven by motors at the cell body (see also ref. wiggins\_goldstein1998 ).

Fig. 1 illustrates the model problem. For simplicity, replace the helices with straight but flexible rods of length $`L`$, rotated with the frequency $`\omega _\text{B}`$ about the cell body axis of symmetry, $`z`$. Let $`b`$ denote the distance between the axis of the unstressed rod and the $`z`$-axis. Since the body is about a micron across, and flagellar filaments are typically six to ten microns long, we suppose $`bL`$. We also disregard the rotational disturbance flow arising from the no-slip condition at the cell body. In the body-fixed frame, this disturbance flow reduces the net rotational flow near the body. We disregard this disturbance flow since the flow field of a sphere of radius $`a`$ rotating with angular velocity $`𝝎`$ takes the form $`𝒗=𝝎\times 𝒓(a/r)^3`$, falling off rapidly with $`r`$ happel\_brenner1965 . Likewise, it is argued below that the axial drag on a filament due to the nonzero swimming velocity plays little role in our problem. Finally, we focus our attention on the contribution to flagellar filament wrapping due to body rotation, and not the flows set up by the individual rotating filaments, by ignoring the hydrodynamic interactions among the rods. Thus, it suffices to consider the shape of a single rod.

During runs, the left-handed flagellar filaments turn counter-clockwise (when viewed from outside the cell), and the body turns clockwise (when viewed from behind—i.e. from the distal end of the bundle). When our model filament is turned about the body-rotation axis $`z`$ in this same sense (clockwise when viewed from the positive $`z`$-axis, see fig. 1), it forms a right-handed shape (e.g. see fig. 2 and note that the proximal end $`x/L=b=0.1`$ is in the plane $`z=0`$, and the distal end with $`x`$ near $`0`$ has positive $`z`$ coordinate). Furthermore, two lefthanded helices rotating about their respective axes with proximal ends held stationary will lead to a flow which also tends to wrap the helices around each other in a righthanded manner promise . Thus, the body-rotation effect treated here and the swirling flow effect treated in promise  act to wrap the filaments in the same sense.

Since typical Reynolds numbers for swimming bacteria are of order $`10^6`$ berg1993 , inertia is unimportant and the steady-state rod shape is determined by a balance of viscous and elastic forces per unit length. For gentle distortions of a slender body, the viscous forces per unit length are well-approximated by the resistive-force coefficients (e.g see lighthill1975  and references therein): $`𝒇=\zeta _{}𝒖_{}+\zeta _{||}𝒖_{||},`$ where $`𝒖_{}`$ and $`𝒖_{||}`$ are the perpendicular and parallel components of the local rod velocity relative to the fluid velocity $`𝒗`$: $`𝒖=𝒓/t𝒗`$. The transverse friction coefficient (per unit length) is of the form

$$\zeta _{}\frac{4\pi \eta }{\mathrm{log}(L/a)+1/2},$$
(1)
where $`\eta `$ is the fluid viscosity, $`a`$ is the rod radius, and $`\mathrm{log}`$ denotes the natural logarithm lighthill1975 . As discussed below, $`\zeta _{||}`$ does not enter the analysis since we work in the linearized approximation. Resistive-force theory gives an accurate value for the drag force per unit length on a slender filament except near the filament ends; however, the effect of this error on the shape is $`𝒪(a/L)`$ higdon . There is also a viscous torque tending to twist the rod; however, the effects of this torque are subleading compared to the effects of the translational drag wolgemuth\_et\_al2000a . To see why, note that the total torque from rotational drag is $`𝒪(\omega \zeta _rL)`$, where $`\zeta _r=4\pi \eta a^2`$ is the friction coefficient for rotation landau\_lifshitzFM . The total torque from translational drag is $`𝒪(b(\omega b\zeta _{})\mathrm{})`$, where, as we shall see below, only the portion of the rod within a distance $`\mathrm{}`$ of the held end $`(z=0)`$ contributes to the translational drag. The ratio of these two torques is $`𝒪((a/b)^2(L/\mathrm{})[\mathrm{log}(L/a)+1/2])`$. For the representative values $`L=10`$ $`\mu `$m, $`a10`$ nm, and $`b1`$ $`\mu `$m, this ratio is small even if $`L/\mathrm{}10`$. We therefore disregard rotational drag and twist strain.

To find the bending force per unit length, note that since $`bL`$, the displacement of any rod element will also be small. Thus, the elastic energy is well-approximated by the quadratic expression

$$=\frac{1}{2}A\left[\left(\frac{^2x}{z^2}\right)^2+\left(\frac{^2y}{z^2}\right)^2\right]\text{d}z,$$
(2)
where $`x`$ and $`y`$ are as in fig. 1, and $`A`$ is the bend modulus landau\_lifshitz\_elas . Since the variation in rod shape is rapid for sufficiently high rotation rate, even for small $`b`$, this approximation eventually fails and must be replaced by the full geometrically nonlinear elastic rod energy. As we discuss below, the rotation rates of interest are small enough for (2) to hold. The variational derivative of (2) yields the elastic bending force per unit length: $`\delta /\delta 𝒓_{}=A^4𝒓_{}/z^4,`$ where $`𝒓_{}x\widehat{𝒙}+y\widehat{𝒚}`$.

To leading order for $`bL`$, the motion of the rod is purely perpendicular to the rod centerline, yielding the equation of motion machin1958

$$\zeta _{}\left(\frac{𝒓_{}}{t}𝒗_{}\right)=A\frac{^4𝒓_{}}{z^4},$$
(3)
where $`𝒗_{}`$ is the transverse fluid velocity. Since inertia is unimportant in the limit of zero Reynolds number, eqn. (3) applies equally well to the rotating frame in which the rod is fixed and the flow is $`𝒗_{}=\omega _\text{B}\widehat{𝒛}\times 𝒓_{}`$. Such a flow tends to wrap the rod around the $`z`$-axis in a shape with a helical modulation and exponential envelope. In the steady-state, eqn. (3) reduces to

$`y`$ $`=`$ $`\mathrm{}^4{\displaystyle \frac{^4x}{z^4}}`$ (4)
$`x`$ $`=`$ $`\mathrm{}^4{\displaystyle \frac{^4y}{z^4}},`$ (5)
where $`\mathrm{}(A/\zeta _{}\omega _\text{B})^{1/4}`$ is the characteristic length scale associated with bending and drag machin1958 . The solution to eqns. (4,5) is a simple generalization of Machin’s solution to the in-plane bending problem:

$$x(z)=\underset{n=1}{\overset{8}{}}A_n\mathrm{exp}(r_nz/\mathrm{}),$$
(6)
where $`r_1,\mathrm{},r_8`$ are the eight eighth roots of $`1`$. The wavelengths $`\lambda _n`$ and decay lengths $`\nu _n`$ of the eight fundamental complex solutions $`\mathrm{exp}(r_nz/\mathrm{})`$ (with $`r_n=2\pi i/\lambda _n+1/\nu _n`$) are comprised of the four possible combinations of $`\lambda _n=\pm 16.419`$ and $`\nu _n=\pm 1.0824`$, and the four possible combinations of $`\lambda _n=\pm 6.8009`$ and $`\nu _n=\pm 2.6131`$.

The boundary conditions determine the amplitudes and phases of the coefficients $`A_n`$. At the distal end $`z=L`$, there is zero force and moment: $`A^3𝒓_{}/z^3=0`$, $`A^2𝒓_{}/z^2=0`$ landau\_lifshitz\_elas . At the proximal end, flagellar filaments are connected to the rotary motor by a hook which is more flexible than the rest of the filament. We simply model this flexible connection as a hinge with zero moment at $`z=0`$: $`A^2𝒓_{}/z^2=0`$. (The other extreme, a rigid hook with $`𝒓_{}/z=0`$ leads to qualitatively similar shapes for $`\mathrm{}/L<1`$, except near $`z=0`$.) Finally, $`𝒓_{}(z=0)=b\widehat{𝒙}`$. Applying these boundary conditions to the solutions in eqn. (6) with $`b=L/10`$ yields the shapes shown in figs. 24. For large $`\mathrm{}`$, the rod is very stiff and does not bend; it is easy to show that in the limit of $`\mathrm{}/L1`$ that $`x(z)=b(13z/2)+𝒪((L/\mathrm{})^4)`$ and $`y(z)=𝒪((L/\mathrm{})^4)`$ for the hinged (zero moment) boundary condition at $`z=0`$. In the lab frame, the rod pivots about the point $`z/L=2/3`$, tracing out a cone (a rigid rod confined to the plane also pivots about this point in a viscous fluid wiggins\_goldstein1998 ). When $`\mathrm{}/L<1`$, the rod spirals around the axis of rotation, with the spiral becoming more complete as $`\mathrm{}`$ gets smaller and smaller. Note the anisotropy; the projection of the shape $`x`$-$`y`$ plane is elongated along the $`x`$-axis (fig. 2). The rod configuration is a compromise between minimizing the bending energy and minimizing the dissipation rate. For $`\mathrm{}/L1`$, elasticity dominates, and the rod is straight. For $`\mathrm{}/L1`$, viscous effects dominate and the rod bends to align along the axis of rotation and thus minimize the dissipation rate. In this limit, the linear approximation for the shape of the rod becomes invalid, and we must replace (2) with the full expression for the curvature. This nonlinear problem is readily solved by standard methods (see e.g. koehler\_powers2000 ); the result is that inaccuracies of only a few percent arise when $`\mathrm{}/L1/10`$.

To assess the importance of the role of body rotation in bundling, we estimate the characteristic length $`\mathrm{}`$. Various estimates have appeared for the flagellar filament stiffness $`A`$, from $`10^{24}`$ N m2 fushime\_maruyama\_asakura1972  to $`10^{22}`$ N m2 hoshikawa\_kamiya1985 . Fortunately, the characteristic length $`\mathrm{}`$ is not very sensitive to the value of $`A`$. To estimate the transverse drag coefficient $`\zeta _{}`$, eqn. (1), we use the viscosity of water $`\eta =0.001`$ N s/m2, a typical length $`L=10`$ $`\mu `$m, and a diameter $`2a=20`$ nm. With a typical body rotation rate of $`\omega _\text{B}=10`$ Hz macnab1977  and the range of stiffnesses quoted above, the characteristic length $`\mathrm{}`$ is found to be two to six microns. Therefore, the filaments are sufficiently flexible for the observed body rotation rate to contribute significantly to bundling. Furthermore, the linear treatment of the rod shape is justified. Presumably, body rotation is especially important for the bundles which include many right-handed filaments and a single left-handed filament, as observed in ref. turner\_ryu\_berg2000 .

Including axial drag does not alter the conclusions. Axial drag due to the swimming velocity leads to a tension gradient in the rod which slightly increases the spiral pitch. Assuming a constant tension equal to the maximum tension at the base of the rod and disregarding the shadow effect of the cell body yields an upper bound on the change in pitch. For a swimming velocity of about $`30`$ $`\mu `$m/sec, the change in pitch is small compared to the pitch.

The purpose of this work has been to point out the importance of body rotation for flagellar filament bundling. In order to focus on the essential physics of this element of the bundling phenomenon, we have disregarded several important but complementary effects, such as the helical shape of the flagellar filament and the flows induced by the individual filaments promise . Despite these simplifications, we have shown that bacterial flagellar filaments are flexible enough for body rotation to lead to wrapping.

###### Acknowledgements.

I am indebted to R.E. Goldstein and G. Huber for important conversations and ongoing collaborations. This work is supported by NSF grant no. CMS-0093658.


text:
# Charmonium mass in nuclear matter

## Abstract

The mass shift of charmonium states in nuclear matter is studied in the perturbative QCD approach. The leading-order effect due to the change of gluon condensate in nuclear matter is evaluated using the leading-order QCD formula, while the higher-twist effect due to the partial restoration of chiral symmetry is estimated using a hadronic model. We find that while the mass of $`J/\psi `$ in nuclear matter decreases only slightly, those of $`\psi (3686)`$ and $`\psi (3770)`$ states are reduced appreciably. Experimental study of the mass shift of charmonium states in nuclear matter can thus provide valuable information on the changes of the QCD vacuum in nuclear medium.

preprint: nucl-th/0208003

Understanding hadron mass changes in nuclear medium and/or at finite temperature can provide valuable information about the QCD vacuum . It is also relevant phenomenologically to the interpretation of experimental results from relativistic heavy ion collisions , in which a hot dense matter is formed during the collisions. Previous studies have been largely concerned with hadrons made of light quarks . Only recently were there studies of the in-medium masses of hadrons consisting of heavy charm quarks. Using either QCD sum rules  or the quark-meson coupling model , it has been found that the mass of $`D`$ meson, which is made of a charm quark and a light quark, is reduced significantly in nuclear medium as a result of the decrease of the light quark condensate. For the $`J/\psi `$, which consists of a charm and anticharm quark pair, both the QCD sum rules analysis  and the LO perturbative QCD calculation  show that its mass is reduced slightly in the nuclear matter mainly due to the reduction of the gluon condensate in nuclear matter.

The change of hadron masses at finite temperature is best studied using the lattice gauge theory as its prediction is less model dependent. Recent lattice gauge calculations at finite temperature with dynamical quarks have shown that even below critical temperature the interquark potential at large separation approaches an asymptotic value $`V_{\mathrm{}}(T)`$ that decreases with increasing temperature . This transition from a linearly rising interquark potential in free space to a saturated one at finite temperature is due to the decrease in the string tension and the formation of $`\overline{Q}q`$ and $`\overline{q}Q`$ pairs, where $`q`$ denotes a light quark, when the separation of the two heavy quarks ($`Q`$) becomes large. The decrease in $`V_{\mathrm{}}(T)`$ can thus be interpreted as a decrease of the open heavy quark meson ($`\overline{Q}q`$ or $`\overline{q}Q`$) mass $`m_H`$, such as the $`D`$ meson mass, at finite temperature . Furthermore, the decrease of $`m_H`$ seems to be a consequence of the reduction in the constituent mass of light quark as the temperature dependence of $`V_{\mathrm{}}(T)`$ is similar to that of the chiral condensate $`\overline{q}q`$ . This relation between the mass $`m_H`$ and the chiral order parameter also follows naturally from the heavy quark symmetry . With the finite temperature interquark potential, it has been shown via the solution of corresponding Schrödinger equation that the masses of charmonium states are reduced at finite temperature as well .

At finite density, lattice gauge calculations are at present not feasible for studying the heavy quark potential or the mass $`m_H`$ of the open heavy quark meson. Masses of these heavy quark systems are, however, expected to change appreciably in nuclear medium. Model independent estimates have shown  that condensates of the lowest dimensional operators $`\frac{\alpha _s}{\pi }G^2`$ and $`\overline{q}q`$ decrease, respectively, by 6% and 30% at normal nuclear matter, which are significant changes expected only near the critical point at finite temperature. As in the case of finite temperature, the reduction of gluon condensate leads to the softening of the confining part of interquark potential , while the decrease of quark condensates implies a drop of the open heavy quark meson mass or $`V_{\mathrm{}}`$ of the heavy quark potential. Both are expected to lead to nontrivial changes in the binding energies of the charmonium states $`\psi (3686)`$ and $`\psi (3770)`$, as their wave functions are sensitive to both the confining part and the asymptotic value of the interquark potential.

In this letter, we evaluate the mass shift of $`\psi (3686)`$ and $`\psi (3770)`$ due to changes in the gluon and quark condensates in nuclear medium. The effect of the gluon condensate is determined using the leading-order LO QCD formula, which was developed in Refs.  and has been used to study the $`J/\psi `$ mass in medium . The effect due to the change in quark condensates is difficult to calculate using the quark and gluon degrees of freedom as they appear as higher twist effects in the operator product expansion . However, its dominant effect to a heavy quark system is to reduce $`V_{\mathrm{}}`$ as a result of the decrease of $`D`$ meson in-medium mass, about 50 MeV in normal nuclear matter due to the 30% reduction in the quark condensate . Therefore, we can study the effect of changing quark condensate on the charmonium states at finite density by using a hadronic model to calculate their mass shifts due to the change of $`D`$ meson in-medium mass. Combining the effects from changes in the gluon condensate and in $`m_D`$, we find that both $`\psi (3686)`$ and $`\psi (3770)`$ masses are reduced appreciably at normal nuclear matter density.

The mass shift of charmonium states in nuclear medium can be evaluated in the perturbative QCD when the charm quark mass is large, i.e., $`m_c\mathrm{}`$. In this limit, one can perform a systematic operator product expansion (OPE) of the charm quark-antiquark current-current correlation function between the heavy bound states by taking the separation scale ($`\mu `$) to be the binding energy of the charmonium . The forward scattering matrix element of the charm quark bound state with a nucleon then has the following form:

$`T(q^2=m_\psi ^2)={\displaystyle \underset{n}{}}{\displaystyle \frac{C_n}{(\mu )^n}}𝒪_n_N.`$ (1)
Here, $`C_n`$ is the Wilson coefficient evaluated with the charm quark bound state wave function and $`𝒪_n_N`$ is the nucleon expectation value of local operators of dimension $`n`$.

For heavy quark systems, there are only two independent lowest dimension operators; the gluon condensate ($`\frac{\alpha _s}{\pi }G^2`$) and the condensate of twist-2 gluon operator multiplied by $`\alpha _s`$ ($`\frac{\alpha _s}{\pi }G_{\alpha \mu }G_\nu ^\alpha `$). These operators can be rewritten in terms of the color electric and magnetic fields: $`\frac{\alpha _s}{\pi }E^2`$ and $`\frac{\alpha _s}{\pi }B^2`$. Since the Wilson coefficient for $`\frac{\alpha _s}{\pi }B^2`$ vanishes in the non-relativistic limit, the only contribution is thus proportional to $`\frac{\alpha _s}{\pi }E^2`$, similar to the usual second-order Stark effect. We shall thus calculate the mass shift of charmonium states due to change of the gluon condensate in nuclear medium by the QCD second-order Stark effect .

The mass shift of charmonium states to leading order in density is obtained by multiplying the leading term in Eq.(1), by the nuclear density $`\rho _N`$. This gives,

$`\mathrm{\Delta }m_\psi (ϵ)`$ $`=`$ $`{\displaystyle \frac{1}{9}}{\displaystyle 𝑑k^2\left|\frac{\psi (k)}{𝐤}\right|^2\frac{k}{k^2/m_c+ϵ}}`$ (3)
$`\times {\displaystyle \frac{\alpha _s}{\pi }}E^2_N{\displaystyle \frac{\rho _N}{2m_N}}.`$
In the above, $`m_N`$ and $`\rho _N`$ are the nucleon mass and the nuclear density, respectively; $`\frac{\alpha _s}{\pi }E^2_N0.5`$ GeV2 is the nucleon expectation value of the color electric field and $`ϵ=2m_cm_\psi `$. In Ref., the LO mass shift formula was derived in the large charm quark mass limit. As a result, the wave function $`\psi (k)`$ is Coulombic and the mass shift is expressed in terms of the Bohr radius $`a_0`$ and the binding energy $`ϵ_0=2m_cm_{J/\psi }`$. This might be a good approximation for $`J/\psi `$ but is not realistic for the excited charmonium states as Eq.(3) involves the derivative of the wave function, which measures the dipole size of the system. We have thus rewritten in the above the LO formula for charmonium mass shift in terms of the QCD parameters $`\alpha _s=0.84`$ and $`m_c=1.95`$, which are fixed by the energy splitting between $`J/\psi `$ and $`\psi (3686)`$ in free space. Furthermore, we take wave functions of the charmonium state to be Gaussian with the oscillator constant $`\beta `$ determined by their squared radii $`r^2=`$ $`0.47^2`$, $`0.96^2`$, and 1 fm2 for $`J/\psi `$, $`\psi (3686)`$, and $`\psi (3770)`$, respectively, as obtained from the potential models . This gives $`\beta =`$ 0.52, 0.39, and 0.37 GeV if we assume that these charmonium states are in the $`1S`$, $`2S`$, and $`1D`$ states, respectively. Using these parameters, we find that the mass shifts at normal nuclear matter density obtained from the LO QCD formula Eq.(3) are -8, -100, and -140 MeV for $`J/\psi `$, $`\psi (3686)`$, and $`\psi (3770)`$, respectively.

Although the higher twist effects on the charmonium masses are expected to be nontrivial, the result for $`J/\psi `$ is consistent with those from other non-perturbative QCD studies, such as the QCD sum rules  and the effective potential model , which are all based on the dipole interactions between quarks in the charmonium and those in the nuclear matter. To go beyond the leading order in the OPE, we need to calculate the contributions from higher dimensional operators in Eq.(1), which include light quark operators. Explicit calculations from QCD sum rules for $`J/\psi `$ up to dimension 6 operators  show that the effect due to change in the condensates of light quark operators at dimension 6, which include $`\overline{q}\mathrm{\Gamma }q\overline{q}\mathrm{\Gamma }q`$ and $`\overline{q}DGq`$ , is unimportant for the mass shift of $`J/\psi `$. However, such calculation cannot be easily generalized to the excited charmonium states $`\psi (3686)`$ and $`\psi (3770)`$, where the sum rules do not exist even in the vacuum. On the other hand, the higher twist effects due to the light quark operators can be estimated by considering the coupling of the charmonium to the $`\overline{D}D`$ states as in the potential model for charmonium states . Therefore, instead of summing up the non-convergent contributions from the change in the light quark condensates in the OPE of Eq.(1), we estimate its contribution by evaluating the charmed meson one-loop effect on the mass of a charmonium with in-medium $`D`$ meson mass predicted from the QCD sum rules  or the quark-meson coupling model .

Following the studies in Ref.  on $`\rho \pi `$ interactions and in Ref.  on $`\varphi K`$ interactions, we use the following Lagrangian for interacting charmonium $`\psi `$ and $`D`$ meson:

$``$ $`=`$ $`{\displaystyle \frac{1}{2}}\left(|D_\mu 𝐃|^2m_D^2|𝐃|^2\right){\displaystyle \frac{1}{4}}F_{\mu \nu }F^{\mu \nu }+{\displaystyle \frac{1}{2}}m_\psi ^2\psi _\mu \psi ^\mu ,`$ (4)
where $`F_{\mu \nu }=_\mu \psi _\nu _\nu \psi _\mu `$ is the charmonium field strength, $`D_\mu =_\mu i2g_{\psi DD}\psi _\mu `$, and $`𝐃=(D^0,D^+)`$.

The coupling constant $`g_{\psi DD}`$ can be determined using the $`3P0`$ model . In this model, the coupling constant is proportional to the overlap integral between the relative quark wave functions of charmonium and the two outgoing charmed mesons as well as to a coupling parameter $`\gamma `$, which characterizes the probability of producing a light quark-antiquark pair in the $`{}_{}{}^{3}P_{0}^{}`$ state. The result can be read off from Refs.  and is given by

$`g_{\psi DD}^2(q)`$ $`=`$ $`\gamma ^2\pi ^{3/2}{\displaystyle \frac{m_\psi ^3}{\beta _D^3}}f_\psi (q^2,r)e^{\frac{q^2}{2\beta _D^2(1+2r^2)}},`$ (5)
where $`q`$ is the three-momentum of $`D`$ mesons in the $`\psi `$ rest frame and $`r=\beta /\beta _D`$ with $`\beta _D`$ ($`\beta `$) being the oscillator constant for $`D`$ meson ($`\psi `$) wave function. For the $`\beta `$’s, the same values will be used as in the LO QCD calculation. The values for $`\gamma `$ and $`\beta _D`$ are taken to be 0.35 and 0.31 GeV, respectively, to reproduce both the decay width of $`\psi (3770)`$ to $`D\overline{D}`$ and the partial decay width of $`\psi (4040)`$ to $`DD`$, $`DD^{}`$, and $`D^{}D^{}`$ . The function $`f_\psi (q^2,r)`$ denotes $`\frac{2^6r^3(1+r^2)^2}{(1+2r^2)^5}`$ for $`J/\psi `$, $`\frac{2^5(3+2r^2)^2(13r^2)^2}{3(1+2r^2)^7}(1\frac{2r^2(1+r^2)}{(1+2r^2)(3+2r^2)(3r^21)}\frac{q^2}{\beta _D^2})^2`$ for $`\psi (3686)`$, and $`\frac{2^95r^7}{3(1+2r^2)^7}(1\frac{(1+r^2)}{5(1+2r^2)}\frac{q^2}{\beta _D^2})^2`$ for $`\psi (3770)`$.

Because of its momentum dependence, $`g_{\psi DD}(q)`$ takes into account the form factor at the $`\psi DD`$ vertex and allows also the coupling of the charmonium to off-shell $`D`$ mesons. For $`\psi (3770)`$, it can decay to $`D\overline{D}`$ in free space, and its on-shell coupling constant is $`g_{\psi (3770)DD}(q=(m_\psi ^2/4m_D^2)^{1/2})=15.4`$. The coupling constants at $`q=0`$ are 15.3, 18.7, and 16.8 for $`J/\psi `$, $`\psi (3686)`$, and $`\psi (3770)`$, respectively. The value for $`J/\psi `$ coupling to $`D`$ mesons is slightly larger than that estimated by the vector meson dominance model  and by the QCD sum rules. As the $`D`$ meson momentum increases, its coupling constant to $`J/\psi `$ has a simple exponential fall off due to the $`1S`$ quark wave function of the $`J/\psi `$. In contrast, the coupling constants of excited charmonium states $`\psi (3686)`$ and $`\psi (3770)`$ to $`D`$ mesons fall off exponentially with the $`D`$ meson momentum but vanish at certain $`q^2`$ as a result of the nodes in the $`2S`$ or $`1D`$ wave functions of the excited charmonium states .

Similar to the method introduced in Ref., we have used the above Lagrangian to evaluate the self-energy of a charmonium due to the $`D`$ meson loop. After performing the energy integral in the rest frame of the $`\psi `$, i.e., $`k=(m_\psi ,0)`$, the invariant part of the polarization $`\mathrm{\Pi }(k)`$ then has the following form:

$`\mathrm{\Pi }(k)`$ $`=`$ $`{\displaystyle \frac{1}{6\pi ^2}}𝒫{\displaystyle }dq^2g_{\psi DD}^2(q^2)[{\displaystyle \frac{q}{\sqrt{m_D^2+q^2}}}`$ (6)
$`\times `$ $`({\displaystyle \frac{4q^2}{m_\psi ^24m_D^24q^2}}+3)(m_D^{}=m_D)],`$ (7)
where $`m_D^{}`$ is the in-medium $`D`$ meson mass and $`𝒫`$ denotes that only the principle value of the integral is evaluated. The subtracted term in the above equation is a renormalization constant which is determined by requiring $`\mathrm{\Pi }(k^2=m_\psi ^2)=0`$ when $`m_D^{}=m_D`$. This ensures that the $`D`$ meson loop does not contribute to the real part of the charmonium self energy in free space. The mass shift of the charmonium at finite density is then given by $`\mathrm{\Delta }m_\psi =\mathrm{\Pi }(k^2=m_\psi ^2)`$.

In Fig. 1, we show the mass shifts of charmonium states as functions of $`m_D^{}`$. It is seen that the mass shift of $`\psi (3770)`$ is negative for small negative shift of $`D`$ meson mass but becomes positive when the $`D`$ meson mass drop is large. In contrast, the mass shift of $`\psi (3686)`$ is negative for all negative mass shifts of the $`D`$ meson. This difference can be understood from Eq.(7), where the integral is a convolution of the form factor $`g_{\psi DD}^2(q^2)`$ with the terms in the square bracket, which are singular when $`q^2=m_\psi ^2/4m_D^2`$ and $`q^2=m_\psi ^2/4m_D^2`$. The integrand thus changes signs whenever the $`D`$ meson momentum $`q`$ passes through these singularities and finally becomes negative when $`q^2`$ is larger than any of the singularities, which correspond to the energies of the virtual intermediate $`D`$ meson states. As in second-order perturbation theory, the contribution is attractive when the energy of the intermediate state is larger than the charmonium mass. However, the form factor decreases exponentially with $`q^2`$ and can even be zero, the large negative contribution expected for a constant form factor is suppressed, leading thus to an increase of the $`\psi (3770)`$ mass when $`m_Dm_D^{}10`$ MeV. On the other hand, the singularity of the integrand in Eq.(7) in the case of $`\psi (3683)`$ occurs only when $`2m_D^{}`$ falls below its mass and therefore has only a small positive contribution when $`q^2`$ is very small, leading to a reduction of its mass for any $`D`$ meson mass shift. For $`J/\psi `$, we find that its mass only increases slightly with dropping $`D`$ meson mass and depends weakly on $`m_D^{}`$. For $`m_Dm_D^{}=50`$ MeV, which is the expected mass shift of $`D`$ meson at normal nuclear matter density, the mass shift of $`J/\psi `$ is about 3 MeV. This result is consistent with that from the QCD sum rules  and is also expected from the potential model , where the $`J/\psi `$ wave function has only a small $`D\overline{D}`$ component. We note that the density dependence of the mass shifts of charmonium states, particularly the excited ones, is nonlinear if we use a linearly density-dependent $`D`$ in-medium meson $`m_D^{}=m_D50\rho /\rho _0`$ MeV in the denominator of Eq.(7). On the other hand, the mass shift obtained from the LO QCD formula in Eq.(3) depends linearly on the nuclear density.

Adding the mass shift from the $`D`$ meson loop effect to the result from the LO QCD calculation, we find that masses of charmonium states are changed by the following amount at normal nuclear matter density:

$`\mathrm{\Delta }m_{J/\psi }`$ $`=`$ $`8+3\mathrm{MeV},`$ (8)
$`\mathrm{\Delta }m_{\psi (3686)}`$ $`=`$ $`10030\mathrm{MeV},`$ (9)
$`\mathrm{\Delta }m_{\psi (3770)}`$ $`=`$ $`140+15\mathrm{MeV},`$ (10)
where the first number represents the shift from the LO QCD while the second number is from the $`D`$ meson loop. The above results thus show that masses of excited charmonium states are reduced significantly in nuclear matter, largely due to the non-trivial decrease of the in-medium gluon condensate in the LO QCD formula for their masses.

The mass shifts of both $`\psi (3686)`$ and $`\psi (3770)`$ in nuclear medium are large enough to be observed in experiments involving $`\overline{p}A`$ annihilation as proposed in the future accelerator facility at the German Heavy Ion Accelerator Center (GSI) . In these experiments, $`\psi (3770)`$ and $`\psi (3686)`$ produced inside a heavy nucleus will be studied via the dilepton spectrum emitted from their decays. While the lifetime of $`J/\psi `$ has been shown to remain constant in nuclear matter, those of $`\psi (3686)`$ and $`\psi (3770)`$ are reduced to less than 5 fm/$`c`$ due to increases in their width in nuclear matter . Therefore, an appereciable fraction of produced excited charmonium states in these experiments are expected to decay inside the nucleus , leading to an observable shift of the peak positions in the dilepton spectrum. The observation of such shifts in the masses of excited charmonium states in these experiments would give us valuable information on the nontrivial changes of the QCD vacuum in nuclear medium and on the origin of masses in QCD.

This paper is based on work supported by the National Science Foundation under Grant No. PHY-0098805 and the Welch Foundation under Grant No. A-1358. S.H.L is also supported by the Brain Korea 21 project of Korean Ministry of Education and by KOSEF under Grant No. 1999-2-111-005-5.


text:
# Witnessing the Hierarchical Assembly of the Brightest Cluster Galaxy in a Cluster at z=1.26

## 1 Introduction

The cores of rich clusters are often dominated by massive elliptical galaxies: many of these brightest cluster galaxies (BCG’s) are conspicuously different from other cluster members, in being at least one magnitude brighter than other giant ellipticals (Sandage 1976, Hoessel et al. 1980) and being located at or close to the bottom of the cluster potential well (Oegerle & Hill 2001). It is likely that BCG’s arise from merging of massive satellites, drawn towards the cluster center by dynamical friction, as also hinted by the high frequency of multiple nucleation in these objects (e.g., Furuzawa et al. 1999 and references therein), or by collimated infall along filaments in the early epochs of cluster formation (West 1994; Dubinski 1998).

The $`K`$-band Hubble diagram provides a measure of BCG evolution but previous results have been contradictory: Aragon-Salamanca, Baugh, & Kauffmann (1998) argued that BCG’s dim with redshift according to, or fainter than, no-evolution models, suggesting that their mass has therefore increased in recent times by galaxy merging or cannibalism. On the other hand, Collins & Mann (1998) found evidence that BGC’s evolve passively in an X-ray selected sample of clusters. Burke, Collins, & Mann (2000) suggested that the discrepancy is due to sample selection, as Aragon-Salamanca et al’s (1998) sample consists of optically selected clusters some of which are not yet virialized enough to show strong X-ray emission. Recently, Nelson, Gonzalez, Zaritsky, & Dalcanton (2001, 2002); Nelson et al. (2002) have confirmed that (i) BCG’s in different environments evolve differently (Burke, Collins, & Mann, 2000) and (ii) there has been significant growth in BCG mass in low X-ray luminosity clusters since at least $`z1`$. However, Brough et al. (2002) recently found that there is no notable difference in the luminosity of brightest cluster galaxies between clusters with high and low X-ray luminosity at $`z<0.1`$, suggesting that BCG evolution is nearly complete at the present epoch in cluster environments.

Observations at high redshift allow us to study systems in an earlier stage of dynamical evolution and at a younger age. Among the small sample of $`z>1`$ clusters discovered so far, RX J0848.9+4452 (Rosati et al., 1999) is one of the most secure examples of a rich, high concentration system resembling rich Abell clusters today. Stanford et al. (2001) measured the temperature of the X-ray hot gas as T=5.8 keV and showed the gas has a regular, centrally concentrated spatial distribution. The central galaxy of the cluster is indeed the highest-redshift one in the sample studied in Burke, Collins, & Mann (2000), and therefore provides the strongest leverage on the evolution of BCG’s.

We have exploited the good image quality achievable on the Subaru telescope to obtain very deep near-infrared images of this cluster at high spatial resolution. We find that the BCG is clearly resolved into two components in our $`K^{}`$ image and interpret this result in the light of the $`K`$-band Hubble diagram of BCG’s.

In this paper, we focus on the properties of the BCG in the cluster core while our study of the luminosity function and color-magnitude diagram will be presented in a separate paper (Yamada et al. in preparation). We adopt cosmological parameters $`q_0=0.5`$, $`H_0`$ = 50 km s-1 Mpc-1, $`\lambda _0=0`$ throughout the paper for consistency with previous work unless noted.

## 2 Observations

A deep high-resolution $`K^{}`$-band image of the cluster RX J0848.9+4452 was obtained with the Subaru telescope equipped with The Infrared Camera and Spectrograph  (IRCS) (Kobayashi et al., 2000) during the night of 5 January, 2001 (UT). The pixel scale was $`0.058^{\prime \prime }`$ per pixel, for a field of view of $`1^{}\times 1^{}`$. We accumulated 120-sec exposures with a 5-point dithering pattern for a total net integration time of 4 hours. The seeing was moderate and the FWHM of the stellar objects in the final combined image $`0.^{\prime \prime }45`$. Data were reduced in the standard manner; after dark subtraction and flat-fielding using the dome-flat frame, we subtracted a median sky frame from each image, derived from the five preceding and following frames. Magnitude calibration to the Mauna Kea system $`K`$ band was carried out by observing the UKIRT Faint Standard Stars (Hawarden et al. 2001) observed before and after the cluster observation. We ignored the $`K^{}K`$ color correction.

In addition to the IRCS data, we also used a part of the Subaru Suprime-Cam image of the field (Nakata, 2002) and archival WFPC2 data from Hubble Space Telescope (PID:8269, PI:Elston) in order to study the galaxy properties at the optical wavelengths.

## 3 The Brightest Cluster Galaxy in RX J0848.9+4452

Figure 1 shows the $`K^{}`$-band image of the central region of the cluster. The side of the box is $`7^{\prime \prime }`$, which corresponds to 58 kpc at $`z=1.26`$. In this image, the brightest galaxy previously catalogued as galaxy $`\mathrm{\#}1`$ in Rosati et al. (1999) is clearly resolved into two components. The projected separation between the peaks of the two components is 0.′′7 or 5.8 kpc assuming both galaxies lie at the cluster redshift.

Since the field is crowded, it is not straightforward to derive photometric properties for each galaxy. We modeled the galaxies in Figure 1 using a de Vaucoleurs’ profile with centroids as determined from the SExtractor algorithm (Bertin & Arnouts, 1996): the parameters using in our modeling were: effective radius, effective surface brightness (or equivalently, total magnitude), axial ratio, and position angle for the five galaxies. Figure 2 shows artificial galaxy images built using the IRAF ARTDATA package using the best fitting model parameters (left-hand panel) and residuals after subtraction of the actual image (right-hand panel). We summarize the results of the fitting in Table 1. Galaxy B is the first ranked cluster galaxy whereas galaxy A is still about 0.5 magnitudes brighter than the next brightest spectroscopic member (# 11) in Rosati et al. (1999)

Figure 2 shows both positive and negative residuals at about $`2\%`$ and $`5\%`$ of the total flux of galaxy B. Although our assumption that galaxies in Figure 1 are represented by de Vaucouleurs profiles is certainly an oversimplification, the errors introduced in the modeling are therefore too small to affect our discussion of the $`K`$-band Hubble diagram. In order to test this we smoothed our image to the $`0.9^{\prime \prime }`$ seeing and the resolution reported in Rosati et al. (1999) and derived a luminosity within 50 kpc metric aperture for the combined galaxy of $`K=16.84`$ which compares well with the published value of $`K=16.72`$ (Rosati et al. 1999).

Figure 3 shows the $`K`$-band Hubble diagram of the brightest cluster galaxies. The central galaxies A and B in RX J0848.9+4452 are plotted as filled squares together with low and intermediate redshift data from Collins & Mann (1998) (as open circles) and tracks for passive and no-evolution models (cf. Figure 2 in Burke et al. 2000). Magnitudes ($`K=17.9`$ and 17.4 for galaxy A and B, respectively) are measured within 50 kpc metric apertures for consistency with previous data. Neither A nor B is as bright as the local brightest cluster galaxies evolved passively to $`z=1.26`$. This result holds for another cosmological model with $`\mathrm{\Omega }_m=0.3`$, $`\mathrm{\Omega }_\lambda =0.7`$, and $`H_0=70`$ km s-1Mpc-1 where the predicted $`K`$-band magnitude at $`z=1.26`$ of the models with same present-day luminosity is about 0.8 mag fainter than in Figure 3. Although RX J0848.9+4452 is an X-ray cluster and a massive system in an evolved dynamical stage with high X-ray temperature, its ‘BCG’ appears to be at an early evolutionary phase relative to its counterparts in the local universe.

## 4 Discussion

We have found that the brightest galaxy in the rich X-ray cluster RX J0848.9+4452 at $`z=1.26`$ consists of two components and is therefore fainter than its local counterparts. We consider here the colors of the two components in order to constrain their stellar populations. We used a 4800s WFPC2 $`F814W`$ exposure of this field taken by HST. Figure 4 shows a $`4^{\prime \prime }\times 4^{\prime \prime }`$ region of this image including our galaxies. The two components are clearly identified. We smoothed the $`F814W`$ image to same resolution as our IRCS data and measured $`IK`$ colors of the two components through $`0.6^{\prime \prime }`$-diameter apertures centered on the $`K^{}`$-band centroids. Both components have very red colors, $`I_{F814W}K`$ = 3.27$`\pm `$0.07 and 3.62$`\pm `$0.08 (in $`AB`$ magnitude), respectively, but galaxy A is 0.3 mag bluer than B.

Figure 5 shows the two-color diagram of $`K^{}`$-selected galaxies in our IRCS field. Optical colors are from the Suprime-Cam study of this cluster by Nakata (2002). Our IRCS image was degraded to match the resolution and seeing ($`1^{\prime \prime }`$) of the Suprime-Cam image. Colors were measured within 2′′-diameter apertures. Galaxies A and B are not separated in the image, and we treated them as a single galaxy. We measured $`RI`$ and $`IK`$ colors (in Cousins and UKIRT-MK system) of our galaxies. We also plotted passive evolution models for old cluster galaxies from Kodama & Arimoto (1997). The composite brightest cluster galaxy (A+B) is very close to predictions of passive-evolution models for a $`M_V=23`$ (at $`z=0`$) galaxy observed at z=1.26 whose predicted $`K`$-band magnitude is 16.4. It is also one of the reddest galaxies in the field. Thus galaxies A and B of the rich z=1.26 cluster have stellar populations quite consistent with prediction of the passive-evolution model for the most luminous old elliptical galaxies, but are less massive than today’s BCG’s, having sizes comparable to those of normal ellipticals.

If we assume that the two galaxies lie at the same redshift, their separation is as small as 6 kpc. Numerical simulations (Hausman & Ostriker, 1978; Rood & Leir, 1979) show that these objects should merge on timescales of less than a few $`10^8`$ years. We therefore argue that we are witnessing the major merger of two massive ($`L^{}`$) elliptical galaxies to fuel the hierarchical growth of the BCG in RX J0848.9+4453 although the exact redshifts of the two systems and their relative velocity are necessary to draw definite conclusions on this issue. This result is consistent with models of hierarchical merging growth of BCGs. Aragon-Salamanca, Baugh, & Kauffmann (1998) argued that the typical mass of BCGs at $`z=1`$ is expected to be about half of the present. Dubinski (1998) also showed in his numerical simulation that the central galaxy forms through the merger of several massive galaxies in early history of cluster formation.

Yamada et al. (2000) have measured $`K`$ luminosities of BCG’s in three other $`z>1`$ clusters: 3C324, B2 1335+28 and ClG J0848+4453 and found these galaxies are all fainter than the predictions of Burke, Collins, & Mann (2000) based on passive evolution models. These three clusters, however, are less X-ray luminous than RX J0848.9+4453 (Dickinson, 1997; Stanford et al., 2001) and/or are more irregular and less concentrated in their galaxy distributions (Kajisawa et al., 2000; Tanaka et al., 2000; Nakata et al., 2001; Stanford et al., 2001): the present result shows that BCG’s are consistently less massive than present-day systems even in well-virialized systems.

It is not uncommon for present-day BCG’s to contain multiple nuclei: about half of the BCG’s in Abell clusters have multiple nuclei within 19.2 kpc (Hoessel & Schneider, 1985; Tonry, 1985); however, objects with small separation are somewhat rare: only 7% of the galaxies have multiple nuclei within 5 kpc of each other; the magnitude difference between the nuclei is larger than 1 magnitude in 60% of the low-redshift sample of Hoessel & Schneider (1985). Therefore, the nascent BCG in RX J0848.9+4453 is a relatively rare object and may be an example of an equal mass merger as is predicted to occur at the top of the merging hierarchy.

The two component galaxies are aligned to point roughly in the direction of the nearby $`z=1.27`$ cluster ClG J0848+4453 (Stanford et al., 1997) and are aligned with the outer X-ray contour of RX J0848.9+4452 (Stanford et al., 2001) This may be the high redshift equivalent of the alignment effect of BCGs in nearby clusters (Binggeli, 1982; Fuller, West, & Bridges, 1999). Galaxies in the $`z=1.2`$ cluster around the radio galaxy 3C324 may be similarly aligned Nakata et al. (2001). West (1994) proposed that this arises as clusters form by collimated infall along filaments. Dubinski (1998) also showed in his N-body simulation that the shape and orientation of the BCGs become nearly congruent with the galaxy distribution in the host cluster. The observed evidence of the alignment effect at high redshift, if confirmed, implies that such collimated structure formation indeed took place at $`z>1`$.

This work is based on data collected at Subaru Telescope, which is operated by the National Astronomical Observatory of Japan. This work is also based in part on observations with the NASA/ESA Hubble Space Telescope, obtained from the data archive at the Space Telescope Science Institute, U.S.A., which is operated by AURA, Inc. under NASA contract NAS5–26555. The Image Reduction and Analysis Facility (IRAF) used in this paper is distributed by National Optical Astronomy Observatories. U.S.A., operated by the Association of Universities for Research in Astronomy, Inc., under contact to the U.S.A. National Science Foundation.TK acknowledges JSPS postdoctoral research fellowship and the Daiwa-Adrian Prize 2001 for financial support.


text:
# Exponential Lower Bound for 2-Query Locally Decodable Codes via a Quantum Argument

## 1 Introduction

Error-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 $`m=O(n)`$ already suffice to recover from errors in a constant fraction of the bitpositions of the codeword (even in linear time ). One disadvantage of such “standard” error-correction, is that one usually needs to consider all or most of the (corrupted) codeword to recover anything about $`x`$. If one is only interested in recovering one or a few of the bits of $`x`$, then more efficient schemes are possible, so-called locally decodable codes (LDCs). LDCs allow us to extract small parts of encoded information from a corrupted codeword, while looking at (“querying”) only a few positions of that word. They have found various applications in complexity theory and cryptography, such as self-correcting computations, PCPs, worst-case to average-case reductions, and private information retrieval. Informally, LDCs are described as follows:

> A $`(q,\delta ,\epsilon )`$-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 $`1/2+\epsilon `$ making only $`q`$ queries, even if the codeword is corrupted in $`\delta m`$ of the bits.

For example, the Hadamard code is a locally decodable code where two queries are sufficient in order to predict any bit with constant advantage, even with a constant fraction of errors. The code has $`m=2^n`$ and $`C(x)_j=jx\text{ mod }2`$ for all $`j\{0,1\}^n`$. Recovery from a corrupted codeword $`y`$ is possible by picking a random $`j\{0,1\}^n`$, querying $`y_j`$ and $`y_{je_i}`$, and outputting the XOR of those two bits. If neither bit has been corrupted, then we output $`y_jy_{je_i}=jx(je_i)x=e_ix=x_i`$, as we should. If $`C(x)`$ has been corrupted in at most $`\delta m`$ positions, then a fraction of at least $`12\delta `$ of all $`(j,je_i)`$ pairs of indices is uncorrupted, so the recovery probability is at least $`12\delta `$. This is $`>1/2`$ as long as $`\delta <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`$, $`\delta `$, and $`\epsilon `$. For $`q=polylog(n)`$, Babai et al.  showed how to achieve length $`m=O(n^2)`$, for some fixed $`\delta ,\epsilon `$. This was subsequently improved to nearly linear length by Polishchuk and Spielman . Beimel et al.  recently improved the best known upper bounds for constant $`q`$ to $`m=2^{n^{O(\mathrm{log}\mathrm{log}q/q\mathrm{log}q)}}`$, with some more precise bounds for small $`q`$.

The study of lower bounds on $`m`$ was initiated by Katz and Trevisan . They proved that for $`q=1`$, LDCs do not exist if $`n`$ is larger than some constant depending on $`\delta `$ and $`\epsilon `$. For $`q2`$, they proved a bound of $`m=\mathrm{\Omega }(n^{q/(q1)})`$ if the $`q`$ queries are made non-adaptively; this bound was generalized to the adaptive case by Deshpande et al. . 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 whether $`m=poly(n)`$ is achievable with constant $`q`$. Recently, Goldreich et al.  examined the case $`q=2`$, and showed that $`m2^{\delta \epsilon n/8}`$ if $`C`$ is a linear code. Obata  subsequently strengthened the dependence on $`\epsilon `$ to $`m2^{\mathrm{\Omega }(\delta n/(12\epsilon ))}`$, which is essentially optimal.

Katz and Trevisan, and Goldreich et al. established a close connection between locally decodable codes and private information retrieval (PIR) schemes. In fact, the best known LDCs for constant $`q`$ are derived from PIR schemes. A PIR scheme allows a user to extract a bit $`x_i`$ from an $`n`$-bit database $`x`$ that is replicated over some $`k1`$ 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. If there is only one server ($`k=1`$), then 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 $`k2`$ servers, then smarter protocols are possible. Chor et al.  exhibited a 2-server PIR scheme with communication complexity $`O(n^{1/3})`$ and one with $`O(n^{1/k})`$ for $`k>2`$. Ambainis  improved the latter to $`O(n^{1/(2k1)})`$. Beimel et al.  improved the communication complexity to $`O(n^{2\mathrm{log}\mathrm{log}k/k\mathrm{log}k})`$; their results improve the previous best bounds for all $`k3`$ but not for $`k=2`$. No general lower bounds better than $`\mathrm{\Omega }(\mathrm{log}n)`$ are known for PIRs with $`k2`$ servers. A PIR scheme is linear if for every query the user makes, the answer bits are linear combinations of the bits of $`x`$. Goldreich et al.  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 $`t=\mathrm{\Omega }(n/a^k)`$.

### 1.1 Our results: Locally decodable codes

The main result of this paper is an exponential lower bound for general 2-query LDCs:

> A $`(2,\delta ,\epsilon )`$-locally decodable code requires length $`m2^{cn1}`$,

for $`c=1H(1/2+3\delta \epsilon /14)`$, where $`H()`$ is the binary entropy function. This is the first superpolynomial lower bound on general LDCs with more than one query. Our constant $`c`$ in the exponent is somewhat worse than the ones of Goldreich et al. and of Obata, but our proof establishes the exponential lower bound for all LDCs, not just linear ones. In the body of the paper we will focus only on codes over the binary alphabet. In Appendix B we show how to extend our result to the case of larger alphabets, using a classical reduction due to Trevisan.

Our proof introduces one radically new ingredient: quantum computing. We show that if two classical queries can recover $`x_i`$ with probability $`1/2+\epsilon `$, then $`x_i`$ can also be recovered with probability $`1/2+4\epsilon /7`$ using only one quantum query.111One can’t reduce 3 classical queries to 1 quantum query, because the XOR of 3 bits requires 2 quantum queries. In other words, a $`(2,\delta ,\epsilon )`$-locally decodable code is a $`(1,\delta ,4\epsilon /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 $`\mathrm{log}m`$. Nayak’s  linear lower bound on such codes finishes off the proof. For the sake of completeness, we include a proof of his result in Appendix A.

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.222The quantum lower bound on the communication complexity of the inner product function of Cleve et al.  provides new insight in a classical result, but does not establish a new result for classical computer science. Radhakrishnan et al.  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. . Sen and Venkatesh did the same for data structures for the predecessor problem \[18, quant-ph version\]. Finally, Klauck et al.  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 these cases, however, the underlying proof techniques easily yield a classical proof. 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 LDCs don’t).

We also 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 decoding algorithm 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 $`\delta `$ and $`\epsilon `$ . For larger $`q`$, it turns out that the best known $`(2q,\delta ,\epsilon )`$-LDCs, due to Beimel et al. , are actually $`(q,\delta ,\epsilon )`$-LQDCs. Hence for fixed number of queries $`q`$, we obtain LQDCs that are significantly shorter than the best known LDCs. In particular, Beimel et al. give a 4-query LDC with length $`m=2^{O(n^{3/10})}`$ which is a 2-query LQDC. This is significantly shorter than the $`m=2^{\mathrm{\Theta }(n)}`$ that 2-query LDCs need. We summarize the situation in the following table, where our contributions are indicated by boldface.

### 1.2 Our 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 . Thus we obtain an $`\mathrm{\Omega }(n)`$ lower bound on the communication complexity for all classical 2-server PIRs with 1-bit answers. Previously, such a bound was known only for linear PIRs (first proven in \[6, Section 5.2\] and extended to linear PIRs with constant-length answers in ). In Appendix B we extend our lower bound to PIR schemes with 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. \[4, 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 below.

## 2 Preliminaries

### 2.1 Quantum

Below we give more precise definitions of locally decodable codes and related notions, but we first briefly explain the standard notation of quantum computing. We refer to Nielsen and Chuang  for more details. A qubit is a linear combination of the basis states $`|0`$ and $`|1`$, also viewed as a 2-dimensional complex vector:

$$\alpha _0|0+\alpha _1|1=\left(\begin{array}{c}\alpha _0\\ \alpha _1\end{array}\right),$$

where $`\alpha _0,\alpha _1`$ are complex amplitudes, and $`|\alpha _0|^2+|\alpha _1|^2=1`$.

The $`2^m`$ basis states of an $`m`$-qubit system are the $`m`$-fold tensor products of the states $`|0`$ and $`|1`$. For example, the basis states of a 2-qubit system are the four 4-dimensional unit vectors $`|0|0`$, $`|0|1`$, $`|1|0`$, and $`|1|1`$. We abbreviate, e.g., $`|1|0`$ to $`|0|1`$, or $`|1,0`$, or $`|10`$, or even $`|2`$ (since 2 is 10 in binary). With these basis states, an $`m`$-qubit state $`|\varphi `$ is a $`2^m`$-dimensional complex unit vector

$$|\varphi =\underset{i\{0,1\}^m}{}\alpha _i|i.$$

We use $`\varphi |=|\varphi ^{}`$ to denote the conjugate transpose of the vector $`|\varphi `$, and $`\varphi |\psi =\varphi ||\psi `$ for the inner product between states $`|\varphi `$ and $`|\psi `$. These two states are orthogonal if $`\varphi |\psi =0`$. The density matrix corresponding to $`|\varphi `$ is the outer product $`|\varphi \varphi |`$. The density matrix corresponding to a mixed state, which is in pure state $`|\varphi _i`$ with probability $`p_i`$, is $`\rho =_ip_i|\varphi _i\varphi _i|`$. If a 2-register quantum state has the form $`|\varphi =_i\sqrt{p_i}|i|\varphi _i`$, then the state of a system holding only the second register of $`|\varphi `$ is described by the (reduced) density matrix $`_ip_i|\varphi _i\varphi _i|`$.

The most general measurement allowed by quantum mechanics is a so-called positive operator-valued measurement (POVM). A $`k`$-outcome POVM is specified by positive operators $`E_i=M_i^{}M_i`$, $`1ik`$, subject to the condition that $`_iE_i=I`$. Given a state $`\rho `$, the probability of getting the $`i`$th outcome is $`p_i=\text{Tr}(E_i\rho )=\text{Tr}(M_i\rho M_i^{})`$. If the outcome is indeed $`i`$, then the resulting state is $`M_i\rho M_i^{}/\text{Tr}(M_i\rho M_i^{})`$. In particular, if $`\rho =|\varphi \varphi |`$, then $`p_i=\varphi |E_i|\varphi =M_i|\varphi ^2`$, and the resulting state is $`M_i|\varphi /M_i|\varphi `$. A special case is where $`k=2^m`$ and $`B=\{|\psi _i\}`$ forms an orthonormal basis of the $`m`$-qubit space. “Measuring in the $`B`$-basis” means that we apply the POVM given by $`E_i=M_i=|\psi _i\psi _i|`$. Applying this to a pure state $`|\varphi `$ gives resulting state $`|\psi _i`$ with probability $`p_i=|\varphi |\psi _i|^2`$. Apart from measurements, the basic operations that quantum mechanics allows us to do, are unitary (i.e., linear norm-preserving) transformations of the vector of amplitudes.

Finally, a word about quantum queries. A query to an $`m`$-bit string $`y`$ is commonly formalized as the following unitary transformation, where $`j[m]`$, and $`b\{0,1\}`$ is called the target bit:

$$|j|b|j|by_j.$$

A quantum computer may apply this to any superposition. An equivalent formalization that we will be using here, is:

$$|c|j(1)^{cy_j}|c|j.$$

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.

### 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`$ while making only few queries to $`y`$.

###### Definition 1

$`C:\{0,1\}^n\{0,1\}^m`$ is a $`(q,\delta ,\epsilon )`$-locally decodable code (LDC) if there is a classical randomized decoding algorithm $`A`$ such that

1. $`A`$ makes at most $`q`$ queries to $`y`$, non-adaptively.
2. For all $`x`$ and $`i`$, and all $`y\{0,1\}^m`$ with Hamming distance $`d(C(x),y)\delta m`$ we have $`\mathrm{Pr}[A^y(i)=x_i]1/2+\epsilon `$.

The LDC is called linear if $`C`$ is a linear function over $`GF(2)`$ (i.e., $`C(x+y)=C(x)+C(y)`$).

By allowing $`A`$ to be a quantum computer and to make queries in superposition, we can similarly define $`(q,\delta ,\epsilon )`$-locally quantum-decodable codes (LQDCs).

It will be convenient to work with non-adaptive queries, as used in the above definition, 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 first remark at the end of Section 3.3.

### 2.3 Private information retrieval

Next we formally define private information retrieval schemes.

###### Definition 2

A one-round, $`(1\delta )`$-secure, $`k`$-server private information retrieval (PIR) scheme with recovery probability $`1/2+\epsilon `$, query size $`t`$, and answer size $`a`$, consists of a randomized algorithm representing the user, and $`k`$ deterministic algorithms $`S_1,\mathrm{},S_k`$ (the servers), such that

1. On input $`i[n]`$, the user produces $`k`$ $`t`$-bit queries $`q_1,\mathrm{},q_k`$ and sends these to the respective servers. The $`j`$th server sends back an $`a`$-bit string $`a_j=S_j(x,q_j)`$. The user outputs a bit $`b`$ depending on $`i,a_1,\mathrm{},a_k,`$ and his randomness.
2. For all $`x`$ and $`i`$, the probability (over the user’s randomness) that $`b=x_i`$ is at least $`1/2+\epsilon `$.
3. For all $`x`$ and $`j`$, the distributions on $`q_j`$ (over the user’s randomness) are $`\delta `$-close (in total variation distance) for different $`i`$.

The scheme is called linear if, for every $`j`$ and $`q_j`$, the $`j`$th server’s answer $`S_j(x,q_j)`$ is a linear combination (over $`GF(2)`$) of the bits of $`x`$.

All known upper bounds on PIR have one round, $`\epsilon =1/2`$ (perfect recovery) and $`\delta =0`$ (the servers get no information whatsoever about $`i`$). Below we will assume one round and $`\delta =0`$ without mentioning this further. We can straightforwardly generalize these definitions to quantum PIR for the case where $`\delta =0`$ (the server’s state after the query should be independent of $`i`$), and that is the only case we will need here.

## 3 Lower Bound for Locally Decodable Codes with Two Queries

The proof has two parts, each with a clear intuition but requiring quite a few technicalities:

1. A 2-query LDC gives 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 its indices turns out to be a $`\mathrm{log}m`$-qubit quantum random access code for $`x`$, for which a linear lower bound is already known .

### 3.1 From 2 classical queries to 1 quantum query

The key to the first step is the following lemma:

###### Lemma 1

Let $`f:\{0,1\}^2\{0,1\}`$ and suppose we can make queries to the bits of some input string $`a=a_1a_2\{0,1\}^2`$. 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 $`1f(a)`$ otherwise.

Proof.  The quantum algorithm makes the query $`\frac{1}{\sqrt{3}}\left(|0|1+|1|1+|1|2\right),`$ where the first bit is the control bit, and the appropriate phase $`(1)^{a_j}`$ is added in front of $`|j`$ if the control bit is 1. The result of the query is the state

$$|\varphi =\frac{1}{\sqrt{3}}\left(|0|1+(1)^{a_1}|1|1+(1)^{a_2}|1|2\right).$$

The algorithm then measures this state in a basis containing the following four states ($`b\{0,1\}^2`$):

$$|\psi _b=\frac{1}{2}\left(|0|1+(1)^{b_1}|1|1+(1)^{b_2}|1|2+(1)^{b_1+b_2}|0|2\right).$$

Note that these four states are orthogonal to each other.

The probability of getting outcome $`a`$ is $`|\varphi |\psi _a|^2=3/4`$, and each of the other 3 outcomes has probability $`1/12`$. The algorithm determines its output based on $`f`$ and on the measurement outcome $`b`$. We distinguish 3 cases for $`f`$:

1. $`|f(1)^1|=1`$ (the case $`|f(1)^1|=3`$ is completely analogous, with 0 and 1 reversed). If $`f(b)=1`$, then the algorithm outputs 1 with probability 1. If $`f(b)=0`$ then it outputs 0 with probability $`6/7`$ and 1 with probability $`1/7`$. Accordingly, if $`f(a)=1`$, then the probability of outputting 1 is $`\mathrm{Pr}[f(b)=1]1+\mathrm{Pr}[f(b)=0]1/7=3/4+1/28=11/14.`$ If $`f(a)=0`$, then the probability of outputting 0 is $`\mathrm{Pr}[f(b)=0]6/7=(11/12)(6/7)=11/14.`$
2. $`|f(1)^1|=2`$. Then $`\mathrm{Pr}[f(a)=f(b)]=3/4+1/12=5/6`$. If the algorithm outputs $`f(b)`$ with probability $`13/14`$ and outputs $`1f(b)`$ with probability $`1/14`$, then its probability of outputting $`f(a)`$ is exactly $`11/14`$.
3. $`f`$ is constant. In that case the algorithm just outputs that value with probability $`11/14`$.

$`\mathrm{}`$

Peter Høyer (personal communication) recently improved the $`11/14`$ in the above lemma to $`9/10`$, which we can show to be optimal. Using our lemma we can prove:

###### Theorem 1

A $`(2,\delta ,\epsilon )`$-locally decodable code is a $`(1,\delta ,4\epsilon /7)`$-locally quantum-decodable code.

Proof.  Consider some $`i`$, $`x`$, and $`y`$ such that $`d(C(x),y)\delta 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 $`j,k[m]`$ and an $`f:\{0,1\}^2\{0,1\}`$ such that

$$\mathrm{Pr}[f(y_j,y_k)=x_i]=p1/2+\epsilon ,$$

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 $`o`$ such that

$$\mathrm{Pr}[o=f(y_j,y_k)]=11/14.$$

The success probability of this quantum decoder is:333Here 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 $`\mathrm{AND}(y_1,y_2)=x_i`$ with probability $`3/5`$ and $`\mathrm{XOR}(y_3,y_4)=1x_i`$ with probability $`2/5`$. Then it outputs $`x_i`$ with probability $`3/5>1/2`$. However, if our quantum procedure computes $`\mathrm{AND}(y_1,y_2)`$ with success probability $`11/14`$ but $`\mathrm{XOR}(y_3,y_4)`$ with success probability 1, then its recovery probability is $`(3/5)(11/14)<1/2`$.

$`\mathrm{Pr}[o=x_i]`$ $`=`$ $`\mathrm{Pr}[o=f(y_j,y_k)]\mathrm{Pr}[f(y_j,y_k)=x_i]+\mathrm{Pr}[of(y_j,y_k)]\mathrm{Pr}[f(y_j,y_k)x_i]`$
$`=`$ $`{\displaystyle \frac{11}{14}}p+{\displaystyle \frac{3}{14}}(1p)={\displaystyle \frac{3}{14}}+{\displaystyle \frac{4}{7}}p{\displaystyle \frac{1}{2}}+{\displaystyle \frac{4\epsilon }{7}}.`$
$`\mathrm{}`$

### 3.2 Exponential lower bound for 1-query LQDCs

A quantum random access code is an encoding $`x\rho _x`$ of $`n`$-bit strings $`x`$ into $`m`$-qubit states $`\rho _x`$, such that any bit $`x_i`$ can be recovered with some probability $`p1/2+\epsilon `$ from $`\rho _x`$. The following lower bound is known on the length of such quantum codes  (see Appendix A for a proof).

###### Theorem 2 (Nayak)

An encoding $`x\rho _x`$ of $`n`$-bit strings into $`m`$-qubit states with recovery probability at least $`p`$, has $`m(1H(p))n`$.

This allows us to prove an exponential lower bound for 1-query LQDC:

###### Theorem 3

If $`C:\{0,1\}^n\{0,1\}^m`$ is a $`(1,\delta ,\epsilon )`$-locally quantum-decodable code, then

$$m2^{cn1},$$

for $`c=1H(1/2+\delta \epsilon /4)`$.

Proof.  We fix $`i`$. Let $`|Q=_{c\{0,1\},j[m]}\alpha _{cj}|c|j`$ be the query that the quantum decoder makes to recover $`x_i`$. Let $`D`$ and $`ID`$ be the two POVM operators that the decoder uses on the state $`|R`$ returned by the query, corresponding to outcomes 1 and 0, respectively. Its probability of outputting 1 on $`|R`$ is $`p(R)=R|D|R=\sqrt{D}|R^2`$. Without loss of generality, we assume that all $`\alpha _{cj}`$ are non-negative reals (this is the most general query a quantum decoder can ask, because complex phases and entanglement with its workspace can always be added by the decoder after the query). Since $`C`$ is a LQDC, the decoder can recover $`x_i`$ with probability $`1/2+\epsilon `$ from the state

$$\underset{c\{0,1\},j[m]}{}\alpha _{cj}(1)^{cy_j}|c|j$$

for every $`y`$ such that $`d(C(x),y)\delta m`$. Our goal below is to show that we can also recover $`x_i`$ with probability $`1/2+\delta \epsilon /4`$ from the uniform state

$$|U(x)=\frac{1}{\sqrt{2m}}\underset{c\{0,1\},j[m]}{}(1)^{cC(x)_j}|c|j.$$

Since $`|U(x)`$ is independent of $`i`$, we can actually recover any bit $`x_j`$ with that probability. Hence $`|U(x)`$ is a $`(\mathrm{log}(m)+1)`$-qubit random access code for $`x`$. Applying Theorem 2 gives the result.

Inspired by the “smoothing” technique of , we split the amplitudes $`\alpha _j`$ of the query $`|Q`$ into small and large ones: $`A=\{cj:\alpha _{cj}\sqrt{1/\delta m}\}`$ and $`B=\{cj:\alpha _{cj}>\sqrt{1/\delta m}\}`$. Since the query does not affect the $`|0|j`$-states, we can assume without loss of generality that $`\alpha _{0j}`$ is the same for all $`j`$, so $`\alpha _{0j}1/\sqrt{m}1/\sqrt{\delta m}`$ and hence $`0jA`$. Let $`a=\sqrt{_{cjA}\alpha _{cj}^2}`$ be the norm of the “small-amplitude” part. Since $`_{cjB}\alpha _{cj}^21`$, we have $`|B|<\delta m`$. Define non-normalized states

$$|A(x)=\underset{cjA}{}(1)^{cC(x)_j}\alpha _{cj}|c|j\text{ and }|B=\underset{cjB}{}\alpha _{cj}|c|j.$$

The states $`|A(x)+|B`$ and $`|A(x)|B`$ each correspond to a $`y\{0,1\}^m`$ that is corrupted (compared to $`C(x)`$) in at most $`|B|\delta m`$ positions, so the decoder can recover $`x_i`$ from each of these states. If $`x`$ has $`x_i=1`$, then

$$p(A(x)+B)1/2+\epsilon \text{ and }p(A(x)B)1/2+\epsilon .$$

Since $`p(A\pm B)=p(A)+p(B)\pm (A|D|B+B|D|A)`$, averaging the previous two inequalities gives

$$p(A(x))+p(B)1/2+\epsilon .$$

Similarly, if $`x^{}`$ has $`x_i^{}=0`$, then

$$p(A(x^{}))+p(B)1/2\epsilon .$$

Hence, for the normalized states $`|A(x)/a`$ and $`|A(x^{})/a`$ we have

$$p(A(x)/a)p(A(x^{})/a)2\epsilon /a^2.$$

Since this holds for every $`x,x^{}`$ with $`x_i=1`$ and $`x_i^{}=0`$, there are constants $`q_1,q_0[0,1]`$, $`q_1q_02\epsilon /a^2`$, such that $`p(A(x)/a)q_1`$ whenever $`x_i=1`$ and $`p(A(x)/a)q_0`$ whenever $`x_i=0`$.

If we had a copy of the state $`|A(x)/a`$, then we could run the procedure below to recover $`x_i`$. Here we assume that $`q_11/2+\epsilon /a^2`$ (if not, then we must have $`q_01/2\epsilon /a^2`$ and we can use the same argument with 0 and 1 reversed), and that $`q_1+q_01`$ (if not, then $`q_01/2\epsilon /a^2`$ and we’re already done).

> Output 0 with probability $`q=11/(q_1+q_0)`$,
> and otherwise output the result of running the decoder’s POVM on $`|A(x)/a`$.

If $`x_i=1`$, then the probability that this procedure outputs 1 is

$$(1q)p(A(x)/a)(1q)q_1=\frac{q_1}{q_1+q_0}=\frac{1}{2}+\frac{q_1q_0}{2(q_1+q_0)}\frac{1}{2}+\frac{\epsilon }{2a^2}.$$

If $`x_i=0`$, then the probability that it outputs 0 is

$$q+(1q)(1p(A(x)/a))q+(1q)(1q_0)=1\frac{q_0}{q_1+q_0}=\frac{q_1}{q_1+q_0}\frac{1}{2}+\frac{\epsilon }{2a^2}.$$

Thus, we can recover $`x_i`$ with good probability if we had the state $`|A(x)/a`$.

It remains to show how we can obtain $`|A(x)/a`$ from $`|U(x)`$ with reasonable probability. This we do by applying a POVM with operators $`M^{}M`$ and $`IM^{}M`$ to $`|U(x)`$, where $`M=\sqrt{\delta m}_{cjA}\alpha _{cj}|cjcj|`$. Both $`M^{}M`$ and $`IM^{}M`$ are positive operators (as required for a POVM) because $`0\sqrt{\delta m}\alpha _{cj}1`$ for all $`cjA`$. The POVM gives the first outcome with probability

$$U(x)|M^{}M|U(x)=\frac{\delta m}{2m}\underset{cjA}{}\alpha _{cj}^2=\delta a^2/2.$$

In this case we have obtained the normalized version of $`M|U(x)`$, which is $`|A(x)/a`$, so then we can run the above procedure to recover $`x_i`$. If the measurement gives the second outcome, then we just output a fair coin flip. Thus we recover $`x_i`$ from $`|U(x)`$ with probability at least

$$(\delta a^2/2)(1/2+\epsilon /2a^2)+(1\delta a^2/2)1/2=1/2+\delta \epsilon /4.$$

$`\mathrm{}`$

### 3.3 Exponential lower bound for 2-query LDCs

###### Theorem 4

If $`C:\{0,1\}^n\{0,1\}^m`$ is a $`(2,\delta ,\epsilon )`$-locally decodable code, then

$$m2^{cn1},$$

for $`c=1H(1/2+3\delta \epsilon /14)`$.

Proof.  The theorem follows by combining Theorems 1 and 3. Straightforwardly, this would give a constant of $`1H(1/2+\delta \epsilon /7)`$. 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 $`\alpha _{0j}`$ are in $`A`$). Hence in the proof of Theorem 3, we can redefine “small amplitude” to $`\alpha _{cj}\sqrt{2/3\delta m}`$, and still $`B`$ will have at most $`\delta m`$ elements because $`_{cjB}\alpha _{cj}^22/3`$. This in turns allows us to make $`M`$ a factor $`\sqrt{3/2}`$ larger, which improves the probability of getting $`|A(x)/a`$ from $`|U(x)`$ to $`3\delta a^2/4`$ and the recovery probability to $`1/2+3\delta \epsilon /8`$. Combining that with Theorem 1 (which makes $`\epsilon `$ a factor $`4/7`$ smaller) gives $`c=1H(1/2+3\delta \epsilon /14)`$, as claimed. $`\mathrm{}`$

Remarks:

(1) A $`(2,\delta ,\epsilon )`$-LDC with adaptive queries gives a $`(2,\delta ,\epsilon /2)`$-LDC with non-adaptive queries: if query $`q_1`$ would be followed by query $`q_2^0`$ or $`q_2^1`$ depending on the outcome of $`q_1`$, then we can just guess in advance whether to query $`q_1`$ and $`q_2^0`$, or $`q_1`$ and $`q_2^1`$. With probability 1/2, the second query will be the one we would have made in the adaptive case and we’re fine, in the other case we just flip a coin, giving overall recovery probability $`1/2(1/2+\epsilon )+1/2(1/2)=1/2+\epsilon /2`$. Thus we also get slightly weaker but still exponential lower bounds for adaptive 2-query LDCs.

(2) For a $`(2,\delta ,\epsilon )`$-LDC where the decoder’s output is the XOR of its two queries, we can give a better reduction than in Theorem 1. In this case, the quantum decoder can apply his query to $`\frac{1}{\sqrt{2}}\left(|1|1+|1|2\right),`$ giving

$$\frac{1}{\sqrt{2}}\left((1)^{a_1}|1|1+(1)^{a_2}|1|2\right)=(1)^{a_1}\frac{1}{\sqrt{2}}\left(|1|1+(1)^{a_1a_2}|1|2\right),$$

and extract $`a_1a_2`$ from this with certainty. Thus the recovery probability remains $`1/2+\epsilon `$ instead of going down to $`1/2+4\epsilon /7`$. Accordingly, we also get slightly better lower bounds for 2-query LDCs where the output is the XOR of the two queried bits, namely $`c=1H(1/2+3\delta \epsilon /8)`$.

(3) In Appendix B we extend the lower bound to larger alphabets.

## 4 Locally Quantum-Decodable Codes with Few Queries

The second remark of Section 3.3 immediately generalizes to:

###### Theorem 5

A $`(2q,\delta ,ϵ)`$-LDC where the decoder’s output is the XOR of the $`2q`$ queried bits, is a $`(q,\delta ,\epsilon )`$-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. \[4, 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 $`m=2^{n^{O(\mathrm{log}\mathrm{log}q/q\mathrm{log}q)}}`$ for $`q`$-query LDCs, for some constant depending on $`\delta `$ and $`ϵ`$, as well as more precise estimates for small $`q`$. In particular, for $`q=4`$ they construct an LDC of length $`m=2^{O(n^{3/10})}`$. All their LDCs 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 $`m=2^{O(n^{3/10})}`$. In contrast, any 2-query LDC requires length $`m=2^{\mathrm{\Omega }(n)}`$ as we 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(\sqrt{q})`$ quantum queries :

###### Theorem 6

A $`(q,\delta ,ϵ)`$-LDC is a $`(q/2+O(\sqrt{q}),\delta ,\epsilon /2)`$-LQDC.

## 5 Private Information Retrieval

### 5.1 Lower bounds for classical PIR

As mentioned, there is a close connection between locally decodable codes and private information retrieval. Our techniques allow us to give new lower bounds for 2-server PIRs. Again we 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 7

If there exists a classical 2-server PIR scheme with $`t`$-bit queries, 1-bit answers, and recovery probability $`1/2+\epsilon `$, then there exists a quantum 1-server PIR scheme with $`(t+2)`$-qubit queries, $`(t+2)`$-qubit answers, and recovery probability $`1/2+4\epsilon /7`$.

Proof.  The proof is analogous to the proof for locally decodable codes. If we let the quantum user use the same randomness as the classical one, the problem boils down to computing some $`f(a_1,a_2)`$, where $`a_1`$ is the first 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+t)`$-qubit state

$$\frac{1}{\sqrt{3}}\left(|0|0,0^t+|1|1,q_1+|2|2,q_2\right),$$

where ‘$`0^t`$’ is a string of $`t`$ 0s. The user sends everything but the first register to the server. The state of the server is now a uniform mixture of $`|0,0^t`$, $`|1,q_1`$, and $`|2,q_2`$. By the security of the classical protocol, $`|1,q_1`$ contains no information about $`i`$ (averaged over the user’s randomness), and the same holds for $`|2,q_2`$. Hence the server gets no information about $`i`$.

The quantum server then puts $`(1)^{a_j}`$ in front of $`|j,q_j`$ ($`j\{1,2\}`$), leaves $`|0,0^t`$ alone, and sends everything back. Note that we need to supply the name of the classical server $`j\{1,2\}`$ to tell the server in superposition whether it should play the role of server 1 or 2. The user now has

$$\frac{1}{\sqrt{3}}\left(|0|0,0^t+(1)^{a_1}|1|1,q_1+(1)^{a_2}|2|2,q_2\right).$$

From this we can compute $`f(a_1,a_2)`$ with success probability exactly $`11/14`$, giving overall recovery probability $`1/2+4\epsilon /7`$ as before. $`\mathrm{}`$

Combining the above reduction with the quantum random access code lower bound, we obtain the first $`\mathrm{\Omega }(n)`$ lower bound that holds for all 1-bit-answer 2-server PIRs, not just for linear ones.

###### Theorem 8

A classical 2-server PIR scheme with $`t`$-bit queries, 1-bit answers, and recovery probability $`1/2+\epsilon `$, has $`t(1H(1/2+4\epsilon /7))n2`$.

Proof.  We first reduce the 2 classical servers to 1 quantum server in the way of Theorem 7. Now consider the state of the quantum PIR scheme after the user sends his $`(t+2)`$-qubit message:

$$|\varphi _i=\underset{r}{}\sqrt{p_r}|r\frac{1}{\sqrt{3}}\left(|0|0,0^t+|1|1,q_1(r,i)+|2|2,q_2(r,i)\right).$$

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 $`B=\{0^{t+1}\}\{1,2\}\times \{0,1\}^t`$ be the server’s basis states, we can write $`|\varphi _i`$ as:

$$|\varphi _i=\underset{bB}{}\lambda _b|a_{ib}|b.$$

Here the $`|a_{ib}`$ are pure states that do not depend on $`x`$. The coefficients $`\lambda _b`$ are non-negative reals that do not depend on $`i`$, for otherwise a measurement of $`b`$ would give the server information about $`i`$ (contradicting privacy). The server then tags on the appropriate phase $`s_{bx}`$, which is 1 for $`b=0^{t+1}`$ and $`(1)^{S_j(x,q_j)}`$ for $`b=jq_j`$, $`j\{1,2\}`$. This gives

$$|\varphi _{ix}=\underset{bB}{}\lambda _b|a_{ib}s_{bx}|b.$$

Now the following pure state will be a random access code for $`x`$

$$|\psi _x=\underset{bB}{}\lambda _bs_{bx}|b,$$

because a user can unitarily map $`|0|b|a_{ib}|b`$ to map $`|0|\psi _x|\varphi _{ix}`$, from which he can get $`x_i`$ with probability $`p=1/2+4\epsilon /7`$ by completing the quantum PIR protocol. The state $`|\psi _x`$ has $`t+2`$ qubits, hence from Theorem 2 we obtain $`t(1H(p))n2`$. $`\mathrm{}`$

In Appendix B we extend this bound to classical 2-server PIR schemes with larger answer size.

For the special case where the classical PIR outputs the XOR of the two answer bits, we can improve our lower bound to $`t(1H(1/2+\epsilon ))n1`$. In particular, $`tn1`$ in case of perfect recovery ($`\epsilon =1/2`$), which is tight. Very recently but independently of our work, Beigel, Fortnow, and Gasarch  found a classical proof that a 2-server PIR with perfect recovery and 1-bit answers needs query length $`tn2`$ (no matter whether it uses XOR or not).

### 5.2 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 efficient LQDCs. Similarly, we can also turn the underlying classical $`k`$-server PIR schemes directly into quantum PIR schemes with $`k/2`$ servers.

Most interestingly, there exists a 4-server PIR with 1-bit answers and communication complexity $`O(n^{3/10})`$ \[4, 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. . In the introduction we mentioned also some upper bounds for $`k>2`$, which are obtained similarly.

### Acknowledgments

We thank Luca Trevisan for many insightful comments throughout this work and also for allowing us to include Lemma 2 in Appendix A. We also thank Harry Buhrman, Peter Høyer, Hartmut Klauck, Ashwin Nayak, Kenji Obata, Pranab Sen (and via him also Rahul Jain), Mario Szegedy, and Ashish Thapliyal for helpful discussions. We thank Amos Beimel for sending us a version of  and Bill Gasarch for sending us a version of .

## Appendix A Lower Bound for Quantum Random Access Codes

As mentioned before, a quantum random access code is an encoding $`x\rho _x`$, such that any bit $`x_i`$ can be recovered with some probability $`p1/2+\epsilon `$ from $`\rho _x`$. Below we reprove Nayak’s  linear lower bound on the length $`m`$ of such encodings.

We assume familiarity with the following notions from quantum information theory, referring to \[14, Chapters 11 and 12\] for more details. Very briefly, if we have a bipartite quantum system $`AB`$ (given by some density matrix), then we use $`A`$ and $`B`$ to denote the states (reduced density matrices) of the individual systems. $`S(A)=\text{Tr}(A\mathrm{log}A)`$ is the (Von Neumann) entropy of $`A`$; $`S(A|B)=S(AB)S(B)`$ is the conditional entropy of $`A`$ given $`B`$; and $`S(A:B)=S(A)+S(B)S(AB)=S(A)S(A|B)`$ is the mutual information between $`A`$ and $`B`$.

We define an $`n+m`$-qubit state $`XM`$ as follows:

$$\frac{1}{2^n}\underset{x\{0,1\}^n}{}|xx|\rho _x.$$

We use $`X`$ to denote the first subsystem, $`X_i`$ for its individual bits, and $`M`$ for the second subsystem. By \[14, Theorem 11.8.4\] we have

$$S(XM)=n+\frac{1}{2^n}\underset{x}{}S(\rho _x)n=S(X).$$

Since $`M`$ has $`m`$ qubits we have $`S(M)m`$, hence

$$S(X:M)=S(X)+S(M)S(XM)S(M)m.$$

Using a chain rule for relative entropy, and the subadditivity of Von Neumann entropy we get

$$S(X|M)=\underset{i=1}{\overset{n}{}}S(X_i|X_1\mathrm{}X_{i1}M)\underset{i=1}{\overset{n}{}}S(X_i|M).$$

Since we can predict $`X_i`$ from $`M`$ with success probability $`p`$, Fano’s inequality implies

$$H(p)S(X_i|M).$$

In fact, Fano’s inequality even applies under the weaker assumption that the success probability in predicting $`x_i`$ is $`p`$ only when averaged over all $`x`$. Putting the above equations together we obtain

$$(1H(p))nS(X)\underset{i=1}{\overset{n}{}}S(X_i|M)S(X)S(X|M)=S(X:M)m.$$

## Appendix B Extension to Larger Alphabets

In this section we extend our lower bounds for binary 2-query LDCs to the case of larger alphabets (and our bounds for binary 2-server PIR schemes to the case of larger answers). For simplicity we assume the alphabet is $`\mathrm{\Sigma }=\{0,1\}^{\mathrm{}}`$, so a query to position $`j`$ now returns an $`\mathrm{}`$-bit string $`C(x)_j`$. The definition of $`(q,\delta ,\epsilon )`$-LDC from Section 2.2 carries over immediately, with $`d(C(x),y)`$ now measuring the Hamming distance between $`C(x)\mathrm{\Sigma }^m`$ and $`y\mathrm{\Sigma }^m`$.

We will need the notion of smooth codes and their connection to LDCs as stated in .

###### Definition 3

$`C:\{0,1\}^n\mathrm{\Sigma }^m`$ 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 $`\mathrm{Pr}[A^{C(x)}(i)=x_i]1/2+\epsilon `$
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 \[11, Theorem 1\] established the following connection:

###### Theorem 9 (Katz and Trevisan)

Let $`C:\{0,1\}^n\mathrm{\Sigma }^m`$ be a $`(q,\delta ,\epsilon )`$-locally decodable code. Then $`C`$ is also a $`(q,q/\delta ,\epsilon )`$-smooth code.

In order to prove the exponential lower bound for LDCs over non-binary alphabet $`\mathrm{\Sigma }`$, we will reduce a smooth code over $`\mathrm{\Sigma }`$ 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.

###### Lemma 2 (Trevisan)

Let $`C:\{0,1\}^n\mathrm{\Sigma }^m`$ be a $`(2,c,\epsilon )`$-smooth code. Then, there exists a $`(2,c2^{\mathrm{}},\epsilon /2^2\mathrm{})`$-smooth code $`C^{}:\{0,1\}^n\{0,1\}^{m2^{\mathrm{}}}`$ that is good on average, i.e., there is a decoder $`A`$ such that for all $`i[n]`$

$$\frac{1}{2^n}\underset{x\{0,1\}^n}{}\mathrm{Pr}[A^{C^{}(x)}(i)=x_i]\frac{1}{2}+\frac{\epsilon }{2^2\mathrm{}}.$$

Proof.  We form the new binary code $`C^{}`$ by replacing each symbol $`C(x)_j\mathrm{\Sigma }`$ of the old code by its Hadamard code, which consists of $`2^{\mathrm{}}`$ bits. The length of $`C^{}(x)`$ is $`m2^{\mathrm{}}`$ bits. The new decoding algorithm uses the same randomness as the old one. Let us fix the two queries $`j,k[m]`$ and the output function $`f:\mathrm{\Sigma }^2\{0,1\}`$ 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=C(x)_j`$ and $`b=C(x)_k`$.

First, if for this specific $`j,k,f`$ we have $`\mathrm{Pr}_x[f(a,b)=x_i]1/2`$, 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 $`\mathrm{Pr}_x[f(a,b)=x_i]=1/2+\eta `$ for some $`\eta >0`$. Switching from the $`\{0,1\}`$-notation to the $`\{1,1\}`$-notation enables us to say that $`E_x[f(a,b)x_i]=2\eta `$. Viewing $`a`$ and $`b`$ as two $`\mathrm{}`$-bit strings, we can represent $`f`$ by its Fourier representation: $`f(a,b)=_{S,T[\mathrm{}]}\widehat{f}_{S,T}_{sS}a_s_{tT}b_t`$ and hence

$$\underset{S,T}{}\widehat{f}_{S,T}E_x\left[\underset{sS}{}a_s\underset{tT}{}b_tx_i\right]=E_x\left[\left(\underset{S,T}{}\widehat{f}_{S,T}\underset{sS}{}a_s\underset{tT}{}b_t\right)x_i\right]=E_x[f(a,b)x_i]=2\eta .$$

Averaging and using that $`|\widehat{f}_{S_0,T_0}|1`$, it follows that there exist subsets $`S_0,T_0`$ such that

$$\left|E_x\left[\underset{sS_0}{}a_s\underset{tT_0}{}b_tx_i\right]\right|\widehat{f}_{S_0,T_0}E_x\left[\underset{sS_0}{}a_s\underset{tT_0}{}b_tx_i\right]\frac{2\eta }{2^2\mathrm{}}.$$

Returning to the $`\{0,1\}`$-notation, we must have either

$$\underset{x}{\mathrm{Pr}}[S_0aT_0b=x_i]1/2+\eta /2^2\mathrm{}$$

or

$$\underset{x}{\mathrm{Pr}}[S_0aT_0b=x_i]1/2\eta /2^2\mathrm{},$$

where $`S_0a`$ and $`T_0b`$ denote inner products mod 2 of $`\mathrm{}`$-bit strings. Accordingly, either the XOR of the two bits $`S_0a`$ and $`T_0b`$, or its negation, predicts $`x_i`$ with average probability $`1/2+\eta /2^2\mathrm{}`$. Both of these bits are in the binary code $`C^{}(x)`$. The $`c`$-smoothness of $`C`$ translates into $`c2^{\mathrm{}}`$-smoothness of $`C^{}`$. Averaging over the classical randomness (i.e. the choice of $`j,k`$, and $`f`$) gives the lemma. $`\mathrm{}`$

This lemma enables us to modify our proof of Theorem 4 so that it works for non-binary alphabets $`\mathrm{\Sigma }`$:

###### Theorem 10

If $`C:\{0,1\}^n\mathrm{\Sigma }^m=(\{0,1\}^{\mathrm{}})^m`$ is a $`(2,\delta ,\epsilon )`$-locally decodable code, then

$$m2^{cn\mathrm{}},$$

for $`c=1H(1/2+\delta \epsilon /2^{3\mathrm{}+1})`$.

Proof.  Using Theorem 9 and Lemma 2, we turn $`C`$ into a binary $`(2,2^{\mathrm{}+1}/\delta ,\epsilon /2^2\mathrm{})`$-smooth code $`C^{}`$ that has average recovery probability $`1/2+\epsilon /2^2\mathrm{}`$ and length $`m^{}=m2^{\mathrm{}}`$ 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 second remark following Theorem 4).

We now reduce this quantum smooth code to a quantum random access code, by a modified version of the proof of Theorem 4. The smoothness of $`C^{}`$ implies that all amplitudes $`\alpha _j`$ (which depend on $`i`$) in the one quantum query satisfy $`\alpha _j\sqrt{2^{\mathrm{}+1}/\delta m^{}}`$. 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 $`|U(x)=\frac{1}{\sqrt{m^{}}}_{j=1}^m^{}(1)^{C(x)_j^{}}|j`$, $`|A(x)=_{j=1}^m^{}\alpha _j(1)^{C(x)_j^{}}|j`$, and POVM operator $`M=\sqrt{\delta m^{}/2^{\mathrm{}+1}}_j\alpha _j|jj|`$. The probability that the POVM takes us from $`|U(x)`$ to $`M|U(x)=|A(x)`$ is now $`U(x)|M^{}M|U(x)=\delta /2^{\mathrm{}+1}`$. Hence $`|U(x)`$ forms a random access code with average success probability

$$p=\frac{\delta }{2^{\mathrm{}+1}}\left(\frac{1}{2}+\frac{\epsilon }{2^2\mathrm{}}\right)+\left(1\frac{\delta }{2^{\mathrm{}+1}}\right)\frac{1}{2}=\frac{1}{2}+\frac{\delta \epsilon }{2^{3\mathrm{}+1}}.$$

The $`(1H(p))n`$ lower bound for a quantum random access code holds even if the recovery probability $`p`$ is only an average over $`x`$, hence we obtain $`\mathrm{log}(m^{})(1H(p))n`$. $`\mathrm{}`$

We can also extend our linear lower bound on 2-server PIR schemes with answer length $`a=1`$ (Theorem 8) to the case of larger answer length. We use the reduction from PIR to smooth codes given by Lemma 7.1 of :

###### Lemma 3 (GKST)

If there is a classical 2-server PIR scheme with query length $`t`$, answer length $`a`$, and recovery probability $`1/2+\epsilon `$, then there is a $`(2,3,\epsilon )`$-smooth code $`C:\{0,1\}^n\mathrm{\Sigma }^m`$ for $`\mathrm{\Sigma }=\{0,1\}^a`$ and $`m62^t`$.

Going through roughly the same steps as for the above LDC lower bound, we get:

###### Theorem 11

A classical 2-server PIR scheme with $`t`$-bit queries, $`a`$-bit answers, and recovery probability $`1/2+\epsilon `$, has $`t\mathrm{\Omega }(n\epsilon ^2/2^{6a})`$.