text:
# Close-packed floating clusters: granular hydrodynamics beyond the freezing point?

## Abstract

Monodisperse granular flows often develop regions with hexagonal close packing of particles. We investigate this effect in a system of inelastic hard spheres driven from below by a “thermal” plate. Molecular dynamics simulations show, in a wide range of parameters, a close-packed cluster supported by a low-density region. Surprisingly, the steady-state density profile, including the close-packed cluster part, is well described by a variant of Navier-Stokes granular hydrodynamics (NSGH). We suggest a simple explanation for the success of NSGH beyond the freezing point.

Continuum modeling of flow of macroscopic grains remains a challenge Kadanoff ; Mills ; Aranson1 ; Bocquet ; Aranson2 . The best known version of continuum theory here is the Navier-Stokes granular hydrodynamics (NSGH) for a system of inelastic hard spheres Haff ; Jenkins . The applicability of NSGH is limited to rapid granular flows Campbell . By definition, these flows are dominated by binary particle collisions, while multi-particle interactions are negligible. Despite this drastic simplification, the validity of the NSGH demands several additional assumptions, some of which can be rather stringent. Under the molecular chaos assumption, the NSGH is derivable systematically from more fundamental kinetic equations for inelastic hard spheres Jenkins ; Sela ; Brey1 . Going over from kinetic equations to hydrodynamics, one should assume scale separation: the mean free path of the particles should be much smaller than the characteristic length scale, and the mean time between two consecutive collisions much shorter than any characteristic time scale, described hydrodynamically. The inelasticity of particle collisions brings immediate complications. Already at moderate inelasticity $`q=(1r)/2`$ (where $`r`$ is the coefficient of normal restitution of the particle collisions), the scale separation may break down, even in the low-density limit Grossman ; Goldhirsch . The normal stress difference Goldhirsch  and deviations of the particle velocity distribution Grossman ; Poeschel  from the Maxwell distribution also become important for moderately inelastic collisions. Therefore, the NSGH is expected to be accurate only for small inelasticity, $`q1`$.

Additional complications appear at large densities. Here the molecular chaos assumption breaks down, already for elastic hard spheres, when the packing fraction approaches the freezing point value $`\varphi _f0.49`$ (in three dimensions) or $`0.69`$ (in two dimensions). As the kinetic equations become invalid, the constitutive relations (CRs), necessary for the closure of hydrodynamics, are not derivable from first principles anymore. This is the regime considered in this work. We consider an ensemble of monodisperse, nearly elastic hard spheres in such conditions that the standard NSGH Haff ; Jenkins  breaks down because of large densities, not large inelasticity. Our main objective is to check whether a variant of NSGH can still be used in an extreme case when the packing fraction is close to the maximum possible value, corresponding to hexagonal packing of spheres.

We will focus on granular materials fluidized by a rapidly vibrating bottom plate in a gravity field. Vibrofluidized granular materials exhibit fascinating pattern-formation phenomena that have attracted much recent interest patterngran . In the high-frequency and small-amplitude limit of vibrofluidization, there is no direct coupling between the vibration and the collective granular motion. In a simplified description of this limit one specifies a constant granular temperature at an immobile bottom plate. In a wide range of parameters, molecular dynamics (MD) simulations of this system show an (almost) close-packed cluster of particles, floating on a low-density fluid, see below. The close-packed floating cluster is an extreme form of the density inversion, a phenomenon well known in vibrofluidized granular materials. Lan and Rosato LanRosato95  were apparently the first to observe density inversion in three-dimensional MD simulations. Kudrolli et al. Kudrolli  observed a floating cluster in a reduced-gravity experiment: a slightly tilted two dimensional system of steel spheres rolling on a smooth surface and driven by a vibrating side wall. Recently, a pronounced density inversion has been observed, in two- and three dimensional vibrofluidized granular beds, by Wildman et al. Wildman2001 .

An accurate hydrodynamic description of almost close-packed floating clusters seems a very difficult task, as the packing fraction here is far beyond the freezing point. Still, we will attempt to use a variant of NSGH for this purpose. This attempt will prove successful, and we will suggest an explanation. Here is the model problem we are working with. Let $`N1`$ nearly elastic hard spheres of diameter $`d`$ and mass $`m`$ move in a two-dimensional box with periodic boundary conditions in $`x`$-direction (period $`L_x`$) and infinite height. The driving base is located at $`y=0`$. Gravity acceleration $`g`$ acts in negative $`y`$ direction. Upon collision with the base, the particle velocity is drawn from a Maxwell distribution with temperature $`T_0`$ (which is measured in the units of energy). The kinetic energy of the particles is being lost by inelastic hard-core collisions parameterized by a constant inelasticity parameter $`q1`$. Figure 1 shows a typical snapshot of an almost close-packed floating cluster, observed in an event-driven MD simulation of this system. Hexagonal packing is apparent in Fig. 1 defects .

Going over to a hydrodynamic description of zero-mean-flow steady states, we introduce coarse-grained fields: the particle number density $`n(y)`$, the granular temperature $`T(y)`$ and the pressure $`p(y)`$. The maximum possible value of $`n`$ is the hexagonal close-packing value $`n_c=2/(\sqrt{3}d^2)`$. A laterally uniform steady state is described by the momentum and energy balance equations:

$$\frac{dp}{dy}+mng=0,\frac{d}{dy}\left(\kappa \frac{d}{dy}T\right)I=0,$$
(1)
where $`\kappa `$ is the thermal conductivity and $`I`$ is the energy loss rate by collisions. To proceed, we need CRs: an equation of state (EOS) $`p=p(n,T)`$ and relations for $`\kappa `$ and $`I`$ in terms of $`n`$ and $`T`$. First-principles CRs are available only in the low-density limit (well below the freezing point). Grossman et al. Grossman  derived a set of approximate global CRs for a version of NSGH that assumes nearly elastic collisions, but is not limited to low densities. Grossman et al. employed free volume arguments in the close vicinity of the hexagonal packing and suggested simple interpolations between the hexagonal-packing limit and low-density limit. These interpolations include two fitting constants $`\alpha `$ and $`\gamma `$ (see below). The optimum values of these constants were found by a comparison with MD simulations of a system of inelastic hard spheres driven by a thermal wall at zero gravity Grossman .

Notice that, prescribing global CRs of any type, one grossly simplifies the delicate issue of phase coexistence that is expected to occur here in close analogy to the system of elastic hard spheres Chaikin ; Luding . Still, we will use the simple CRs Grossman  to attempt a NSGH description of the close-packed floating clusters. In our notation, the CRs Grossman  read

$$p=nT\frac{n_c+n}{n_cn},\kappa =\frac{\mu n(\alpha l+d)^2T^{1/2}}{m^{1/2}l}$$
(2)
and $`I=4(\mu /\gamma l)qnm^{1/2}T^{3/2}`$. Here $`l`$ is the mean free path of the grains,

$$l=\frac{1}{\sqrt{8}nd}\frac{n_cn}{n_can},$$
(3)
and $`a=1(3/8)^{1/2}`$. According to Grossman et al. $`\alpha =1.15`$ and $`\gamma =2.26`$. We adopted this value of $`\gamma `$, but found better agreement between the hydrodynamics and MD (see below) for $`\alpha =0.6`$. The value of $`\mu =𝒪(1)`$ drops out from the steady-state problem.

Recently a more accurate global EOS $`p=p(n,T)`$ has been suggested Luding . Still, in the absence of comparably accurate relations for $`\kappa `$ and $`I`$, employing a more accurate EOS in Eqs. (1) would be an excess of accuracy.

Equations (1) should be complemented by three boundary conditions. One of them is $`T(0)=T_0=\text{const}`$. Integrating the first of Eqs. (1) over the height from $`0`$ to $`\mathrm{}`$ and using the conservation of the total number of particles: $`_0^{\mathrm{}}n(y)𝑑y=N/L_x=\text{const}`$, we obtain the second boundary condition: $`p(0)=mgN/L_x`$. The third one is a zero heat flux (that is, a constant granular temperature) at $`y\mathrm{}`$ Eggers ; tempincrease . In practice, one should use the shooting method, varying the heat flux $`\kappa dT/dy`$ at $`y=0`$ until the third condition is satisfied with desired accuracy.

Let us measure $`y`$ in units of the gravity length scale $`\lambda =T_0/(mg)`$ (note that $`\lambda /d`$ should be large enough to fluidize the granulate at the bottom). We rewrite Eqs. (1), in scaled form, as three first-order equations:

$`{\displaystyle \frac{dP}{dy}}+{\displaystyle \frac{1}{Z}}=0,{\displaystyle \frac{d\mathrm{\Phi }}{dy}}=\mathrm{\Lambda }Q(Z)P^{3/2},`$ (4)
$`{\displaystyle \frac{d}{dy}}\left[F_2(Z)P^{3/2}\right]={\displaystyle \frac{\mathrm{\Phi }}{F_1(Z)}}.`$ (5)
Here $`Z(y)=n_c/n(y)`$ is the inverse scaled density, $`P(y)=p(y)/(n_cT_0)`$ is the scaled pressure, and $`\mathrm{\Phi }(y)`$ is the scaled heat flux. The functions $`F_1`$, $`F_2`$, and $`Q`$ are

$`F_1(Z)={\displaystyle \frac{\left[\alpha Z(Z1)+\sqrt{32/3}(Za)\right]^2}{(Za)(Z1)Z^2}},`$
$`F_2(Z)={\displaystyle \frac{(Z1)^{3/2}Z^{3/2}}{(Z+1)^{3/2}}},Q(Z)={\displaystyle \frac{(Za)(Z1)^{1/2}}{(Z+1)^{3/2}Z^{1/2}}}.`$
Finally, $`\mathrm{\Lambda }=(64/\gamma )q(\lambda /d)^2`$ and $`f=(\sqrt{3}d^2N)/(2\lambda L_x)`$ are two scaled governing parameters. Parameter $`\mathrm{\Lambda }`$ controls the relative role of the inelastic heat losses and heat conduction, while $`f`$ is the effective area fraction of the grains (it can be smaller or greater than unity). The boundary conditions at the base become

$$P(0)=f\text{and}Z(0)=\frac{1+f+(1+6f+f^2)^{1/2}}{2f}.$$
(6)
Using the hydrodynamic formulation, we first determine the condition for a density inversion. At too small inelasticity $`q`$ (the rest of the parameters fixed) there is no density inversion, like in the elastic case $`q=0`$ where $`T(y)=const`$ and $`n(y)`$ goes down monotonically. At large enough $`q`$ the temperature $`T(y)`$ drops rapidly with $`y`$. To maintain the hydrostatic balance, $`n(y)`$ should increase with the height, on an interval of heights between $`y=0`$ and the location of the density maximum $`y=y_c`$. In our hydrodynamic formulation the density inversion occurs, at fixed $`f`$, when $`\mathrm{\Lambda }>\mathrm{\Lambda }_c`$, where $`\mathrm{\Lambda }_c=\mathrm{\Lambda }_c(f)`$ is a critical value. The density inversion is born at $`y=0`$: $`\mathrm{\Lambda }=\mathrm{\Lambda }_c(f)`$ corresponds to $`dn/dy`$ vanishing at $`y=0`$. Using this condition together with Eqs. (4), (5) and (6), we obtain

$$\mathrm{\Phi }(0)=\frac{3}{2}f^{1/2}\frac{F_1[Z(0)]F_2[Z(0)]}{Z(0)}.$$
(7)
For a given $`f`$, Eq. (7) prescribes the heat flux at the base $`y=0`$ that corresponds to the birth of the density inversion. Using shooting, we determine, for every $`f`$, the critical value $`\mathrm{\Lambda }_c(f)`$, demanding that the temperature approaches a constant value at large heights. This procedure yields the critical curve $`\mathrm{\Lambda }=\mathrm{\Lambda }_c(f)`$ shown in Fig. 2.

The density inversion occurs above the critical curve $`\mathrm{\Lambda }=\mathrm{\Lambda }_c(f)`$, and it is more and more pronounced, at fixed $`f`$, as $`\mathrm{\Lambda }`$ grows. Figure 3 (a) shows the density profiles at $`f=0.25`$ and three different values of $`\mathrm{\Lambda }>\mathrm{\Lambda }_c`$. One can see that, at large enough $`\mathrm{\Lambda }`$, a hexagonally-packed cluster appears. The scaled parameters $`\mathrm{\Lambda }=20,015`$ and $`f=0.25`$ correspond to the snapshot shown in Fig. 1. Noticeable is a steep (exponential) density fall at the upper boundary of the cluster; the exponent corresponds to the very low temperature there. Figure 3 (b) shows the scaled temperature for these three cases.

Figure 4 compares the density profiles, predicted by this hydrodynamics (solid curves), with the profiles found in MD simulations with $`N=10^4`$ particles of diameter $`d=1`$, mass $`m=1`$ and $`r=0.98815`$. The (periodic) box width is $`L_x=100`$, the gravity acceleration $`g=1`$. The MD simulations were done for three different values of the temperature at the base: $`T_0=100\sqrt{3},\mathrm{\hspace{0.17em}200}\sqrt{3}`$ and $`300\sqrt{3}`$. The hydrodynamic parameters in these three cases are $`f=0.5`$ and $`\mathrm{\Lambda }=5004`$; $`f=0.25`$ and $`\mathrm{\Lambda }=20015`$, and $`f=0.167`$ and $`\mathrm{\Lambda }=45036`$, respectively. One can see that the agreement between hydrodynamics and MD simulations is surprisingly good.

An additional argument in favor of hydrodynamics follows from the dimensional analysis of the problem. The full set of parameters includes $`d,m,r,g,T_0,N`$ and $`L_x`$. One can always choose $`d=m=g=1`$, so there are actually four independent parameters. This number reduces to three for an $`x`$-independent steady state, as $`N`$ and $`L_x`$ enter the problem only through $`N/L_x`$. It is crucial that hydrodynamics further reduces the number of parameters: now only two scaled parameters $`\mathrm{\Lambda }`$ and $`f`$ appear. This prediction is very robust, as it is independent of the particular form of the functions $`F_1,F_2`$ and $`Q`$ (and of the values of $`\alpha `$ and $`\gamma `$). We verified this prediction in MD simulations by varying $`N,T_0`$ and $`r`$, but keeping $`\mathrm{\Lambda }=20,015`$ and $`f=0.25`$ constant. After rescaling the coordinate $`y`$ by $`\lambda =T_0/(mg)`$, the resulting density profiles almost coincide with each other, see Fig. 5. A small shift between the two profiles, observed in Fig. 5, is apparently caused by small vertical oscillations of the granulate. In this example the oscillation amplitude is about 3 particle diameters oscillations .

As already mentioned, the global CRs completely ignore the issue of coexistence, beyond the freezing point, of different phases of the granulate: the liquid-like phase, the random close-packed phase etc. So why are they so successful? We believe the reason is the following. The vibrofluidized steady state, considered in this work, has a zero mean flow. Therefore, the viscosity terms in the hydrodynamic equations vanish. This fact is not merely a technical simplification. The shear viscosity of granular flow is finite in the liquid-like phase, and infinite in the (multiple) domains of the random close-packed phase. The effective total viscosity of the system is expected to diverge when the coarse-grained density slightly exceeds the freezing density. This invalidates any NSGH for sufficiently dense flows, and necessitates the introduction of an order parameter and a different type of the stress-strain relation into the theory, cf. Ref. Aranson1 . Luckily, these complications do not appear for a zero-mean-flow state. Indeed, the EOS, heat conductivity and inelastic heat loss rate do not exhibit any singularity around the freezing point, and all the way to the hexagonal close packing. Therefore, the NSGH remains reasonably accurate far beyond the freezing point. A future work should address the important question about the range of applicability of the NSGH (actually, of any binary collision model) for solid yet vibrated phase, versus the granular statics approach.

We are grateful to Stefan Luding for comments and for sharing with us his unpublished results on the shear viscosity divergence. We thank Igor Aronson, Detlef Lohse and Arkady Vilenkin for discussions. This research was supported by the Israel Science Foundation (Grant No. 180/02) and by Deutsche Forschungsgemeinschaft (Grant PO 472/6-1).


format: text

text:
# Loss of quantum coherence from discrete quantum gravity

(February 25th 2004)

## Abstract

We show that a recent proposal for the quantization of gravity based on discrete space-time implies a modification of standard quantum mechanics that naturally leads to a loss of coherence in quantum states of the type discussed by Milburn. The proposal overcomes the energy conservation problem of previously proposed decoherence mechanisms stemming from quantum gravity. Mesoscopic quantum systems (as Bose–Einstein condensates) appear as the most promising testing grounds for an experimental verification of the mechanism.

It is commonly believed that a satisfactory theory of quantum gravity may require a drastic modification of our description of space-time. Among the proposed fundamental changes that appear in the literature is that the ultimate theory may imply a discrete structure for space-time at a microscopic level. Recently, a quantization of gravity in discrete space-time has been developed which addresses major fundamental concerns of the canonical program discrete . Among the appealing elements of the proposal is the solution of the problem of time in generally covariant systems through the introduction of relational time in quantum mechanics greece . Having promoted time into the quantum realm it is meaningful to ask how to compare the resulting theory with the traditional Schrödinger picture. We shall show in what follows that in the semiclassical limit, discrete quantum gravity may lead to information loss in quantum states. We will also argue that the process can potentially lead to observable consequences. This construction leads to the same density matrix evolution equation that has been considered by several authors lind ; ghir ; mil ; perc ; adler  in other contexts. It can also be viewed as a concrete implementation of the idea of Penrose penrose  that gravity should play a role in the state reduction process. The equation is given by,

$$\frac{\rho }{t}=i[H,\rho ]𝒟(\rho ),$$
(1)
with $`𝒟(\rho )`$ a decoherence term which has been usually taken as having the modified Lindblad’s formlind ,

$$𝒟(\rho )=\underset{n}{}[D_n,[D_n,\rho ]],D_n=D_n^{},[D_n,H]=0,$$
(2)
so it defines a completely positive map on $`\rho `$, and which is consistent with the monotonous increase of Von Neumann entropy $`S=\mathrm{Tr}(\rho \mathrm{log}\rho )`$ and conservation of energy. This type of equation was introduced by Ghirardi, Rimini and Weber (GRW) ghir  with the aim of providing an objective solution to the measurement problem in standard quantum mechanics. (Similar equations can be used to describe the decoherence due to interaction with an environment, see joos .) GRW considered a single $`D`$ as a localizing operator in coordinate space. As discussed by Adler and Horwitz adler , and also Milburn, Percival and Hughston mil ; perc , setting $`D`$ to be proportional to $`H`$ is most natural since it leads to an objective state vector reduction in the energy pointer basis. This loss of coherence may be a way to avoid macroscopic superpositions, like the “Schrödinger cat” mil ; adler . We shall show that starting from the recent proposal for “consistent discrete quantum gravity” of discrete  one obtains proportionality between $`D`$ and $`H`$. There are other type of constructions where $`𝒟`$ represents collectively quantum gravity effects. In general it does not take the commutator form of equation (2) and it is mainly associated with partial traces over “environmental” degrees of freedom like microscopical black holes or strings haw ; ellis ; banks . As shown by Hawking hawk , these generalized equations may lead to violations of unitarity during black hole evaporation. Hawking’s proposal was criticized on the grounds that it violates energy conservation banks . To find an explicit description of information loss in quantum gravity consistent with energy conservation is one of the major challenges of the field. We will show that the “consistent discrete approach” discrete  ensures energy conservation. Therefore one can conjecture that this description may provide a concrete theoretical solution to the black hole entropy problem based on a quantum description of space-time.

Let us now show how discrete quantum gravity leads to $`DH`$. There have been several attempts to formulate a purely relational description of quantum mechanics relational ; page . The idea is to consider a system that is closed and try to define a notion of time through the evolution of a sub-system of the closed system. This is of interest conceptually in ordinary quantum mechanics, since it frees the description of its reliance on an external classical clock and is unavoidable when one is considering quantum cosmology, where there simply does not exist an external observer. Perhaps the most explicit examples of attempting to present a detailed description at the quantum mechanical level of a purely relational evolution are the series of papers by Page, Wootters and others page . A notion of time is introduced via conditional probabilities, that is, asking what is the probability that a certain quantity has a certain value when another quantity has a given value. The latter could be viewed as a “quantum mechanical clock” introducing a purely quantum mechanical notion of time. The resulting description is an extension of ordinary quantum mechanics that allows to make predictions in regimes where the notion of a classical clock is not applicable. As discussed by Kuchař Kuchar , there are problems with the relational approach, when applied to totally constrained systems like general relativity due to the presence of constraints. The proposed consistent discrete framework for gravity is constraint-free, and therefore we have been able to show that it is possible to introduce a relational description of time avoiding the hard issues that plagued the previous attempts greece .

Let us consider a concrete application of the consistent discrete approach to a Friedmann cosmology coupled to a scalar field. We will denote the latter by $`\varphi `$. Details of a similar model can be seen in cosmo . In a Friedmann cosmology set up as a canonical system, the fundamental variable is the spatial metric, which has only one independent component and its canonically conjugate momentum. It is best to describe the model using Ashtekar variables Ashtekar . In these variables the metric is replaced by a triad, which also has only one independent component in the Friedmann case. We denote it by $`E`$. Its canonically conjugate momentum is denoted by $`A`$. The scalar field and their canonical momenta are $`(\varphi ,P^\varphi )`$. One writes the Einstein action for the model and discretizes the evolution parameter (since the model is homogeneous) as $`\tau =n\mathrm{\Delta }\tau `$. Evolution can be represented at the canonical level via a canonical transformation that implements the discrete equations of motion from the level $`n`$ to level $`n+1`$. One of the equations (the one that would correspond in the discrete theory to the single constraint of the continuum theory) determines the lapse and is solved for it. The resulting theory therefore has no constraints. All its variables are therefore candidates for physical observables and one is therefore ready for the application of the relational time formalism. The quantization of the theory is given in terms of quantum states $`\mathrm{\Psi }(A,P^\varphi ,n)`$. The evolution of the theory is unitary in terms of the $`n`$ variable, since we can represent the canonical transformation as a unitary evolution operator in the quantum theory. We can now use for instance the variable $`A`$ as a time variable and compute the conditional probability that the scalar field momentum have a certain value at a given “time” as (one should really phrase it in terms of intervals since the variables have continuous spectrum)

$`P_{\mathrm{cond}}(P^\varphi =x|A=t)=`$
$`\underset{N\mathrm{}}{lim}{\displaystyle \frac{\underset{n=0}{\overset{N}{}}\mathrm{\Psi }^2[A=t,P^\varphi =x,n]}{_{n=0}^N_{\mathrm{}}^{\mathrm{}}\mathrm{\Psi }^2[A=t,P^\varphi ,n]𝑑P^\varphi }}`$ (3)
In the discrete approach the cosmology appears as a succession of “snapshots” labeled by the integer $`n`$, which lacks any intrinsic meaning. The emergence of time in the model is only through the correlations of the dynamical variables of the theory. The quantum theory that results from the relational probabilities only agrees with ordinary quantum mechanics in regimes in which a notion of classical time is a good approximation to the behavior of a quantum variable greece . It is clear that generically there could be departures from this regime. Let us denote by $`\rho `$ the initial density matrix for the gravity-matter system and assume that in the semiclassical limit we can decouple the system as $`\rho \rho _1\rho _2`$, with $`\rho _1,\rho _2`$, associated to geometry and the field respectively. We sketch a proof that there exists a relational Schrödinger picture where there is an effective density matrix for the “system” which evolves in “internal clock” time into a statistical mixture even if it was in a pure initial state with a resulting evolution equation of the form (1,2) with $`D`$ proportional to $`H`$.

We discuss the derivation for a generic system, to particularize it to the cosmology we mentioned before one chooses one of the variables as clock, for instance $`t=A`$ and $`x=P^\varphi `$. We proceed in two steps. First we introduce the relational Schrödinger picture that our approach follows. We compute the evolution of the density matrix for the “rest” system by summing over all configurations in the variable $`n`$ that are compatible with a certain time $`t`$, $`\rho _2(t)_n𝒫_n(t)U_2(n)\rho _2(0)U_{2}^{}{}_{}{}^{}(n)`$, where $`𝒫_n(t)=\mathrm{Tr}[P_t(0)U_1(n)\rho _1U_1(n)]`$. Where $`U_1(n),U_2(n)`$ are the unitary discrete evolution operators in terms of the discrete parameter $`n`$ for the “time” and “the rest” variables respectively. We also denote as $`P_t(0),P_x(0)`$ the projectors in the $`n=0`$ level into the sub-space corresponding to the values $`t,x`$ of the “time” and the field. We will assume now that there exists a Hamiltonian operator for $`U_2`$ such that $`U_2(n)=\mathrm{exp}(iH_2n)`$. It is important to notice that this evolution differs from the usual Schrödinger picture due to the presence of the sum, which is related to the fact that there is not a unique correspondence between the discrete parameter $`n`$ and a given value of time $`t`$. Therefore the trace of the square of the evolved density matrix will not be one and therefore a pure state evolves into a mixed state. For reasons of space, we do not present the detailed derivation that this evolution equation implies the equations (1,2), but we give the following intuitive explanation. If the probability distribution $`𝒫_n(t)`$ were a Dirac delta (one step $`n`$ is associated uniquely to some time $`t`$) then the density matrix would satisfy equation (1) with $`𝒟=0`$. In practice, the probability distribution will be peaked around some value of $`n`$ with contributions from neighboring values. In the sum this implies that there will be terms representing the evolution from those neighboring values of n. This evolution can be viewed as generated by the action of a Hamiltonian operator. This additional operatorial action is what leads to the double commutator in (2). This can be worked out in detail, we will present the calculation elsewhere.

Let us make, however, some comments. Consider $`t_{max}(n)`$, that is, the value of the maximum probability for the variable $`t`$ as a function of $`n`$. We will assume we chose the temporal variable in such a way that $`t_{max}(n)=\gamma n`$ with $`\gamma `$ a constant of the motion and we will denote by $`\delta \gamma `$ its quantum fluctuations. It is possible to show that $`D=\sqrt{\sigma }H`$ with $`\gamma \sigma =(\delta t_{max})^2/n`$, where $`\delta t_{max}=(\delta \gamma )n`$. What is happening here is that one chose a wavepacket in which $`t`$ was a peaked function of $`n`$ for the clock, but as the system evolves such wavepacket spreads out and $`\sigma `$ will be a measure of that spread. $`\sigma `$ is related to the rate of growth of the spread of the packet.

Equations (1,2) imply that coherence is lost since the off diagonal terms of the density matrix go to zero,

$$\rho _{2}^{}{}_{nm}{}^{}(t)=\rho _{2}^{}{}_{nm}{}^{}(0)e^{i\omega _{nm}t}e^{(\sigma (\omega _{nm})^2)t}$$
(4)
where $`\omega _{mn}=E_mE_n`$ are the Bohr frequencies (for a derivation see Garay , where this formula was obtained by studying a classical non-ideal clock). Notice the loss of coherence implied by the exponential. This can have remarkable effects, for instance if one waits long enough all off-diagonal elements of the density matrix vanish. In spite of this, it is difficult to find experimental situations where these effects are measurable. For instance one may consider light that propagates from distant stars in order to have long times of flight and enhance the effect. However, since most optical measurements imply measuring second (or, more generally, even)-order correlations glauber , this loss of coherence has no visible consequences in optics.

In order to seek for possible experiments, let us first estimate the value of $`\sigma `$, which we expect is going to be a small time scale, of the order of the Planck one. We shall begin by using the whole universe as the quantum clock in order to get some intuition to the bounds for these effects to happen. Since the universe is the biggest reservoir we have it is naturally to believe that it is the best clock we can build. Let us assume that our present universe may be modeled by the Friedmann cosmology we discussed before. As it is shown in discrete  the discrete evolution for the connection $`A`$ goes as $`l_p\mathrm{\Lambda }^{1/2}a(n+k)^{2/3}`$ and $`E=l_{p}^{}{}_{}{}^{2}a^2(n+k)^{4/3}`$, where $`a>0,k`$ are two non-dimensional constants which parameterize the set of equivalent orbits in the continuum limit. Let us now take the relational time as $`t=\mathrm{\Lambda }^{3/4}l_p^{1/2}A^{3/2}`$, such that it has dimension of time, and time is thus measured in cosmological units (we also have $`\mathrm{}=c=1`$). We have $`t=l_pa^{3/2}(n+k)`$ which is of the form $`t=\gamma (n+k)`$, with $`\gamma =l_pa^{3/2}`$, and linearly in $`n`$ as we wanted. On the other hand, due the uncertainty principle for $`E,A`$, i.e. $`\mathrm{\Delta }E\mathrm{\Delta }A>l_{p}^{}{}_{}{}^{2}`$, we have $`a\delta a^2>\frac{1}{l_p\mathrm{\Lambda }^{1/2}(n+k)}`$. From this one can immediately estimate a lower bound for $`\delta \gamma `$ and therefore a lower bound for $`\sigma >l_p/(t\sqrt{\mathrm{\Lambda }})`$. For the present epoch of the universe one therefore has $`\sigma >l_p`$. These estimations for $`\sigma `$ should not be seen as a concrete calculation. In order to refine them we need to construct a more realistic model of the universe including more complexity. See GaPoPu  for a lengthier discussion.

As was first discussed by Ellis et al. ellis  there are several possible phenomenological implications of this non standard quantum behavior. Examples are neutron interferometry and the neutral kaon decay. It is easy to see that our approach implies extremely small corrections to the usual quantum mechanical predictions for these systems. All these models suffer from the same problem, they involve small energy differences between channels so our predictions, though of theoretical interest, are extremely small. This contrasts with the string theory predictions considered in ellis  where the size of the effect is controlled by the external string background and its energy scale is conjectured to be some exponent of the Planck Mass banks .

A system which has been considered in connection with Milburn’s mil  type of decoherence is a two level atom interacting with the electromagnetic field in a cavity subir . We follow closely the analysis of reference subir . The system is described by the Hamiltonian $`H=H_a+H_f+H_i`$ where $`H_a=\frac{\omega }{2}R_3`$ describes the energy splitting of the two level atom. $`H_f=\omega a^{}a`$ is the traditional number operator for the $`\omega `$-mode of the field inside the cavity, and $`H_i=\lambda (R^+a+a^{}R^{})`$ with $`\lambda ^2\mu ^2\omega `$, the dipole coupling constant. Here $`\mu `$ is the dipole matrix element between both levels of the atom. The operators $`R_3,R^\pm `$ are essentially the traditional angular momentum operators and $`(R_3)^2=1`$. Notice that this model could be used to describe any two level system coupled to a mode of a field which induces transitions. Indeed the population of the upper level is given by $`1/2(1+<R_3>)`$. It is easy to see now that within our approach the atomic inversion evolves as,

$$<R_3>_\sigma =\underset{s}{}|Q_s(0)|^2e^{\left(2(s+1)\sigma \lambda ^2t\right)}\mathrm{cos}(2\sqrt{s+1}\lambda t)$$
(5)
where $`Q_se^{|\alpha |^2/2}\frac{\alpha ^s}{\sqrt{s!}}`$. We have considered initially the field in a coherent state $`|\alpha >`$ ($`\overline{n}=|\alpha |^2`$), and the atom in its excited state. This system was first analyzed by Moya et al. moya  who studied the same model within Milburn’s proposalmil  which is dynamically identical to our approach plus the identification $`\sigma \theta _0`$. The physical conclusions are that coherence is destroyed and “revivals” in the coherence are exponentially suppressed. The loss of coherence is likely to act slower than the decoherence due to ambiental factors and therefore one expects that actual experiments will be dominated by the ambient decoherence. In fact, modeling the latter by the introduction of a damping constant $`\gamma `$ and Langevin noise leads to a solution for the atomic inversion in the under-damping limit $`\gamma <<\lambda `$, of the form subir ,

$`<R_3>_\gamma ={\displaystyle \frac{12\overline{n}}{1+2\overline{n}}}\left(e^{\gamma \frac{1+2\overline{n}}{1+\overline{n}}t}1\right)+`$
$`{\displaystyle \underset{s}{}}|Q_s(0)|^2e^{\gamma t}cos(2\sqrt{s+1}\lambda t)`$ (6)
Notice that both effects are similar but leave a different imprint since the exponential decay does not depends on the number of photons $`n`$ in the ambient decoherence while it does in the one due to loss of coherence. In order for the effect to be visible one would need a high intensity laser, which would face limitations since high intensities will increase the ambient decoherence of the cavity. It should be noticed that the relative importance of the loss of coherence can be enhanced through the increase of the dipole coupling of the field with the two level atom $`\mu `$. Therefore an optimal experiment should have intense fields, strong coupling of the atom to the field and widely separated energy levels in the atom. At present this appears beyond the state of the experimental art with these types of experiment.

Since the effect depends on the number of photons, this suggests that systems involving mesoscopic quantum states should be well suited for experimentally probing the effect. An example of such systems could be the Bose-Einstein condensation (BEC). Recently Greiner at al nature  studied the “collapse and revival” of matter wave fields in BEC. They showed that the macroscopical wave function undergoes a series of “collapses and revivals” due the collisions of cold atoms confined to a potential well. We will not repeat the calculation explicitly here for this model for reasons of space, but we have found an effect very similar to that of equation (5) for this system. The main difference is that in the exponent the number of atoms enters quadratically, as opposed to (5) where the number of photons entered linearly. Although the currently considered experiments with BEC involve very few atoms, and again one is very far away from seeing quantum gravitational effects, it is possible that future experiments with more atoms, giving the quadratic dependence on the number could be more promising. To our knowledge these detection of revivals will, in the future, provide the most stringent bounds on quantum gravity inspired decoherence known up to now. In general experiments that test “Schrödinger cat” type situations can all potentially lead to observations of the decoherence we found. For a recent review see Leggett . SQUID experiments seem to provide the best bound up to date Ellis ; Joychristian .

Summarizing, we have shown that a recently introduced proposal for quantizing gravity on discrete space-time leads naturally to a quantum mechanics that includes a fundamental decoherence of the Milburn type. Contrary to Hawking’s information loss proposal, ours does not violate energy conservation. Future experimental developments in quantum mesoscopic systems can lead to a confirmation of the process.

We wish to thank Peter Knight for correspondence. This work was supported by grant NSF-PHY0244335 and funds from the Horace Hearne Jr. Institute for Theoretical Physics.


text:
# Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range

## 1 Introduction

Quantum computing provides speedups for many search problems. The most famous example is Grover’s algorithm , which computes OR of $`N`$ variables with $`O(\sqrt{N})`$ queries. Other examples include counting , estimating mean and median , finding collisions , determining element distinctness , finding triangles in a graph  and verifying matrix products . For many of these problems, we can also prove that known quantum algorithms are optimal or nearly optimal.

In at least two cases, the lower bounds match the best known algorithm only with an additional “large range” assumption. For example, consider the collision problem  which models collision-free hash functions. We have to distinguish if a function $`f:\{1,\mathrm{},N\}\{1,\mathrm{},M\}`$ is one-to-one or two-to-one. A quantum algorithm can solve the problem with $`O(N^{1/3})`$ queries (evaluations of $`f`$) , which is better than the $`\mathrm{\Theta }(N^{1/2})`$ queries required classically. A lower bound by Aaronson and Shi  says that $`\mathrm{\Omega }(N^{1/3})`$ quantum queries are required if $`M3N/2`$. If $`M=N`$, the lower bound becomes $`\mathrm{\Omega }(N^{1/4})`$.

A similar problem exists for element distinctness. (Again, we are given $`f:\{1,\mathrm{},N\}\{1,\mathrm{},M\}`$ but $`f`$ can be arbitrary and we have to determine if there are $`i,j`$, $`ij`$, $`f(i)=f(j)`$.) If $`M=\mathrm{\Omega }(N^2)`$, the lower bound is $`\mathrm{\Omega }(N^{2/3})`$ , which matches the best algorithm . But, if $`M=N`$, the lower bound is only $`\mathrm{\Omega }(\sqrt{N})`$ or $`\mathrm{\Omega }(\sqrt{N\mathrm{log}N})`$, depending on the model .

Thus, it might be possible that a quantum algorithm could use the small $`M`$ to decrease the number of queries. While unlikely, this cannot be ruled out. Remember that classically, sorting requires $`\mathrm{\Omega }(N\mathrm{log}_2N)`$ steps in the general case but only $`O(N)`$ steps if the items to be sorted are all from the set $`\{1,\mathrm{},N\}`$ (Bucket Sort, ).

In this paper, we show that the collision and element distinctness problems require $`\mathrm{\Omega }(N^{2/3})`$ and $`\mathrm{\Omega }(N^{1/3})`$ queries even if the range $`M`$ is equal to $`N`$. Our result follows from a general result on the polynomial degree of Boolean functions.

We show that, for any symmetric property $`\varphi `$ of functions $`f:\{1,2,\mathrm{},N\}\{1,2,\mathrm{},M\}`$, its polynomial degree is the same for all $`MN`$. The polynomial degree of $`\varphi `$ provides a lower bound for both classical and quantum query complexity. (This was first shown by Nisan and Szegedy  in the classical case and then extended to the quantum case by Beals et al.  for $`M=2`$ and Aaronson  for $`M>2`$.) Thus, one can prove lower bounds on quantum query complexity of a function $`\varphi `$ by lower-bounding the polynomial degree of $`\varphi `$. This is known as the polynomials method for proving quantum lower bounds .

Our result means that, if we have a quantum lower bound for a symmetric property $`\varphi `$ shown by the polynomials method for some range size $`M`$, we also have the same quantum lower bound for all $`MN`$. As particular cases, we get lower bounds on the collision and element distinctness problems with small range. Since many quantum lower bounds are shown using the polynomial degree method, our result may have other applications.

A corollary of our lower bound on element distinctness with small range is that the polynomial degree of the two level AND–OR tree on $`N^2`$ variables is $`\mathrm{\Omega }(N^{2/3})`$. This improves over the previously known lower bound of $`\mathrm{\Omega }(\sqrt{N\mathrm{log}N})`$ by Shi .

Related work. The $`\mathrm{\Omega }(N^{1/3})`$ lower bound for the collision problem with small range was independently discovered by the author of this paper and Kutin , at about the same time, with completely different proofs. Kutin  takes the proof of $`\mathrm{\Omega }(N^{1/3})`$ lower bound for the collision problem with a large range  and changes it so that it works for all $`MN`$. Our result is more general because it applies to any symmetric property and any lower bound shown by the polynomials method. On the other hand, Kutin’s proof has the advantage that it also simplifies the lower bound for the collision problem with large range by Aaronson and Shi .

## 2 Preliminaries

### 2.1 Quantum query model

Let $`[k]`$ denote the set $`\{1,\mathrm{},k\}`$. Let $`f`$ be a function from $`[N]`$ to $`[M]`$. Let $`(N,M)`$ be the set of all $`f:[N][M]`$. We are given a function $`f(N,M)`$ by an oracle that answers queries. In one query, we can give $`i`$ to the oracle and it returns $`f(i)`$ to us.

We would like to know whether $`f`$ has a certain property (for example, whether $`f`$ is one-to-one). More formally, we would like to compute a partial function $`\varphi :^{}\{0,1\}`$, where $`^{}(N,M)`$. In particular, we are interested in the following two properties:

Problem 1: Collision. $`\varphi (f)=1`$ if the input function $`f`$ is one-to-one. $`\varphi (f)=0`$ if $`f`$ is two-to-one (i.e., if, for every $`k[M]`$, there are either zero or two $`x[N]`$ satisfying $`f(x)=k`$). $`\varphi (f)`$ is undefined for all other $`f`$.

Problem 2: Element distinctness. $`\varphi (f)=1`$ if the input function $`f`$ is one-to-one. $`\varphi (f)=0`$ if there exist $`i,j`$, $`ij`$, $`f(i)=f(j)`$.

A quantum algorithm with $`T`$ queries is just a sequence of unitary transformations

$$U_0O_fU_1O_f\mathrm{}U_{T1}O_fU_T.$$

The $`U_j`$’s can be arbitrary unitary transformations that do not depend on $`f(1),\mathrm{},f(N)`$. $`O`$ is a query (oracle) transformation. To define $`O_f`$, we represent basis states as $`|i,b,z`$ where $`i`$ consists of $`\mathrm{log}N`$ bits, $`b`$ is $`\mathrm{log}M`$ bits and $`z`$ consists of all other bits. Then, $`O_f`$ maps $`|i,b,z`$ to $`|i,(b+f(i))modM,z`$.

The computation starts with a state $`|0`$. Then, we apply $`U_0`$, $`O_f`$, $`\mathrm{}`$, $`O_f`$, $`U_T`$ and measure the final state. The result of the computation is the rightmost bit of the state obtained by the measurement.

The quantum algorithm computes $`\varphi `$ with error $`ϵ`$ if, for every $`f`$ such that $`\varphi (f)`$ is defined, the probability that the rightmost bit of $`U_TO_fU_{T1}\mathrm{}O_fU_0|0`$ equals $`\varphi (f)`$ is at least $`1ϵ`$. (Throughout this paper, $`ϵ`$ is an arbitrary but fixed value, with $`0<ϵ<1/2`$.)

### 2.2 Polynomial lower bound

We can describe a function $`f:[N][M]`$ by $`N\times M`$ Boolean variables $`y_{ij}`$ which are 1 if $`f(i)=j`$ and 0 otherwise. Let $`y=(y_{11},\mathrm{},y_{NM})`$.

###### Definition 1

We say that a polynomial $`P`$ $`ϵ`$-approximates the property $`\varphi `$ if

1. $`\varphi (f)=1`$ implies $`1ϵP(y)1`$ for $`y=(y_{11},\mathrm{},y_{NM})`$ corresponding to $`f`$;
2. $`\varphi (f)=0`$ implies $`0P(y)ϵ`$ for $`y=(y_{11},\mathrm{},y_{NM})`$ corresponding to $`f`$;
3. If $`\varphi (f)`$ is undefined, then $`0P(y)1`$ for the corresponding $`y`$.

A polynomial $`P`$ approximates $`f`$ if it $`ϵ`$-approximates $`f`$ for some fixed $`ϵ<1/2`$

$`P`$ is allowed to take any value if $`y`$ does not correspond to any $`f`$. (This happens if for some $`i[N]`$ there is no or there is more than one $`j[M]`$ with $`y_{ij}=1`$.)

###### Lemma 1

 If a quantum algorithm computes $`\varphi `$ with error $`ϵ`$ using $`T`$ queries then there is a polynomial $`P(y_{11},\mathrm{},y_{NM})`$ of degree at most $`2T`$ that $`ϵ`$-approximates $`\varphi `$.

A lower bound on the number of queries can be then shown by proving that such a polynomial $`P`$ does not exist. For the collision and element distinctness problems, we have

###### Theorem 1

 111More precisely, Shi  proved that any polynomial approximating another problem, the half two-to-one problem, has degree $`\mathrm{\Omega }(N^{1/3})`$. He then used that to deduce that $`\mathrm{\Omega }(N^{1/3})`$ and $`\mathrm{\Omega }(N^{2/3})`$ quantum queries are needed for the collision problem (when $`M\frac{3N}{2}`$) and the element distinctness problem (when $`M=\mathrm{\Omega }(N^2)`$). His proof can be easily modified to show a lower bound on the degree of polynomials approximating the collision and element distinctness problems.

1. If a polynomial $`P`$ approximates the collision property for $`M\frac{3N}{2}`$, the degree of $`P`$ is $`\mathrm{\Omega }(N^{1/3})`$;
2. If a polynomial $`P`$ approximates the element distinctness property for $`M=\mathrm{\Omega }(N^2)`$, the degree of $`P`$ is $`\mathrm{\Omega }(N^{2/3})`$;

Therefore, $`\mathrm{\Omega }(N^{1/3})`$ and $`\mathrm{\Omega }(N^{2/3})`$ queries are required to solve the collision problem and element distinctness problem if the range $`M`$ is sufficiently large. Previously, only weaker lower bounds of $`\mathrm{\Omega }(N^{1/4})`$  and $`\mathrm{\Omega }(\sqrt{N\mathrm{log}N})`$  were known if $`M=N`$.

## 3 Results

We call a property $`\varphi `$ symmetric if, for any $`\pi S_N`$ and $`\sigma S_M`$,

$$\varphi (f)=\varphi (\sigma f\pi ).$$

That is, $`\varphi (f)`$ should remain the same if we permute the input set $`\{1,\mathrm{},N\}`$ before applying $`f`$ or permute the output set $`\{1,\mathrm{},M\}`$ after applying $`f`$. The collision and element distinctness properties are both symmetric.

Our main result is

###### Theorem 2

Let $`\varphi :^{}\{0,1\}`$, $`^{}(N,M)`$ be symmetric. Let $`\varphi ^{}`$ be the restriction of $`\varphi `$ to $`f:[N][N]`$. Then, the minimum degree of a polynomial (in $`y_{ij}`$, $`i[N]`$, $`j[M]`$) approximating $`\varphi `$ is equal to the minimum degree of a polynomial (in $`y_{ij}`$, $`i[N]`$, $`j[N]`$) approximating $`\varphi ^{}`$.

Theorems 1 and 2 imply that $`\mathrm{\Omega }(N^{1/3})`$ and $`\mathrm{\Omega }(N^{2/3})`$ queries are needed to solve the collision and element distinctness problems, even if $`M=N`$. (For $`M<N`$, these problems do not make sense because they both involve $`f`$ being one-to-one as one of the cases.)

The proof of Theorem 2 is in two steps.

1. We describe a different way to describe an input function $`f`$ by variables $`z_1`$, $`\mathrm{}`$, $`z_M`$ instead of $`y_{11},\mathrm{},y_{NM}`$. We prove that a polynomial of degree $`k`$ in $`z_1`$, $`\mathrm{}`$, $`z_M`$ exists if and only if a polynomial of degree $`k`$ in $`y_{11}`$, $`\mathrm{}`$, $`y_{NM}`$ exists.
2. We show that a polynomial $`Q(z_1,\mathrm{},z_M)`$ for $`M>N`$ exists if and only $`Q(z_1,\mathrm{},z_N)`$ exists.

The first step can be useful on its own. The representation of $`f`$ by $`y_{11}`$, $`\mathrm{}`$, $`y_{NM}`$ gave the lower bounds of . The new representation by $`z_1`$, $`\mathrm{}`$, $`z_N`$ might yield new lower bounds that are easier to prove using this approach.

### 3.1 New polynomial representation

We introduce variables $`z_1`$, $`\mathrm{}`$, $`z_M`$, with $`z_j=|f^1(j)|`$ (equivalently, $`z_j=|\{i:y_{ij}=1\}|`$). We say that a polynomial $`Q`$ in $`z_1,\mathrm{},z_M`$ approximates $`\varphi `$ if it satisfies requirements similar to Definition 1. ($`Q[1ϵ,1]`$ if $`\varphi (f)=1`$, $`Q[0,ϵ]`$ if $`\varphi (f)=0`$, and $`Q[0,1]`$ if $`z_1,\mathrm{},z_M`$ correspond to $`f(N,M)`$ for which $`\varphi (f)`$ is not defined.)

Example 1: A polynomial $`Q(z_1,\mathrm{},z_M)`$ approximates the collision property if:

1. $`Q(z_1,\mathrm{},z_M)[1ϵ,1]`$ if $`N`$ of the variables $`z_1`$, $`\mathrm{}`$, $`z_M`$ are 1 and the remaining $`MN`$ variables are 0;
2. $`Q(z_1,\mathrm{},z_M)[0,ϵ]`$ if $`\frac{N}{2}`$ of the variables $`z_1`$, $`\mathrm{}`$, $`z_M`$ are 2 and the remaining $`M\frac{N}{2}`$ variables are 0;
3. $`Q(z_1,\mathrm{},z_M)[0,1]`$ if $`z_1,\mathrm{},z_M`$ are non-negative integers and $`z_1+\mathrm{}+z_M=N`$.

Example 2: A polynomial $`Q(z_1,\mathrm{},z_M)`$ approximates element distinctness if:

1. $`Q(z_1,\mathrm{},z_M)[1ϵ,1]`$ if $`N`$ of the variables $`z_1`$, $`\mathrm{}`$, $`z_M`$ are 1 and the remaining $`MN`$ variables are 0;
2. $`Q(z_1,\mathrm{},z_M)[0,ϵ]`$ if $`z_1,\mathrm{},z_M`$ are non-negative integers, $`z_1+\mathrm{}+z_M=N`$, and $`z_i>1`$ for some $`i`$.

In both cases, there is no restriction on $`Q(z_1,\mathrm{},z_M)`$ when $`z_1+\mathrm{}+z_MN`$ because such $`z_1`$, $`\mathrm{}`$, $`z_M`$ do not correspond to any $`f:[N][M]`$.

###### Lemma 2

Let $`\varphi :^{}\{0,1\}`$, $`^{}(N,M)`$ be symmetric. Then, the following two statements are equivalent:

1. There exists a polynomial $`Q`$ of degree at most $`k`$ in $`z_1,\mathrm{},z_M`$ approximating $`\varphi `$;
2. There exists a polynomial $`P`$ of degree at most $`k`$ in $`y_{11}`$, $`\mathrm{}`$, $`y_{NM}`$ approximating $`\varphi `$.

Proof: To see that (1) implies (2), we substitute $`z_j=y_{1j}+y_{2j}+\mathrm{}+y_{Nj}`$ into $`Q`$ and obtain a polynomial in $`y_{ij}`$ with the same approximation properties. Next, we show that (2) implies (1).

Let $`P(y_{11},\mathrm{},y_{NM})`$ be a polynomial approximating $`\varphi `$. We define $`Q(z_1,\mathrm{},z_M)`$ as follows. Let $`S`$ be the set of all $`y=(y_{11},\mathrm{},y_{NM})`$ corresponding to functions $`f:[N][M]`$ with the property that, for every $`i[M]`$ the number of $`j`$ with $`f(j)=i`$ is exactly $`z_i`$. We define $`Q(z_1,\mathrm{},z_M)`$ as the expectation of of $`P(y_{11},\mathrm{},y_{NM})`$ when $`y=(y_{11},\mathrm{},y_{NM})`$ is picked uniformly at random from $`S`$. (An equivalent way to define $`Q`$ is to fix one function $`f`$ with this property and to define $`Q`$ as the expectation of of $`P(y_{11},\mathrm{},y_{NM})`$, for $`y=(y_{11},\mathrm{},y_{NM})`$ corresponding to the function $`f\pi `$, with $`\pi `$ being a random element of $`S_N`$.)

Since $`\varphi `$ is symmetric, we have $`\varphi (f)=\varphi (f\pi )`$. Therefore, if $`P(y_{11},\mathrm{},y_{NM})`$ approximates $`\varphi `$, then $`Q(z_1,\mathrm{},z_M)`$ also approximates $`\varphi `$.

It remains to prove that $`Q`$ is a polynomial of degree at most $`k`$ in $`z_1,\mathrm{},z_M`$. Let

$$I=y_{i_1j_1}y_{i_2j_2}\mathrm{}y_{i_kj_k}$$

be a monomial of $`P`$. It suffices to prove that each $`E[I]`$ is a polynomial of degree at most $`k`$ because $`E[P]`$ is the sum of $`E[I]`$ over all $`I`$.

We can assume that $`i_l`$ for $`l\{1,\mathrm{},k\}`$ are all distinct. (If the monomial $`I`$ contains two variables $`y_{ij}`$ with the same $`i`$, $`j`$, one of them is redundant because $`y_{ij}^2=y_{ij}`$. If $`I`$ contains $`y_{ij}`$, $`y_{ij^{}}`$, $`jj^{}`$, then $`y_{ij}y_{ij^{}}=0`$ because $`f(i)`$ cannot be equal $`j`$ and $`j^{}`$ at the same time. Then, $`I=0`$.) We have

$$E[I]=Pr[y_{i_1j_1}=1]\underset{l=2}{\overset{k}{}}Pr[y_{i_lj_l}=1|y_{i_1j_1}\mathrm{}y_{i_{l1}j_{l1}}=1].$$

There are $`N`$ variables $`y_{ij_1}`$. Out of them, $`z_{j_1}`$ variables are equal to 1 and each $`y_{ij_1}`$ is equally likely to be 1. Therefore,

$$Pr[y_{i_1j_1}=1]=\frac{z_{j_1}}{N}$$

Furthermore, let $`s_l`$ be the number of $`l^{}<l`$ such that $`j_l=j_l^{}`$. Then,

$$Pr[y_{i_lj_l}=1|y_{i_1j_1}\mathrm{}y_{i_{l1}j_{l1}}=1]=\frac{z_{j_l}s_l}{Nl1}$$

because, once we have set $`y_{i_1j_1}=1`$, $`\mathrm{}`$, $`y_{i_{l1}j_{l1}}=1`$, we have also set all other $`y_{i_1j}`$, $`\mathrm{}`$, $`y_{i_{l1}j}`$ to 0. Then, we have $`Nl1`$ variables $`y_{ij_l}`$ which are not set yet and, out of them, $`z_{j_l}s_l`$ must be 1.

Therefore, $`E[I]`$ is a product of $`k`$ terms, each of which is a linear function of $`z_1,\mathrm{},z_M`$. This means that $`E[I]`$ is a polynomial in $`z_1,\mathrm{},z_M`$ of degree $`k`$. This completes the proof of the lemma. $`\mathrm{}`$

### 3.2 Lower bound for properties with small range

We now finish the proof of Theorem 2. Obviously, the minimum degree of a polynomial approximating $`\varphi ^{}`$ is at most the minimum degree of a polynomial approximating $`\varphi `$ (because we can take a polynomial approximating $`\varphi `$ and obtain a polynomial approximating $`\varphi ^{}`$ by restricting it to variables $`y_{ij}`$, $`j[N]`$). In the other direction, we can take a polynomial $`P^{}`$ approximating $`\varphi ^{}`$ and obtain a polynomial $`Q^{}`$ in $`z_1,\mathrm{},z_N`$ approximating $`\varphi ^{}`$ by Lemma 2. We then construct a polynomial $`Q`$ in $`z_1,\mathrm{},z_M`$ of the same degree approximating $`\varphi `$. After that, using Lemma 2 in the other direction gives us a polynomial $`P`$ in $`y_{11},\mathrm{},y_{NM}`$ approximating $`\varphi `$.

It remains to construct $`Q`$ from $`Q^{}`$. For that, we can assume that $`Q^{}`$ is symmetric w.r.t. permuting $`z_1,\mathrm{},z_N`$. (Otherwise, replace $`Q^{}`$ by the expectation of $`Q^{}(z_{\pi (1)},\mathrm{},z_{\pi (N)})`$, where $`\pi `$ is a uniformly random permutation of $`\{1,2,\mathrm{},N\}`$.) Since $`Q^{}`$ is symmetric, it is a sum of elementary symmetric polynomials

$$Q_{c_1,\mathrm{},c_l}^{}=\underset{i_1,\mathrm{},i_l[N]}{}z_{i_1}^{c_1}z_{i_2}^{c_2}\mathrm{}z_{i_l}^{c_l}.$$

Let $`Q`$ be the sum of elementary symmetric polynomials in $`z_1,\mathrm{},z_M`$ with the same coefficients.

We claim that $`Q`$ approximates $`\varphi `$. To see this, consider an input function $`f:[N][M]`$. There are at most $`N`$ values $`j\{1,\mathrm{},M\}`$ such that there exists $`i\{1,\mathrm{},N\}`$ with $`f(i)=j`$. This means that, out of $`M`$ variables $`z_1,\mathrm{},z_M`$ corresponding to $`f`$, at most $`N`$ are nonzero.

Consider a permutation $`\pi S_M`$ that maps all $`i[M]`$ with $`z_i0`$ to $`\{1,\mathrm{},N\}`$. Let $`f^{}=\pi f`$. Since $`\varphi `$ is symmetric, $`\varphi (f)=\varphi (f^{})`$. Since $`f^{}`$ is a function from $`[N]`$ to $`[N]`$, $`Q^{}`$ correctly approximates $`\varphi `$ on $`f^{}`$. Since $`Q(z_1,\mathrm{},z_N,0,\mathrm{},0)=Q^{}(z_1,\mathrm{},z_N)`$, $`Q`$ also correctly approximates $`\varphi `$ on $`f^{}`$. Since $`Q`$ is symmetric w.r.t. permutations of $`z_1,\mathrm{},z_M`$, $`Q`$ approximates $`\varphi `$ on the input function $`f`$ as well. This completes the proof of Theorem 2.

### 3.3 Lower bound on the polynomial degree of the AND–OR tree

As a by-product, our result provides a better lower bound on the polynomial degree of a well-studied Boolean function.

This Boolean function is the two level AND–OR tree on $`N^2`$ variables. Let $`x_1,\mathrm{},x_{N^2}\{0,1\}`$ be the variables. We split them into $`N`$ groups, with the $`i^{\mathrm{th}}`$ group consisting of $`x_{(i1)N+1}`$, $`x_{(i1)N+2}`$, $`\mathrm{}`$, $`x_{iN}`$. The AND–OR function $`g(x_1,\mathrm{},x_{N^2})`$ is defined as

$$g(x_1,\mathrm{},x_{N^2})=\underset{i=1}{\overset{n}{}}\underset{j=(i1)N+1}{\overset{iN}{}}x_j.$$

A polynomial $`p(x_1,\mathrm{},x_{N^2})`$ approximates $`g`$ if $`0p(x_1,\mathrm{},x_{N^2})ϵ`$ whenever $`g(x_1,\mathrm{},x_{N^2})=0`$ and $`1ϵp(x_1,\mathrm{},x_{N^2})1`$ whenever $`g(x_1,\mathrm{},x_{N^2})=1`$ (similarly to Definition 1).

It has been an open problem to determine the minimum degree of a polynomial approximating the two-level AND–OR tree. The best lower bound is $`\mathrm{\Omega }(\sqrt{N\mathrm{log}N})`$ by Shi , while the best upper bound is $`O(N)`$. (Curiously, the quantum query complexity of this problem is known. It is $`\mathrm{\Theta }(N)`$, as shown by . If the polynomial degree is $`o(N)`$, this would be the second example of a Boolean function with a gap between the polynomial degree and quantum query complexity, with the first example being the iterated functions in .) We show

###### Theorem 3

Any polynomial approximating $`g`$ has degree $`\mathrm{\Omega }(N^{2/3})`$.

Proof: Consider the element distinctness problem for $`M=N`$. An instance of this problem, $`f(N,N)`$ can be described by $`N^2`$ variables $`y_{11},\mathrm{},y_{NN}`$ (as shown in Section 2.2).

The values of the function, $`f(1)`$, $`f(2)`$, $`\mathrm{}`$, $`f(N)`$, are all distinct if and only if, for each $`j[N]`$, there exists $`i[N]`$ with $`f(i)=j`$. This, in turn, is equivalent to saying that, for each $`i[N]`$, one of the variables $`y_{1i},y_{2i},\mathrm{},y_{Ni}`$ is equal to 1.

Assume we have a polynomial $`P(x_1,\mathrm{},x_{N^2})`$ of degree $`d`$ approximating the two level AND–OR tree function $`g`$. Consider the polynomial $`Q(y_{11},\mathrm{},y_{NN})`$ obtained from $`P`$ by replacing $`x_{(i1)N+j}`$ with $`y_{ji}`$. If the $`N`$ values $`f(i)`$ are all distinct, then, for each $`j\{1,\mathrm{},N\}`$, there exists $`i`$ such that $`f(i)=j`$. Therefore, one of the variables $`y_{1j},\mathrm{},y_{Nj}`$ is 1 and the OR of those variables is also 1. This means that the AND–OR function $`g(x_1,\mathrm{},x_{N^2})`$ is equal to 1. If the values $`f(i)`$ are not all distinct, then there exists $`j[N]`$ such that there is no $`i`$ with $`f(i)=j`$. Then, $`y_{1i},y_{2i},\mathrm{},y_{Ni}`$ are all 0, implying that $`g(x_1,\mathrm{},x_{N^2})=0`$ for the corresponding assignment $`x_1`$, $`\mathrm{}`$, $`x_{N^2}`$.

This means that $`Q`$ approximates the element distinctness property, in the sense of section 2.2. Since degree $`\mathrm{\Omega }(N^{2/3})`$ is required to approximate element distinctness, $`d=\mathrm{\Omega }(N^{2/3})`$. $`\mathrm{}`$

## 4 Conclusion

We have shown that, for any symmetric property of functions $`f:[N][M]`$, its polynomial degree is the same for all $`MN`$. Thus, if we prove a lower bound for the degree for some large $`M`$, this immediately implies the same bound for $`M=N`$. Since the polynomial degree is a lower bound for quantum query complexity, this can be used to show quantum lower bounds. As particular cases of our result, we get that the collision problem has degree $`\mathrm{\Omega }(N^{1/3})`$ and that the element distinctness problem has degree $`\mathrm{\Omega }(N^{2/3})`$, even if $`M=N`$. This implies $`\mathrm{\Omega }(N^{1/3})`$ and $`\mathrm{\Omega }(N^{2/3})`$ quantum lower bounds on these problems for $`M=N`$.

A part of our result is a new representation for polynomials describing properties of functions $`f:[N][M]`$. This new description might be useful for proving new quantum lower bounds. We conclude with two open problems.

1. Modified element distinctness problem. Say we are given $`f:[N][N]`$ and we are promised that either $`f`$ is one-to-one or there are $`i,j,k`$ such that $`f(i)=f(j)=f(k)`$. We would like to know which of these two is the case. What is the quantum query complexity of this problem?

The problem is quite similar to element distinctness in which we have to distinguish one-to-one function from one having $`f(i)=f(j)`$ for some $`i,j`$ with $`ij`$. The known $`O(N^{2/3})`$ quantum algorithm still applies, but the $`\mathrm{\Omega }(N^{2/3})`$ quantum lower bound of  (by a reduction from the collision problem) breaks down. The best lower bound that we can prove is $`\mathrm{\Omega }(N^{1/2})`$ by a reduction from Grover’s search. Improving this bound to $`\mathrm{\Omega }(N^{2/3})`$ is an open problem.

This problem is also similar to element distinctness if we look at it in our new $`z_1`$, $`\mathrm{}`$, $`z_M`$ representation. For element distinctness, a polynomial $`Q`$ must satisfy $`Q(1,\mathrm{},1)[1ϵ,1]`$ and $`Q(z_1,\mathrm{},z_N)[0,ϵ]`$ if $`z_1+\mathrm{}+z_N=N`$ and $`z_i2`$ for some $`i`$. For our new problem, we must have $`Q(1,\mathrm{},1)[1ϵ,1]`$ and $`Q(z_1,\mathrm{},z_N)[0,ϵ]`$ if $`z_1+\mathrm{}+z_N=N`$ and $`z_i3`$ for some $`i`$. In the first case, degree $`\mathrm{\Omega }(N^{2/3})`$ is needed . In the second case, no such lower bound is known.
2. Polynomial degree vs. quantum query complexity for symmetric properties. Let $`\varphi `$ be a symmetric property of functions $`f:[N][M]`$. Let $`\mathrm{deg}(\varphi )`$ be the minimum degree of a polynomial that $`ϵ`$-approximates $`f`$ and $`Q_2(\varphi )`$ be the minimum number of queries in a quantum query algorithm computing $`\varphi `$ with error at most $`ϵ`$. Is it true that these two quantities are polynomially related: $`Q_2(\varphi )=O(\mathrm{deg}^c(\varphi ))`$ for some constant $`c`$?

This open problem was first proposed by Aaronson , regarding properties which are only symmetric with respect to permuting inputs to $`f`$: $`\varphi (f)=\varphi (f\pi )`$ for any $`\pi S_N`$. It remains open both in this case and in the case of properties having the more general symmetry considered in this paper ($`\varphi (f)=\varphi (\sigma f\pi )`$, for all $`\pi S_N`$ and $`\sigma S_M`$). It is known that $`Q_2(\varphi )=O(\mathrm{deg}^2(\varphi ))`$ if $`M=2`$.


text:
# Giant Goos-Hänchen effect at the reflection from left-handed metamaterials

## Abstract

We study the beam reflection from a layered structure with a left-handed metamaterial. We predict a giant lateral (Goos-Hänchen) shift and splitting of the beam due to the resonant excitation of surface polaritons with a vortex-like energy flow between the right- and left-handed materials.

As is known, a totally reflected beam experiences a lateral displacement from its position predicted by the geometric optics because each of its plane-wave components undergoes a different phase change Goos:1947-333:AP . For the beam reflected from an interface, the lateral beam shift (the so-called Goos-Hänchen effect) is usually much less than the beam width. However, larger beam shifts may occur in the layered systems supporting surface waves, which are able to transfer energy along the interface. Such surface waves are not excited at a single interface because the phase-matching condition between the incident and surface waves are not satisfied. However, a surface polariton can be excited in a layered structure, when the beam is incident at the angle larger than the angle of the total internal reflection. Excitations of polaritons take place in two well known geometries of the attenuated beam reflection (used e.g. for the measurements of the dielectric permittivity of solids): (i) glass prism-air-silver structure (the so-called Otto configuration) and (ii) prism-silver film-air structure (the so-called Kretchmann configuration) (see, e.g., Ref. Chuang:1986-593:JOSA  and references therein).

The extensive study of novel microstructured materials with negative refraction recently fabricated experimentally shelby , the so-called left-handed metamaterials, demonstrates that an interface between right- and left-handed material supports surface polaritons of TE and TM types Ruppin:2000-61:PLA ; Shadrivov:unpub , which can enhance dramatically the Goos-Hänchen effect because surface waves can transfer the energy along the interface. In this Letter, we predict and analize the giant Goos-Hänchen effect in the structure (i) (the Otto configuration), where the third medium is substituted by a left-handed metamaterial.

We consider a two-dimensional geometry shown in Fig. 1(a), where the beam, incident from an optically dense medium ($`ϵ_1\mu _1>ϵ_2\mu _2`$) at the angle larger than the angle of the total internal reflection, is reflected from the interface. We assume that the third medium is separated by a gap (which we call the second medium), and it is made of a left-handed metamaterial which possesses both negative real parts of dielectric permittivity $`ϵ_3`$ and magnetic permeability $`\mu _3`$. The interface between the second and third media supports surface waves which can be excited resonantly when the tangential component of the wave vector of the incident beam coincides with the propagation constant of the surface polariton. In such a case, the surface wave can transfer energy along the interface leading to a great enhancement of the lateral beam shift.

The Goos-Hänchen shift $`\mathrm{\Delta }`$ can be calculated analytically as $`\mathrm{\Delta }=d\mathrm{\Phi }/dk_x`$ Brekhovskikh:Waves , when the phase $`\mathrm{\Phi }`$ of the reflection coefficient is a linear function of the wave vector component $`k_x`$ along the interface, across the spectral width of the beam. The (standard) lateral beam shift has been calculated for the reflection from layered structures with left-handed materials, for the cases of a single interface Berman:2002-067603:PRE  and for a periodic structure of alternating right- and left-handed layers Shadrivov:2003-:APL .

In our geometry \[see Fig. 1(a)\], the reflection coefficient $`R=R(k_x)`$ for the TE-polarized plane monochromatic \[$`\mathrm{exp}(i\omega t)`$\] wave can be found as

$$R=\frac{(\alpha _1+1)(\alpha _2+1)(\alpha _11)(\alpha _21)e^{2ik_2d}}{(\alpha _11)(\alpha _2+1)(\alpha _1+1)(\alpha _21)e^{2ik_2d}},$$
(1)
where $`\alpha _{1,2}=k_{z1,3}\mu _2/k_{z2}\mu _{1,3}`$, $`k_{zi}=(\omega ^2ϵ_i\mu _i/c^2k_x^2)^{1/2}`$, where $`i=1,2,3`$, $`d`$ is the gap thickness, and $`c`$ is the speed of light in vacuum. Here, we consider the TE polarized waves, but the results are qualitatively similar for the TM polarized waves.

We consider an incident beam of the Gaussian shape, $`E_i(x)=\mathrm{exp}(x^2/4a^2ik_{x0}x)`$, where $`a`$ is the width of the beam, $`k_{x0}`$ determines the angle of incidence $`\varphi `$, $`k_{x0}=k_1\mathrm{sin}\varphi `$, and $`k_1`$ is the propagation constant in the fist medium, $`k_1=\omega \sqrt{(ϵ_1\mu _1)}/c`$. The reflected field is found in a standard way

$$E_r(x)=\frac{1}{2\pi }_{\mathrm{}}^{\mathrm{}}R(k_x)\overline{E}_i(k_x)𝑑k_x,$$
(2)
where $`\overline{E}_i`$ is the Fourier spectrum of the incident beam.

Larger lateral beam shifts are expected at the angles of incidence such that the beam spectrum contains the components with the same $`k_x`$ as the propagation constant of the surface waves. As has been shown recently, both forward and backward surface polaritons can exist at the left-handed interface Shadrivov:unpub , depending on the parameters $`X=|ϵ_3|/ϵ_2`$ and $`Y=|\mu _3|/\mu _2`$. Excitation of the forward surface waves results in the energy transfer in the direction of incidence. A negative shift of the beam is obtained when the backward surface waves are excited, this corresponds to the parameters $`XY>1`$ and $`Y<1`$.

We define the relative beam shift $`\mathrm{\Delta }`$ as the normalized first momentum of the electric field of the reflected beam, $`\mathrm{\Delta }=\mathrm{\Delta }_1`$, where

$$\mathrm{\Delta }_n=a^n_{\mathrm{}}^{\mathrm{}}x^n|E_r(x)|^2𝑑x\left(_{\mathrm{}}^{\mathrm{}}|E_r(x)|^2𝑑x\right)^1.$$
(3)
The values $`\mathrm{\Delta }1`$ correspond to the beam shift much smaller then the beam width, while $`\mathrm{\Delta }1`$ corresponds to a giant Goos-Hänchen shift. The second momentum $`\mathrm{\Delta }_2`$ characterizes a change of the beam width during the reflection, $`W=\mathrm{\Delta }_2^{1/2}`$.

We chose the following parameters of the media: $`ϵ_1=12.8`$, $`\mu _1=ϵ_2=\mu _2=1`$, $`ϵ_3=3`$, $`\mu _3=0.5`$. The propagation constant of surface polaritons can be found from the relation $`h^2=(\omega /c)^2ϵ_2\mu _2Y(YX)/(Y^21)`$, and for these parameters the surface waves at the interface are backward propagating. Figures 1(b,c) show the dependence of $`\mathrm{\Delta }`$ and $`W`$ on the angle of incidence at $`\omega a/c=100`$ and $`\omega d/c=3`$, respectively. We observe a distinctive resonant dependence of the beam shift, and the maximum corresponds to the phase matching condition $`k_{x0}=h`$.

In the inset (2) of Fig. 1(c), two distinctive peaks in the reflected beam are observed. The first peak corresponds to a mirror reflection, while the second peak is shifted from the incident beam and it appears due to the excitation of surface waves. At the resonance, the lateral beam shift becomes larger than the beam width. The double-peak structure appears only for narrow beams, when the beam spectrum is wider than the spectrum width of the surface mode, the later can be found as a width of the resonance shown in Fig. 1(b). The components of the beam spectrum outside this region are reflected in a mirror-like fashion, while the spectrum components near the resonance transform into a surface wave, being responcible for the second peak in the shifted reflected beam. For wider beams, such that their spectrum is completely falls into the surface mode excitation line, only the shifted peak appears. With an increase of the beam width, though, the relative beam shift decreases due to the fact that the absolute shift of the beam grows slower than the beam width.

Figures 2(a-c) show the beam shift and width vs. the normalized gap thickness and the structure of the energy flow. The resonances observed in Figs. 2(a,b) have simple physical explanation. Indeed, when the gap is absent ($`d=0`$) or small, no surface wave is excited, and the beam shift is negligible. Increasing the gap width, one increases the quality factor of the surface mode, thus increasing its propagation distance and the reflected beam shift. Similarly, for large $`d`$ the surface wave is not excited, and the reflected beam shift becomes small again.

To understand deeper the physical mechanism for the giant Goos-Hänchen shift, we calculate the energy flow for the beam reflection and compare it with the results for the right-hand media Lai:2000-7330:PRE . Figure 2(c) shows the structure of the energy flow for the case of a negative lateral shift. The strongly curved flow lines in the upper medium correspond to the interference of the incident and mirror-like reflected beams. The finite-extension surface wave excited in a slab along the interface has a distinctive vortex-like structure Shadrivov:PRE . This surface wave transfers the energy in the negative direction, and then the energy is reflected from the interface as a shifted beam.

To make our predictions more realistic, we study the effect of losses always present in left-handed materials. We introduce losses by adding the imaginary parts to the dielectric permittivity $`ϵ_3`$ and magnetic permeability $`\mu _3`$. In particular, we take $`m(\mu _3)=210^5`$ and vary the imaginary part of $`ϵ_3`$. We notice that the losses in the left-handed medium affect mostly the surface waves and, therefore, the major effect produced by the losses is observed for the strongly shifted beam component.

We distinguish two limiting cases. When the beam is narrow, i.e. its spectral width is large, only a part of the beam energy is transferred to surface waves, while the other part is reflected. This case is shown is Figs. 3(a,b). In this case the increase of losses, i.e. the increase of the absolute value of $`m(ϵ_3)`$, results in the suppression of the second peak in the reflected beam, which is due to the surface wave excitation. The growth of the amplitude of the mirror-like reflected beam can be explained by a detuning from the resonance between the incident wave and the surface polariton.

For a wide beam with a narrow spectrum, almost all energy of the beam is transferred into a surface wave and, therefore, the lateral shift becomes strongly affected by the losses in the left-handed medium, as shown in Fig. 3(c). Figure 3(d) show the dependence of the reflection coefficient on the imaginary part of the dielectric permittivity in the third medium.

In conclusion, we have described the Goos-Hänchen shift and splitting of a beam totally reflected from a layered structure with a left-handed metamaterial. The giant lateral shift of the beam is explained by the resonant excitation of surface vortex-like polaritons at the interface between the right- and left-handed materials. The beam shift can be both positive and negative, depending on the type of the surface waves excited at the interface. We believe that the giant enhancement of the lateral shift of the reflected beam can be employed for direct measurements of the parameters of left-handed materials.