text:
# Superfast front propagation in reactive systems with anomalous diffusion

\[

## Abstract

We study a reaction diffusion system where we consider a non-gaussian process instead of a standard diffusion. If the process increments follow a probability distribution with tails approaching to zero faster than a power law, the usual qualitative behaviours of the standard reaction diffusion system, i.e., exponential tails for the reacting field and a constant front speed, are recovered. On the contrary if the process has power law tails, also the reacting field shows power law tail and the front speed increases exponentially with time. The comparison with other reaction-transport systems which exhibit anomalous diffusion shows that, not only the presence of anomalous diffusion, but also the detailed mechanism, is relevant for the front propagation.

\]

The propagation of fronts generated by a reaction-transport system has a considerable interest in a large number of chemical, biological and physical systems . One important model is the advection-reaction-diffusion equation (ARD)

$$_t\theta +(𝐮)\theta =D_0^2\theta +f(\theta )/\tau ,$$
(1)
where $`D_0`$ is the molecular diffusivity, $`𝐮`$ is a given incompressible velocity field and the term $`f(\theta )/\tau `$ describes the production process, whose typical time is $`\tau `$. The scalar field $`\theta `$ represents the fractional concentration of the reaction’s products: $`\theta =1`$ indicates the inert material, $`\theta =0`$ the fresh one and $`0<\theta <1`$ means that fresh materials coexist with products. Usually one considers $`f(\theta )`$ with an unstable fixed point at $`\theta =0`$ and a stable one at $`\theta =1`$ .

Eq. (1) was originally introduced (in the case $`𝐮=\mathrm{𝟎}`$) by Fisher and Kolmogorov, Petrovskii and Piskunov (FKPP) with $`f(\theta )=\theta (1\theta )`$ . Then, the ARD equation has been widely studied in the context of combustion, population growth, aggregation and deposition.
In absence of stirring $`(𝐮=\mathrm{𝟎})`$ it can be shown that a front, replacing the unstable state by the stable one, moves with a speed $`v_0=2\sqrt{D_0f^{}(0)/\tau }`$. This result is valid whenever $`f(\theta )`$ is a positive convex function $`(f^{\prime \prime }(\theta )<0)`$ with two fixed points. For a non-convex production term only an upper and lower bound for $`v_0`$ can be provided .
A more interesting situation occurs in the presence of stirring $`(𝐮\mathrm{𝟎})`$: the front propagates with an average limiting speed $`v_f`$ larger than $`v_0`$. Under general conditions , the advection-diffusion equation, i.e., $`_t\theta +(𝐮)\theta =D_0^2\theta `$, has the same asymptotic feature of a diffusion equation. One has that the field $`\theta `$ (obtained with an average on volumes of linear size much larger than the typical length of $`𝐮`$) at large time obeys a Fick equation:

$$_t\theta =\underset{i,j}{}D_{ij}^e_{ij}^2\theta .$$
(2)
The eddy diffusion coefficients, $`D_{ij}^e`$, contain all the (often non-trivial) effects of the velocity field $`𝐮`$. Eq.(2) states that a test particle described by the Langevin equation:

$$\mathrm{d}𝐱/\mathrm{d}t=𝐮+\sqrt{2D_0}𝜼$$
(3)
where $`𝜼`$ is a white gaussian noise with $`\eta _i=0`$ and $`\eta _i(t)\eta _j(t^{})=\delta _{ij}\delta (tt^{})`$, follows, at large time, a Brownian motion $`(x(t)x(0))^22D_{11}^et`$, where we suppose that the first coordinate is the propagation direction. As a consequence of the asymptotic diffusive behaviour it is possible to show that the front propagates with a finite $`v_f2\sqrt{D_{11}^ef^{}(0)/\tau }`$ .
If the conditions for the validity of standard diffusion do not hold, anomalous diffusion can be observed, i.e.,

$$(x(t)x(0))^2t^{2\nu }$$
(4)
with $`\nu >1/2`$ (super-diffusion) . There are at least three known mechanisms leading to the anomalous diffusion :
a) an infinite variance of the velocity field $`𝐮`$;
b) an infinite memory, i.e., the velocity-velocity correlation function has a non integrable tail;
c) an effective diffusion coefficient increasing with the distance between two particles (in the case of relative diffusion).

Mechanism a) is perhaps the simplest one and Lévy flights belong to this class . Some deterministic maps (e.g., the standard map for specific values of the control parameter) can produce super-diffusion according to mechanism b) . An important example of mechanism c) is given by the fully developed turbulence . There, the relative dispersion of two particles at distance $`R`$ is described by a diffusion equation with an effective diffusion coefficient $`D^eR^{4/3}`$.
It is natural to wonder about the effects of the super-diffusion for the front propagation. In this letter we discuss mechanism a). The evolution equation of $`\theta `$ has the structure:

$$_t\theta =\widehat{L}_\alpha \theta +f(\theta )/\tau $$
(5)
where $`\widehat{L}_\alpha `$ is a linear operator accounting for the concentration spreading of test particles evolving according to Lévy flights with exponent $`\alpha `$. An $`\alpha `$-Lévy flight is an independent increment stochastic process, and the distribution of each increment is a Lévy-stable distribution which exhibits a power law tail $`P_\alpha (w)|w|^{(1+\alpha )}`$, with $`1<\alpha <2`$. The moments behave as $`|x(t)|^qt^{q/\alpha }`$ for $`q<\alpha `$ and $`|x(t)|^q=\mathrm{}`$ for $`q>\alpha `$. So, the role of $`\nu `$ in Eq. (4) is played by $`1/\alpha `$ (for $`q<\alpha `$). Since $`1/\alpha >1/2`$, one can speak of anomalous diffusion. Summarizing, we replace the operator $`(𝐮)+D_0^2`$ in the Eq. (1) by $`\widehat{L}_\alpha `$ substituting an $`\alpha `$-Lévy flight to the Eq. (3). Only for simplicity in the notation and in the numerical computation  we consider a reacting term which is non zero only at discrete time step, when $`\delta `$-form impulses occur:

$$f(\theta ,t)=\underset{n=\mathrm{}}{\overset{\mathrm{}}{}}g(\theta )\delta (tn\mathrm{\Delta }t)\mathrm{\Delta }t,$$
(6)
and we introduce the reaction map $`G(\theta )=\theta +\frac{\mathrm{\Delta }t}{\tau }g(\theta )`$ governing the evolution of an homogeneous field $`\theta `$ (i.e., without diffusion): $`\theta (t+0^+)=G(\theta (t))`$. The detailed shape of $`G(\theta )`$ is not important , it is just necessary to have an unstable fixed point in $`\theta =0`$ and a stable one in $`\theta =1`$. In the following we will present the results for the map:

$$G(\theta )=\theta /[\theta +(1\theta )\mathrm{exp}(\mathrm{\Delta }t/\tau )].$$
(7)
i.e., the exact solution of the equation $`d\theta /dt=\theta (1\theta )/\tau `$. Noting that, assuming Eq. (6), between $`t+0^+`$ and $`t+\mathrm{\Delta }t`$ Eq. (5) reduces to the linear equation $`_t\theta =\widehat{L}_\alpha \theta `$, and we can determine the field $`\theta (x,t+\mathrm{\Delta }t)`$ in terms of $`\theta (x,t)`$:

$`\theta (x,t+\mathrm{\Delta }t)`$ $`=`$ $`{\displaystyle _{\mathrm{}}^+\mathrm{}}dwP_{\alpha ,\mathrm{\Delta }t}(w)\theta (xw,t+0^+)`$ (8)
$`=`$ $`{\displaystyle _{\mathrm{}}^+\mathrm{}}dwP_{\alpha ,\mathrm{\Delta }t}(w)G(\theta (xw,t))`$ (9)
where $`P_{\alpha ,\mathrm{\Delta }t}(w)`$ is the probability distribution to have a flight of size $`w`$ in a time interval $`\mathrm{\Delta }t`$. Of course $`t=n\mathrm{\Delta }t`$, where $`n`$ is an integer number. Let us note that, if one assumes the expression (6) for $`f(\theta )`$, (9) is an exact relation and not only an approximation for small $`\mathrm{\Delta }t`$. It is important to stress that using (9) one can avoid the problem of the precise definition of $`\widehat{L}_\alpha `$ in terms of fractional derivative . In addition one can study the evolution Eq. (9) using a generic distribution $`P_{\alpha ,\mathrm{\Delta }t}(w)`$ which is in the basin of attraction of the $`\alpha `$-Lévy stable distribution.
A similar problem has been studied for reaction systems driven by a Lévy walk . In  reaction-transport processes using non gaussian random walk for the diffusion process are studied. This approach is similar to our one, but the analysis of  is always for a class of processes which give rise to standard diffusion. In addition, in the context of disturbance propagation in chaotic extended systems with long-range coupling, Torcini and Lepri  studied a discrete space version of (9) with a linear shape for $`G(\theta )`$.
Regarding the numerical simulations we study a 1D grid with open boundary conditions and symmetric initial condition with $`\theta (x,0)0`$ in a small region around $`x=0`$. We show the results obtained with the reaction map given by Eq.(7) and $`\tau =1`$. The principal measured observables are the quantity of inert material, $`m(t)`$, and the front speed, $`v_f`$, defined as:

$$m(t)=_{\mathrm{}}^+\mathrm{}dx\theta (x,t)v_f=\underset{t\mathrm{}}{lim}\frac{m(t)}{2t}.$$
(10)
Simple arguments suggest that if $`P(w)`$ is steep enough, e.g., $`P(w)\mathrm{exp}(\beta |w|)`$ then the asymptotic behaviour of $`\theta (x,t)`$ is the usual one of the standard FKPP equation, i.e., $`\theta (x,t)h(xv_ft)`$ where $`v_f\sqrt{w^2}`$ and $`h(z)\mathrm{exp}(\gamma z)`$ for $`z1`$.

In this case the inert material increases linearly in time: $`m(t)=\text{const}+2v_ft`$ (as for the FKPP equation, see Fig. 1).
More interesting is the case of super-diffusive behaviour with $`\alpha `$-Lévy flight ($`1<\alpha <2`$). The shape of $`P(w)`$ used in the numerical computation is $`P(w)=P_0`$ for $`|w|<w_0`$ and $`P(w)=P_n|w|^{(1+\alpha )}`$ for $`|w|w_0`$. The values of the parameters, $`P_n`$ and $`P_0`$, are chosen to guarantee continuity in $`w_0`$ and normalization of $`P(w)`$. Fig. 2 shows that at large time $`\theta `$ develops a power law behaviour $`\theta |x|^{(\alpha +1)}`$. In addition, the inert material invades the fresh one ($`\theta 0`$) exponentially fast. This can be seen by looking at the total quantity of inert material at time $`t`$,

$$m(t)e^{ct}$$
(11)
(see the inset of Fig. 2).

The numerical results illustrated above are supported by an analytical argument using a linear analysis of the tail of $`\theta (x,t)`$ (which is expected to be valid for pulled dynamics ) and the theory of the infinitely divisible distributions . For $`\theta `$ around zero, $`G(\theta )`$ has a linear shape $`G(\theta )a\theta `$ with $`a>1`$. Plugging this into (9), for $`x1`$, one has

$`\theta (x,t)`$ $``$ $`a(P\theta )(x,t1)`$ (12)
$``$ $`a^t(PP\mathrm{}P\theta )(x,0)`$ (13)
where $``$ indicates the convolution operation. It is well known  that processes with power law tail $`P(w)|w|^{(1+\alpha )}`$ with $`1<\alpha <2`$ are in the basin of attraction of the $`\alpha `$-Lévy-stable distribution $`P_\alpha (w)`$. Therefore (13) yields for $`|x|1`$ and large $`t`$

$$\theta (x,t)|x|^{(1+\alpha )}a^t,$$
(14)
in agreement with the behaviour of Figure 2. The growth coefficient in Eq. (11), $`c`$, can be computed with a matching argument. We expect (and this is confirmed by simulations) there exists an $`\stackrel{~}{x}`$ value such that $`\theta 1`$ for $`x<\stackrel{~}{x}`$ and $`\theta |x|^{(1+\alpha )}`$ for $`x>\stackrel{~}{x}`$. We can write $`m(t)2\stackrel{~}{x}`$, and the value of $`\stackrel{~}{x}`$ can be obtained simply matching the $`\theta (x,t)`$ in (14) with $`\theta 1`$, i.e., $`\stackrel{~}{x}a^{t/(1+\alpha )}=\mathrm{exp}(\frac{\mathrm{ln}a}{1+\alpha }t)`$ and therefore $`c=\mathrm{ln}a/(1+\alpha )`$, in good agreement with numerical results (see the inset of Fig. 2). The transient, when $`\mathrm{max}\theta (x,0)`$ is small enough, is dominated by the reaction term, giving an exponential growth $`m(t)a^t`$.

Particularly interesting is the behaviour for $`P(w)|w|^{(1+\alpha )}`$ with $`\alpha >2`$. In this case the distribution belongs to the basin of attraction of the gaussian law since $`w^2<+\mathrm{}`$ (see ). In fact, although the probability distribution, $`P(x_t)`$, of the sum of independent random variables, $`x_t=_{j=1}^tw_j`$, has a power law tail, the core of the distribution behaves as a gaussian, and the tail is less and less important as $`t`$ grows (see Fig. 3). Therefore, at first glance, one could expect the same features of the standard FKPP equation.

But, in reacting systems the presence of this tail can have an important role. In fact for each initial condition, $`\theta (x,0)`$, localized in a small region (e.g., around $`x=0`$), already at the first step, the front has a shape not steep enough for the usual FKPP propagation (i.e., $`\theta (x,1)|x|^{(1+\alpha )}`$. Then, because of the reaction, i.e., the instability of $`\theta =0`$, the tail of $`\theta `$ increases exponentially in time. As consequence of the gaussian core of $`P(x_t)`$ we expect that the bulk of $`\theta `$ behaves in the FKPP way, but, at large time, the exponential growth of the tail has the dominant role.
In Fig. 4 it is shown how, the exponential form of the front (which moves with a constant velocity) is overcome by a power law tail that grows more and more as the time increases, i.e., the initial FKPP behaviour (constant $`v_f`$ and $`\theta (x,t)`$ with exponential decay) is replaced by the exponential increasing of the inert material and $`\theta (x,t)`$ with power law tail. This result is similar to that obtained in  in the context of the growth of perturbation in CML: even a weak long range coupling (e.g, a power law with large $`\alpha `$) has, at large time, a dramatic effect.
Summarizing, we have shown how, in a reaction diffusion system, replacing a standard diffusion with a process whose probability distribution has a tail approaching to zero faster than a power law, one has the same qualitative behaviour of the usual FKPP system, i.e., exponential decay of the front and a finite front speed.

On the contrary, if the process has the same tail in the probability distribution of an $`\alpha `$-Lévy stable process one achieves an exponentially fast propagation of the front, instead of the linear one. Moreover the tails of the field $`\theta `$ have a power law behaviour instead of the exponential decay. As intermediate behaviour we have the case of a stochastic process whose increment have a power law tail but with finite variance. In this case, initially one has the usual FKPP behaviour, but after a while, one has an exponential growing of the inert material.
Let us now compare the above described scenario with the case of super-diffusion induced by strong time correlation of the velocity field. An example is provided by the standard map with suitable values of the control parameter $`K`$ . This advection-diffusion system can show super-diffusive behaviour  in the limit of $`D_00`$. However in the presence of reaction the front speed is finite for each value of $`D_0`$, because it is bounded by $`U_{max}+v_0`$, where $`U_{max}`$ is the maximum velocity of the test particle, and $`v_0`$ is the front speed in absence of stirring. Therefore, just the presence of anomalous diffusion does not necessarily imply a non-linear front propagation, but also the details of the transport-diffusion and reaction mechanisms are important. For example, in the system (8) using a reaction map with $`G(\theta )=\theta `$ around $`\theta =0`$ (e.g., ignition) we have always the usual scenario shown in Fig. 1 also for $`1<\alpha <2`$.
Such a fact is, in our opinion, relevant for the modeling of realistic reaction systems: one has to mimic precisely the mechanism that gives rise to the anomalous diffusion, beyond the simple power law behaviour of $`x^2(t)`$.

We thank M. Cencini, P. Muratore-Gianneschi and A. Torcini for useful discussions and comments. A.V. thanks A.Kupiainen for his kind hospitality at the University of Helsinki during the final write up of this article. This work has been partially supported by INFM Parallel Computing Initiative and MURST (Cofinanziamento Fisica Statistica di Sistemi Complessi Classici e Quantistici). We acknowledge support from the INFM Center for Statistical Mechanics and Complexity (SMC).


format: text

text:
# References

May 2002

Entropy bounds and Cardy-Verlinde formula in Yang-Mills theory

Shin’ichi NOJIRI111nojiri@cc.nda.ac.jp, and Sergei D. ODINTSOV222 odintsov@mail.tomsknet.ru

Department of Applied Physics
National Defence Academy, Hashirimizu Yokosuka 239-8686, JAPAN

$`\mathrm{}`$ Lab. for Fundamental Study, Tomsk State Pedagogical University
634041 Tomsk, RUSSIA

ABSTRACT

Using gauge formulation of gravity the three-dimensional $`SU(2)`$ YM theory equations of motion are presented in equivalent form as FRW cosmological equations. With the radiation, the particular (periodic, big bang-big crunch) three-dimensional universe is constructed. Cosmological entropy bounds (so-called Cardy-Verlinde formula) have the standard form in such universe. Mapping such universe back to YM formulation we got the thermal solution of YM theory. The corresponding holographic entropy bounds (Cardy-Verlinde formula) in YM theory are constructed. This indicates to universal character of holographic relations.

It becomes popular in theoretical physics to apply different formulations (and even theories) in the description of the same phenomenon. For example, it is expected that Einstein theory presented in Yang-Mills (YM) form is easier to quantize. Moreover, its renormalizability properties seem to be better in YM-like form . From another point, there exists the YM theory presentation in Einstein-like form. In this relation the natural question is: can one achieve some new results in YM theory using recent studies of cosmology based on holographic principle?

In this paper we start the investigation in this direction. Using three-dimensional YM theory as an example we first rewrite it in the gravitational form. The YM equations of motion are then rewritten as FRW cosmological equations where natural definition of Hubble, Bekenstein and Bekenstein-Hawking entropies maybe done. As a result FRW equation is represented in the form similar to two-dimensional CFT entropy (so-called Cardy-Verlinde formula ). Introducing the radiation (matter) the explicit solution of such three-dimensional periodic universe is obtained. The cosmological entropy bounds (holographic Cardy-Verlinde formula) are quite simple for such universe. In particular, the Bekenstein entropy is constant. Such three-dimensional universe is then mapped back to YM theory form. (Such procedure maybe considered as an interesting way of generating of YM solutions from FRW cosmological solutions). The correspondent thermal YM solution on which YM action diverges is constructed. The divergence of action is absorbed into the renormalization of the gauge coupling constant. After the identification of YM entropy with Bekenstein entropy the Cardy-Verlinde formula defines the entropy bounds in YM theory.

The action of Yang-Mills theory with the gauge group $`SU(2)`$ is given by

$`S_{\mathrm{YM}}`$ $`=`$ $`{\displaystyle \frac{1}{4g_{\mathrm{YM}}^2}}{\displaystyle d^dx\underset{a=1}{\overset{3}{}}\left(F_{ij}^aF^{aij}+4g_{\mathrm{YM}}^2A_i^aJ^{ai}\right)}`$ (1)
$`F_{ij}^a`$ $`=`$ $`_iA_j^a_iA_j^a{\displaystyle \underset{b,c=1}{\overset{3}{}}}ϵ^{abc}A_i^bA_j^c.`$ (2)
Here $`d`$ is the dimension of the spacetime and $`J^{ai}`$ is the external source. For $`d=3`$, one can rewrite the action (1) in the following form:

$$S_{\mathrm{YM}}=\frac{1}{2g_{\mathrm{YM}}^2}d^dx\underset{a=1}{\overset{3}{}}\left(B_i^aB^{ai}+2g_{\mathrm{YM}}^2A_i^aJ^{ai}\right).$$
(3)
Here $`B_i^a`$ is defined by

$$B^{ak}=ϵ^{kij}\left(_iA_j^a\frac{1}{2}ϵ^{abc}A_i^bA_j^c\right),$$
(4)
The equations of motion are

$$0=ϵ^{kij}D_kB_j^ag_{\mathrm{YM}}^2J^{ai}=ϵ^{kij}\left(_kB_j^a\frac{1}{2}ϵ^{abc}A_k^bB_j^c\right)g_{\mathrm{YM}}^2J^{ai}.$$
(5)
Here $`D_i`$ expresses the covariant derivative. On the other hand, Bianchi identities are:

$$0=D_iB^{ai}.$$
(6)
There exists a formulation of gravity starting from the gauge theory, whose gauge group is the Poincare group composed of translations and Lorentz transformations. The gauge field of the translation corresponds to the vierbein (or vielbein) and that of the Lorentz tansformation to the spin-connection. The gauge curvature of the translation corresponds to the torsion. Then if we impose a condition that the curvature vanishes, we can solve the spin connection in terms of the vier(viel)bein field if the dimension of the spacetime is larger than 2. As the Lorentz group is $`S(d1,1)`$ for $`d`$-dimensional spacetime, one can rewrite the gauge field of $`SO(d1,1)`$ by the vier(viel)bein field. Such a formulation for the supergravity is developed in . In the similar way in ref., 4 dimensional Yang-Mills theory is presented in the Hamiltonian formulation in terms of 3 dimensional gravity333The presentation of SUSY YM theory in terms of Riemann geometry is recently considered in .. The parametrization of the gauge field used in the paper corresponds to the expression of the spin connection by the dreibein fields.

In the following, as a most simple and non-trivial case, we consider the case that the dimension of the spacetime is 3 ($`d=3`$) and the spacetime is Euclidean, where the Lorentz group is $`SO(3)`$ or $`SU(2)`$. In case that the spacetime is 3 dimensional Euclidean space, the Poincare algebra is generated by the generators of the translation $`T^a`$ $`(a=1,2,3)`$ and the rotation $`R^a`$ $`(a=1,2,3)`$ around $`a`$-axis. The algebra is explicitly given by

$$[R^a,R^b]=ϵ^{abc}R^c,[R^a,T^b]=ϵ^{abc}T^c,[T^a,T^b]=0.$$
(7)
Denote the gauge fields corresponding to the translation and the rotation by $`u_i^a`$ and $`A_i^a`$ ($`a=1,2,3`$), respectively. Then the curvatures $`R_{ij}^{Ta}`$ corresponding to the translation and $`R_{ij}^{Ra}`$ corresponding to the rotation are given by

$`R_{ij}^{Ta}`$ $`=`$ $`_iu_j^a_iu_j^aϵ^{abc}\left(A_i^bu_j^cA_j^bu_i^c\right),`$
$`R_{ij}^{Ra}`$ $`=`$ $`_iA_j^a_iA_j^aϵ^{abc}A_i^bA_j^c.`$ (8)
The relation

$$R_{ij}^{Ta}=0$$
(9)
corresponds to the torsionless condition in gravity. The condition (9) can be solved with respect to $`A_i^a`$:

$`A_i^a`$ $`=`$ $`ϵ^{abc}\left(_iu_j^b_ju_i^b\right)\left(u^1\right)_c^j+{\displaystyle \frac{1}{4}}ϵ^{bcd}\left(_ku_j^b_ju_k^b\right)\left(u^1\right)_c^j\left(u^1\right)_d^ku_i^a`$ (10)
$`=`$ $`{\displaystyle \frac{ϵ^{nmk}_mu_k^b\left(u_n^au_i^b\frac{1}{2}u_n^bu_i^a\right)}{detu}}.`$
Then the field strength $`B^{ak}`$ defined by (4) is related with the Einstein tensor $`G^{ij}=R^{ij}\frac{1}{2}g^{ij}R`$ by

$$B^{ai}=\sqrt{g}u_j^aG^{ij}.$$
(11)
Here the metric tensor $`g_{ij}`$ is defined by

$$g_{ij}=u_i^au_j^b$$
(12)
and $`R^{ij}`$ and $`R`$ are the Ricci curvature and the scalar curvature constructed on $`g_{ij}`$. Let denote the covariant derivative with respect to the $`SO(3)`$ gauge group by $`D_i`$ and the covariant derivative with respect to the gravity by $`_i`$. Then Eq.(11) tells that

$$D_jB^{ai}=\sqrt{g}u_j^a\left(_jG^{ij}\mathrm{\Gamma }_{jl}^iG^{kl}+\mathrm{\Gamma }_{lj}^lG^{kl}\right),$$
(13)
which leads

$$D_iB^{ai}=\sqrt{g}u_j^a_iG^{ij}.$$
(14)
The Bianchi identity

$$_iG^{ij}=0$$
(15)
can be consistent with the gauge Bianchi identity (6). By using (11), the Einstein equation

$$G^{ij}=\kappa ^2T^{ij},$$
(16)
with the energy-momentum tensor $`T_{\mu \nu }`$ can be rewritten in terms of the gauge fields:

$$B_i^a=B_i^{\mathrm{ext}a},B_i^{\mathrm{ext}a}\frac{\kappa ^2}{2}\sqrt{g}u_j^aT^{ij}.$$
(17)
Here one can regard $`B_i^{\mathrm{ext}a}`$ as an external filed, which is related with $`J^{ai}`$ (5) by

$$ϵ^{kij}D_kB_j^{\mathrm{ext}a}=g_{\mathrm{YM}}^2J^{ai}.$$
(18)
Since the conservation of the energy-momentum tensor $`_iT^{ij}=0`$ corresponds to the “conservation law” of the external fields, if the energy-momentum conservation holds one can construct the solution of the Bianchi identity (6) from the solution of the Einstein equation (16) using (11).

Now we consider more concrete solution. Assume the dreibein fields have a form of

$$u_t^1=1,u_\theta ^2=\mathrm{e}^{A(t)},u_\varphi ^3=\mathrm{sin}\theta \mathrm{e}^{A(t)},\text{other components}=0,$$
(19)
which give the Euclidean FRW metric

$$ds^2=dt^2+l^2\mathrm{e}^{2A(t)}\left(d\theta ^2+\mathrm{sin}^2\theta d\varphi ^2\right).$$
(20)
The Minkowski signature metric can be obtained changing the compact gauge group $`SU(2)`$ or $`SO(3)`$ to the non-compact ones $`SU(1,1)`$, $`SO(2,1)`$ or $`SL(2,C)`$. The assumptions (19) give

$`A_t^1=A_t^2=A_t^3=A_\theta ^1=A_\theta ^2=A_\varphi ^3=0`$
$`A_\theta ^3=l\mathrm{e}^A\dot{A},A_\varphi ^2=l\mathrm{sin}\theta \mathrm{e}^A\dot{A},A_\varphi ^1=\mathrm{cos}\theta ,`$ (21)
$`B^{2t}=B^{3t}=B^{1\theta }=B^{3\theta }=B^{1\varphi }=B^{2\varphi }=0`$
$`B^{1t}=l^2\mathrm{sin}\theta \mathrm{e}^{2A}\dot{A}^2\mathrm{sin}\theta ,B^{2\theta }=l\mathrm{sin}\theta \left(\ddot{A}+\dot{A}^2\right)\mathrm{e}^A,`$
$`B^{3\varphi }=l\left(\ddot{A}+\dot{A}^2\right)\mathrm{e}^A.`$ (22)
If we define $`B^{ab}`$ by

$$B^{ab}=u_i^bB^{ai},$$
(23)
Eq.(11) tells $`B^{ab}`$ is symmetric:

$$B^{ab}=B^{ba}.$$
(24)
Any $`N\times N`$ symmetric matrix $`M`$, in general, can be diagonalized by a matrix $`O`$ from $`SO(N)`$, $`MO^1MO=\left(\begin{array}{ccccc}m_1& 0& & \mathrm{}& 0\\ 0& m_2& 0& \mathrm{}& 0\\ 0& 0& \mathrm{}& & \mathrm{}\\ \mathrm{}& \mathrm{}& & \mathrm{}& 0\\ 0& 0& \mathrm{}& 0& m_N\end{array}\right)`$. Then using $`SO(3)`$ gauge transformation, one can diagonalize $`B^{ab}`$. The gauge transformation removes 3 components in $`B^{ab}`$, which corresponds to the degree of the freedom. Eq.(19) and also Eq.(S0.Ex4) manifest such a special gauge choice.

The stress-energy tensor may be presented in terms of the energy density $`\rho `$ and the pressure $`p`$ as

$$T^{tt}=\rho ,T^{\theta \theta }=l^2\mathrm{e}^{2A}p,T^{\varphi \varphi }=\frac{1}{l^2\mathrm{sin}\theta }\mathrm{e}^{2A}p,\text{other components}=0,$$
(25)
Thus

$`B^{\mathrm{ext}\mathrm{\hspace{0.17em}2}t}=B^{\mathrm{ext3}t}=B^{\mathrm{ext}\mathrm{\hspace{0.17em}1}\theta }=B^{\mathrm{ext}\mathrm{\hspace{0.17em}3}\theta }=B^{\mathrm{ext}\mathrm{\hspace{0.17em}1}\varphi }=B^{\mathrm{ext}\mathrm{\hspace{0.17em}2}\varphi }=0`$ (26)
$`B^{\mathrm{ext}\mathrm{\hspace{0.17em}1}t}={\displaystyle \frac{\kappa ^2}{2}}l^2\mathrm{sin}\theta \mathrm{e}^{2A}\rho ,B^{\mathrm{ext}\mathrm{\hspace{0.17em}2}\theta }={\displaystyle \frac{\kappa ^2}{2}}l\mathrm{sin}\theta \mathrm{e}^Ap,B^{\mathrm{ext}\mathrm{\hspace{0.17em}3}\varphi }={\displaystyle \frac{\kappa ^2}{2}}l\mathrm{e}^Ap.`$
Then by combining (17), (S0.Ex3) and (26), we obtain the FRW equations:

$`\dot{A}^2+{\displaystyle \frac{1}{a^2}}={\displaystyle \frac{\kappa ^2}{2}}\rho `$ (27)
$`\ddot{A}+\dot{A}^2={\displaystyle \frac{\kappa ^2}{2}}p.`$
If we define $`J^{ai}`$ by (18), any solution of (27) satisfies the equations of motion (5) by the identification (S0.Ex4). Moreover, if the energy momentum tensor (25) satisfies the conservation law $`_iT^{ij}=0`$, the solution of the equation (27) also satisfies the Bianchi identity (6).

Here $`a=l\mathrm{e}^A`$. Combining (S0.Ex3) and (26) with (18), we may obtain the external source $`J^{ai}`$.

In gravity one can define the Hubble, Bekenstein and Bekenstein-Hawking entropies $`S_H`$, $`S_B`$ and $`S_{BH}`$ by

$`S_H^2={\displaystyle \frac{(4\pi )^2V}{\kappa ^4}}\left({\displaystyle 𝑑\theta 𝑑\varphi B^{1t}}+{\displaystyle \frac{V}{a^2}}\right)={\displaystyle \frac{(4\pi )^2V^2\dot{A}^2}{\kappa ^4}},`$
$`S_B=\pi a{\displaystyle 𝑑\theta 𝑑\varphi B^{\mathrm{ext}\mathrm{\hspace{0.17em}1}t}}=\pi aE,S_{BH}={\displaystyle \frac{4\pi V}{\kappa ^2a}},`$ (28)
with space volume $`V`$ and the total energy $`E`$ defined by

$$V=𝑑\theta 𝑑\varphi \sqrt{g}=2\pi a^2,E=𝑑\theta 𝑑\varphi \sqrt{g}\rho ,$$
(29)
Then from FRW equations it follows the relation reminding about two-dimensional CFT entropy  (so-called Cardy-Verlinde formula)

$$S_H^2+S_{BH}^2=2S_{BH}S_B.$$
(30)
The above equation (30) follows from the first equation in (27).

This equation can be rewritten as

$$S_H^2=S_B^2\left(S_{BH}S_B\right)^2.$$
(31)
The well-known square root like in two-dimensional CFT entropy appears when one evaluates Hubble entropy from above relation. We should note that

$$\mathrm{\Phi }=𝑑\theta 𝑑\varphi B^{1t}$$
(32)
is total magnetic flux. Then the external flux

$$\mathrm{\Phi }^{\mathrm{ext}}=𝑑\theta 𝑑\varphi B^{\mathrm{ext}\mathrm{\hspace{0.17em}1}t}$$
(33)
corresponds to the total energy

$$\mathrm{\Phi }^{\mathrm{ext}}=E.$$
(34)
Since Eq.(XVIIIb) tells $`S_B^2\left(S_{BH}S_B\right)^20`$, Eqs.(S0.Ex8) and (34) give somel bound between the external magnetic flux and the spacial volume $`V`$:

$$\left(\mathrm{\Phi }^{\mathrm{ext}}\right)^2\left(\frac{4V}{\kappa ^2a^2}+\mathrm{\Phi }^{\mathrm{ext}}\right)^2.$$
(35)
We should note, however, the spacial volume $`V`$ is given from the gravity side.

In order to proceed further, we consider the radiation as a matter. Then the energy density $`\rho `$ and the pressure $`p`$ have the following forms:

$$\rho =2p=\rho _0\mathrm{e}^{3A}.$$
(36)
The FRW equations (27) are

$`\dot{A}^2+{\displaystyle \frac{\mathrm{e}^{2A}}{l^2}}={\displaystyle \frac{\kappa ^2}{2}}\rho _0\mathrm{e}^{3A}`$
$`\ddot{A}+\dot{A}^2={\displaystyle \frac{\kappa ^2}{4}}\rho _0\mathrm{e}^{3A}.`$ (37)
The solution of (38) is given by using an intermediate variable $`\eta `$ as follows,

$$a=l\mathrm{e}^A=a_0\mathrm{sin}^2\eta ,t=a_0\left(\eta \frac{1}{2}\mathrm{sin}2\eta \right).$$
(38)
The maximum raidus of the universe $`a_0`$ is given by

$$a_0=\frac{\kappa ^2l^3}{2}\rho _0.$$
(39)
The universe starts with the big bang at $`\eta =0`$ ($`t=0`$) and the universe ends with the big crunch at $`\eta =\pi `$ ($`t=\pi a_0`$). Then the universe has the period of $`\pi a_0`$. As this is Euclidean spacetime, one can regard period as the inverse of the temperature $`T`$

$$T=\frac{1}{\pi a_0}.$$
(40)
Since the energy $`E`$ (29) is given by

$$E=4\pi a^2\rho _0\mathrm{e}^{3A}=4\pi l^3\rho _0a^1,$$
(41)
we find that the Bekenstein entropy $`S_B`$ is constant:

$$S_B=4\pi ^2l^3\rho _0=\frac{8\pi ^2}{\kappa ^2}a_0=8\pi \kappa ^2T.$$
(42)
Here Eqs.(39) and (40) are used. When the radius of the universe is maximal ($`a=a_0`$), the Hubble entropy $`S_H`$ and the Bekenstein-Hawking entropy $`S_{BH}`$ are

$$S_H=0,S_{BH}=16\pi \kappa ^2T.$$
(43)
In this case CV formula becomes the identity.

The interesting question is: what happens in terms of Yang-Mills theory? We now evaluate the Yang-Mills action by substituting the classical solution. Being in the Euclidean spacetime, the action can be regarded as the free energy $`F`$ divided by the temperature $`T`$:

$$S_{\mathrm{YM}}=\frac{F}{T}.$$
(44)
Using the obtained free energy, the Yang-Mills theory entropy may be evaluated.

In curved spacetime, the action (1) has the following form:

$$S_{\mathrm{YM}}=\frac{1}{4g_{\mathrm{YM}}^2}d^3x\sqrt{g}\underset{a=1}{\overset{3}{}}\left(F_{ij}^aF^{aij}+4g_{\mathrm{YM}}^2A_i^aJ^{ai}\right).$$
(45)
Then (3) looks as:

$$S_{\mathrm{YM}}=\frac{1}{2g_{\mathrm{YM}}^2}d^3x\underset{a=1}{\overset{3}{}}\left(\frac{1}{\sqrt{g}}B_i^aB^{ai}+2g_{\mathrm{YM}}^2\sqrt{g}A_i^aJ^{ai}\right).$$
(46)
Even in curved spacetime, the Bianchi identity (6) is always satisfied since the Bianchi identity is a topological equation. On the other hand, the equation of motion (5) is modified as

$$0=\frac{1}{\sqrt{g}}ϵ^{kij}D_k\left(\frac{B_j^a}{\sqrt{g}}\right)g_{\mathrm{YM}}^2J^{ai}.$$
(47)
If we define, however, $`J^{ai}`$, instead of (18),

$$\frac{1}{\sqrt{g}}ϵ^{kij}D_k\left(\frac{B_j^{\mathrm{ext}a}}{\sqrt{g}}\right)=g_{\mathrm{YM}}^2J^{ai},$$
(48)
Eq.(47) is always satisfied.

By using the equations of motion (47) and (17), the action (46) can be rewritten in the following form:

$$S_{\mathrm{YM}}=\frac{1}{2g_{\mathrm{YM}}^2}d^3x\frac{1}{\sqrt{g}}\underset{a=1}{\overset{3}{}}B_i^aB^{ai}=\frac{1}{2g_{\mathrm{YM}}^2}d^3x\frac{1}{\sqrt{g}}\underset{a=1}{\overset{3}{}}B_i^{\mathrm{ext}a}B^{\mathrm{ext}ai}.$$
(49)
Then with the help of (19) and (26) one gets

$$S_{\mathrm{YM}}=\frac{\kappa ^4}{8g_{\mathrm{YM}}^2}d^t\mathrm{e}^{2A}\left(\rho ^2+2p^2\right).$$
(50)
By further substituting the solution (38) and using (36), (39) and (40), we obtain the following expression for the action

$$S_{\mathrm{YM}}=\frac{6\pi ^2}{g_{\mathrm{YM}}^2}T_0^\pi \frac{d\eta }{\mathrm{sin}^2\eta }.$$
(51)
The integration in (51) diverges. The divergence may be absorbed into the renormalization of the Yang-Mills coupling $`g`$:

$$\frac{1}{g_R^2}\frac{1}{g_{\mathrm{YM}}^2}_0^\pi \frac{d\eta }{\mathrm{sin}^2\eta }.$$
(52)
Using the renormailized coupling constant $`g_R`$, the action has the following form:

$$S_{\mathrm{YM}}=\frac{6\pi ^2}{g_R^2}T.$$
(53)
From the identification (44), the free energy $`F`$ is given by

$$F=\frac{6\pi ^2}{g_R^2}T^2.$$
(54)
Then the entropy is

$$𝒮=\frac{dF}{dT}=\frac{12\pi ^2}{g_R^2}T.$$
(55)
If we identify

$$\frac{12\pi ^2}{g_R^2}=8\pi \kappa ^2,$$
(56)
the entropy (55) is equal to the Bekenstein entropy $`S_B`$ (42). As we consider curved spacetime, the spacial volume $`V`$ is given by (29). Therefore the identification (56) gives a bound for the entropy of the Yang-Mills theory with the external source $`J^{ai}`$ (48):

$$S_H^2+S_{BH}^2=2S_{BH}𝒮.$$
(57)
As we are now considering the curved spacetime, $`S_{BH}`$ and $`S_B`$ (57) is given, as in (S0.Ex8), by the structures of spacetime where the Yang-Mills field lives. Using (S0.Ex8), (32) and the identification $`𝒮=S_B`$, the entropy in the Yang-Mills theory maybe expressed in terms of the magnetic flux. We can also rewrite Eq.(57) in the form of (31):

$$S_H^2=𝒮^2\left(S_{BH}𝒮\right)^2,$$
(58)
which gives the bound for the entropy $`𝒮`$:

$$𝒮^2S_H^2,𝒮^2\left(S_{BH}𝒮\right)^2.$$
(59)
If necessary the above YM entropy bound found for the particular thermal solution mapped to three-dimensional FRW cosmology maybe completely expressed in terms of gauge fields and sources. Moreover, it is clear that similar procedure maybe applied to study new solutions and entropy bounds for other cases, including YM theory in four and higher dimensions.

There are recent gravitational theory results which have the holographic origin: like FRW cosmology presentation in the form reminding about two-dimensional CFT entropy (see  for a recent review) or cosmological entropy bounds. The main lesson of our investigation is that similar results are in some sense universal. They should be expected in other theories, like in the case of YM theory under consideration.


text:
# Solving Shift Problems and the Hidden Coset Problem Using the Fourier Transform

## 1 Introduction

The Fourier transform lies at the heart of the solution of all problems that are known to admit a large quantum speedup over classical algorithms. This is due to two factors, the quantum Fourier transform can be performed exponentially faster than its classical counterpart, and the Fourier transform is particularly suited to extracting information about periodicities.

Taking a periodic superposition, performing a Fourier transform and measuring gives us the period. More generally, the Fourier transform of a superposition over coset states of a subgroup yields a superposition over the dual or “perp” of the subgroup. This is the basis of the hidden subgroup problem. The most well known example of a problem and algorithm fitting this framework is Shor’s solution to the factoring problem .

However, information about periodicities is not the only feature that Fourier transforms can identify. The Fourier transform can also identify shifts or translations. This suggests that we look for ways in which the Fourier transform can be used to identify unknown shifts.

The shift problem may be formulated as follows.

Let $`g`$ be a complex valued function defined on the group $`G`$. Let $`f`$ be a shifted version of $`g`$ where $`f(x)=g(x+s)`$ for some $`s`$ in $`G`$. Find $`s`$.

We give an efficient quantum algorithm for solving the shift problem provided $`G`$ is abelian and $`g`$ satisfies certain conditions. The conditions are satisfied if $`G`$ is the additive group of a finite field and $`g`$ is a multiplicative character. So our algorithm solves the shifted multiplicative character problem on a finite field.

If the shift is not uniquely determined, it can be shown that the set of possible shifts is a coset of a subgroup of the group $`G`$. We then have the *hidden coset problem*.

Let $`g`$ be a complex valued function defined on the group $`G`$. Let $`f`$ be a shifted version of $`g`$ where $`f(x)=g(x+s)`$ for some $`s`$ in $`G`$. Find all $`s^{}`$ satisfying $`f(x)=g(x+s^{})`$ for all $`x`$.

The hidden coset problem combines the features of the hidden subgroup problem and the shift problem. Our algorithm treats this problem by first solving a hidden subgroup problem to find $`H`$ and then solving a shift problem on the quotient group $`G/H`$. The shifted multiplicative character problem over $`/n`$ fits this framework. The multiplicative characters of $`/n`$ are periodic with respect to the additive group and so the shift is not uniquely determined.

Our algorithm solves the shifted Legendre symbol problem and the shifted quadratic character problem considered by van Dam and Hallgren . The quadratic character is an example of a multiplicative character and the Legendre symbol is the quadratic character for $`/p`$. van Dam and Hallgren also give an algorithm for the shifted Jacobi symbol problem for $`/n`$ where $`n`$ is square free. The Jacobi symbol is also an example of a multiplicative character. Our treatment solves the problem for all multiplicative characters of $`/n`$ for all odd $`n`$.

## 2 The Shift Problem

In this section we state the shift problem, and show how it can be formulated in terms of matrix multiplication. By factoring the relevant matrix we obtain an algorithm for solving the shift problem and also sufficient conditions for the algorithm to be implemented efficiently on a quantum computer. The analysis involves Fourier transforms over finite abelian groups. For a review of characters and Fourier transforms over finite abelian groups see Appendix A.

The shift problem is the following. Let $`g`$ be a complex valued function defined on the group $`G`$. Let $`f`$ be a shifted version of $`g`$ where $`f(x)=g(x+s)`$ for some $`s`$ in $`G`$. Find $`s`$.

We begin by reformulating the shift problem in the following way. Let $`s`$ be the unknown shift and $`X`$ be the matrix with columns and rows indexed by the elements of $`G`$ and the matrix element in row $`x`$ and column $`y`$ given by $`g(x+y)`$. The precise ordering of the elements of $`G`$ is irrelevant as long as we are consistent. That is

$$X=\left[g(x+y)\right]_{x,yG}.$$

We then compute

$`X|s`$ $`={\displaystyle \underset{xG}{}}g(x+s)|x`$
$`={\displaystyle \underset{xG}{}}f(x)|x.`$
Solving the shift problem then reduces to inverting $`X`$.

We show below that the structure of $`X`$ allows us to factor $`X`$ into $`X=(F^T)^1DF^1`$, where $`F`$ is the Fourier transform matrix and $`D`$ is a diagonal matrix. The diagonal entries of $`D`$ (up to a scale factor) turn out to be the Fourier transform of $`g`$ evaluated at the characters of $`G`$. Provided $`g`$ satisfies certain conditions, we can efficiently compute $`X^1`$ by inverting $`F^T`$, $`D`$ and $`F`$ in turn to obtain $`X^1=FD^1F^T`$.

### 2.1 Matrix Factorization

We now show that $`X`$ is “diagonalized”111Strictly speaking we are not diagonalizing $`X`$ as that would mean writing $`X=FDF^{}`$ and not $`X=FDF^T`$. by the Fourier transform matrix. Let $`F`$ be the Fourier transform matrix defined by

$$F=\left[\psi _y(x)\right]_{x,yG},$$

where $`x`$ and $`y`$ index the rows and columns respectively and $`\psi _y`$ is a character of $`G`$ indexed by $`y`$. Thus each column of $`F`$ contains a character of $`G`$ evaluated at all elements of $`G`$.

Computing $`F^TXF`$ we find that

$`F^TXF`$ $`=\left[\psi _v(x)\right]_{v,x}\left[g(x+y)\right]_{x,y}\left[\psi _w(y)\right]_{y,w}`$
$`=\left[\psi _v(x)\right]_{v,x}\left[{\displaystyle \underset{yG}{}}g(x+y)\psi _w(y)\right]_{x,w}`$
$`=\left[\psi _v(x)\right]_{v,x}\left[{\displaystyle \underset{yG}{}}g(y)\psi _w(yx)\right]_{x,w}`$
$`=\left[\psi _v(x)\right]_{v,x}\left[\overline{\psi _w(x)}{\displaystyle \underset{yG}{}}g(y)\psi _w(y)\right]_{x,w}`$
$`=\left[\psi _v(x)\right]_{v,x}\left[\overline{\psi _w(x)}\widehat{g}(\psi _w)\right]_{x,w}`$
$`=\left[{\displaystyle \underset{xG}{}}\psi _v(x)\overline{\psi _w(x)}\widehat{g}(\psi _w)\right]_{v,w}`$
$`=\left[|G|\widehat{g}(\psi _w)\delta _{vw}\right]_{v,w},`$
which is a diagonal matrix. Let $`D`$ denote this diagonal matrix and we have $`F^TXF=D`$.

### 2.2 Matrix Inversion

The algorithm then consists of computing $`X^1=FD^1F^T`$. If $`X`$ is not full rank, then $`D`$ contains some zeros along the diagonal. We then calculate the *pseudoinverse* of $`X`$ (sometimes called the *Moore-Penrose generalized inverse*). The pseudoinverse of $`X`$, $`X^{}`$ satisfies

* $`XX^{}X=X`$,
* $`X^{}XX^{}=X`$,
* $`XX^{}`$ and $`X^{}X`$ are Hermitian.

The pseudoinverse of a matrix always exists and is unique . The pseudoinverse of a diagonal matrix is given by inverting the nonzero elements of the diagonal. We then have $`X^{}=FD^{}F^T`$.

The fraction of zeros along the diagonal of $`D`$ gives the probability of error, the probability that the algorithm fails to output $`s`$.

### 2.3 Sufficient Conditions

To implement the algorithm efficiently we need some conditions on $`g`$.

1. The magnitude of $`g(x)`$ is constant for all $`x`$ such that $`g(x)`$ is nonzero.
2. The Fourier transform of $`g`$, $`\widehat{g}(\psi _y)`$, has constant magnitude for all $`y`$ for which $`\widehat{g}(\psi _y)`$ is nonzero.
3. $`\widehat{g}`$ can be computed efficiently up to a multiplicative constant (on a classical computer).

The above conditions are sufficient for efficient implementation of the algorithm. The following two parameters determine the probability of the algorithm outputting the correct answer.

1. $`\alpha `$, the fraction of $`x`$ in $`G`$ for which $`g(x)`$ is nonzero
2. $`\beta `$, the fraction of $`y`$ in $`G`$ for which the Fourier transform of $`g`$, $`\widehat{g}(\psi _y)`$, is nonzero.

The probability of our algorithm succeeding is $`\alpha \beta `$.

Condition 1 is needed to be able to create the superposition with $`|x`$ having amplitude $`g(x)`$ up to a global constant,

$$\underset{xG}{}g(x)|x.$$

This can be done efficiently with probability $`\alpha `$.

Conditions 2 and 3 are needed because we will need to compute $`\overline{\widehat{g}(\psi _y)}`$ to invert $`D`$.

The parameter $`\beta `$ is describes the rank of $`D`$ and thus of $`X`$. When we apply $`X`$ followed by its pseudoinverse, we get a vector close enough to $`|s`$ so that when we measure we obtain $`s`$ with probability $`\beta `$.

Thus the overall probability of success of the algorithm is $`\alpha \beta `$.

### 2.4 Implementation of the Algorithm

We now show how to implement the algorithm efficiently on a quantum computer.

1. Setup a superposition of the all the values of $`f`$ with the amplitude of $`|x`$ equal to $`f(x)`$ to obtain

$$C\underset{xG}{}g(x+s)|x.$$
2. Compute the Fourier transform to obtain

$$C^{}\underset{yG}{}\overline{\psi _y(s)}\widehat{g}(\psi _y)|y.$$
3. Now compute $`\overline{\widehat{g}(\psi _y)}`$ into the phase to obtain

$$C^{\prime \prime }\underset{\begin{array}{c}yG\\ \widehat{g}(\psi _y)0\end{array}}{}\overline{\psi _y(s)}|y$$
4. Computing the inverse Fourier transform and measuring gives $`s`$.

In step 1 we setup a superposition over the elements of $`G`$,

$$\underset{xG}{}|x,$$

compute $`f(x)`$ and measure to see whether $`f(x)`$ is zero. If so, then the algorithm fails. If not, we are left with a superposition over all $`x`$ such that $`f(x)0`$. The algorithm succeeds here with probability $`\alpha `$. We next compute $`f(x)`$ into the amplitude of $`|x`$ (up to a constant factor) . Condition 1 ensures that we can do this by computing the phase of $`f(x)`$ into the phase of $`|x`$. We can always approximate this arbitrarily closely by approximating the phase of $`f(x)`$ to the nearest $`2^n`$th root of unity for some sufficiently large $`n`$.

Step 2 follows from observing that

$`C^{}{\displaystyle \underset{yG}{}}\left({\displaystyle \underset{xG}{}}g(x+s)\psi _y(x)\right)|y`$ $`=C^{}{\displaystyle \underset{yG}{}}\left({\displaystyle \underset{xG}{}}g(x)\psi _y(xs)\right)|y`$
$`=C^{}{\displaystyle \underset{yG}{}}\overline{\psi _y(s)}\left({\displaystyle \underset{xG}{}}g(x)\psi _y(x)\right)|y`$
$`=C^{}{\displaystyle \underset{yG}{}}\overline{\psi _y(s)}\widehat{g}(\psi _y)|y,`$
where $`C^{}`$ is a constant.

Step 3 can be performed because of Conditions 2 and 3.

In Step 4 we measure and obtain $`s`$ with probability of $`\beta `$. The reason we get $`s`$ instead of $`s`$ is that computing the inverse Fourier transform corresponds to multiplying by $`F^{}`$ instead of $`F^T`$.

Thus the algorithm succeeds in identifying $`s`$ with probability $`\alpha \beta `$ and only requires one query of $`f`$ and one query of $`\widehat{g}`$ .

## 3 The Hidden Coset Problem

If $`g`$ has a “subgroup” structure then the shift may not be unique. We can make this precise in the following way by formulating a *hidden coset problem* that combines the features of the shift problem with that of the hidden subgroup problem. The hidden coset problem is a shift problem where the shift may not be uniquely defined.

The hidden coset problem is the following. Let $`g`$ be a complex valued function defined on the group $`G`$. Let $`f`$ be a shifted version of $`g`$ where $`f(x)=g(x+s)`$ for some $`s`$ in $`G`$. Find all $`s^{}`$ satisfying $`f(x)=g(x+s^{})`$ for all $`x`$.

Let $`H`$ be the largest subgroup of $`G`$ such that $`g`$ is constant on cosets of $`H`$. Because of the structure of $`g`$, $`s`$ is determined only “modulo” $`H`$. Thus to solve the hidden coset problem, we need to first identify the hidden subgroup $`H`$ and then the shift $`s`$ modulo $`H`$.

Assuming that we have already found $`H`$, to find $`s`$ modulo $`H`$, define $`g^{}`$ and $`f^{}`$ as complex valued functions on the quotient group $`G/H`$ in the natural way so that $`g^{}(x+H)=g(x)`$ and $`f^{}(x+H)=f(x)`$ for all $`x`$ in $`G`$. Then if $`g^{}`$ satisfies the conditions in Section 2.3 when considered over the group $`G/H`$ we can apply the algorithm for the shift problem to find $`s`$ modulo $`H`$.

We now show how to find $`H`$. The standard formulation of the hidden subgroup problem assumes that $`g`$ is constant on cosets of $`H`$ and that $`g`$ takes on *distinct values on distinct cosets*. This can be solved using the “standard” algorithm

1. Prepare a superposition over all of $`G`$.
2. Computing $`g`$ into a register.
3. Fourier sampling to obtain a random element of $`H^{}`$.

The condition that $`g`$ takes on distinct values on distinct cosets of $`H`$ means that we sample uniformly over the elements of $`H^{}`$. This condition can be relaxed slightly so that the standard algorithm still works. Boneh and Lipton  and Mosca and Ekert  give the condition that $`g^{}`$ is at most $`m`$ to 1 and $`m`$ is less than the smallest prime factor of $`|H|`$, the cardinality of $`H`$. Hales and Hallgren  give the condition that at least a polylogarithmic number of values of $`g`$ need to be changed to reduce the period of $`g`$.

However, as we already have restrictions on $`g^{}`$ and $`\widehat{g}^{}`$ (so that we can solve the shift problem) we can give another condition for the hidden subgroup problem to be solved efficiently. If $`\beta `$, the fraction of values of $`\widehat{g}^{}`$ that is nonzero satisfies $`\beta >1/p+\text{poly}\mathrm{log}(|H|)`$, where $`p`$ is the smallest prime factor of $`|H|`$, then the following algorithm will find $`H`$.

1. Prepare a superposition over all of $`G`$.
2. Computing $`g`$ into the *phase*.
3. Fourier sampling to obtain a random element of $`H^{}`$.

The difference from the standard algorithm for solving the hidden subgroup problem is that we compute $`g`$ into the *phase*.

## 4 Shifted Character Problem (Finite Field)

The shifted character problem for the finite field $`𝔽_q`$ is as follows.

Given a finite field $`𝔽_q`$ (where $`q=p^m`$ for some prime $`p`$), a multiplicative character $`\chi `$ of $`𝔽_q`$ and a shifted version of $`\chi `$, $`f(x)=\chi (x+s)`$. Find $`s`$.

For a review of additive and multiplicative characters in finite fields see Appendix A. Appendix B contains a discussion of Fourier transforms over the additive group of multiplicative characters.

The shifted multiplicative character problem over a finite field fits into our general framework. The group $`G`$ is the additive group of the finite field. $`g=\chi `$ is a (non-trivial) multiplicative character of $`𝔽_q`$. We show that $`\chi `$ satisfies the sufficient conditions of Section 2.3.

1. For all nonzero $`x`$, $`\chi (x)`$ has unit magnitude.
2. $`\widehat{\chi }(\psi _0)=0`$ and as shown in Appendix B, $`\widehat{\chi }(\psi _{g^m})=\overline{\chi (g^m)}\widehat{\chi }(\psi _{g^0})`$ and so has magnitude $`|\widehat{\chi }(\psi _{g^0})|`$ which is constant.
3. $`\chi `$ and thus $`\overline{\chi (g^m)}`$ can be computed efficiently. So $`\widehat{\chi }`$ can be computed efficiently (up to a constant phase).

We next calculate the probability of our algorithm succeeding.

1. $`\chi (x)`$ is zero only if $`x=0`$ so $`\alpha =11/q`$.
2. $`\widehat{\chi }(\psi _y)`$ is zero if for $`y=0`$ so $`\beta =11/q`$.

So our algorithm succeeds with probability $`\alpha \beta =(11/q)^2`$.

## 5 Shifted Character Problem for $`/n`$

The shifted character problem for $`/n`$ is as follows.

Given a ring $`/n`$ with $`n`$ odd, a multiplicative character $`\chi `$ of $`/n`$ and a shifted version of $`\chi `$, $`f(x)=\chi (x+s)`$. Find $`s`$.

The shifted character problem over $`/n`$ has the interesting feature that the solution to the shift is not unique. This is because multiplicative characters in $`/n`$ have periodicities with respect to the additive group. See Appendix A for a discussion of periodicities of multiplicative characters. Appendix B contains a discussion of Fourier transforms of multiplicative characters.

The shifted character problem over $`/n`$ fits into the hidden coset problem framework described in Section 3 so we can apply our algorithm. If $`n=p_1^{m_1}\mathrm{}p_k^{m_k}`$ we have $`\alpha =\beta =(11/p_1)\mathrm{}(11/p_k)`$ and so our algorithm will succeed with probability $`(11/p_1)^2\mathrm{}(11/p_k)^2`$ (after solving the associated hidden subgroup problem).

## 6 Interpretation as Deconvolution

Our algorithm for solving the shift problem can be thought of solving a deconvolution problem. To see this, let $`\delta _y(x)=\delta (xy)`$ be the delta function centered at $`y`$. Then $`f`$ is the convolution of $`\delta _s`$ and $`g`$, that is

$$f=\delta _sg.$$

So to recover $`s`$ or equivalently $`\delta _s`$, we need to solve a deconvolution problem.

Taking Fourier transforms and observing that in the Fourier domain convolution becomes pointwise multiplication we see that

$$\widehat{f}=\widehat{\delta }_s\widehat{g},$$

where $`\widehat{f}`$, $`\widehat{g}`$, $`\widehat{\delta }_s`$ are the Fourier transforms of $`f`$, $`g`$ and $`\delta _s`$ respectively. We then have

$$\delta _s=^1\left(\widehat{f}/\widehat{g}\right)$$

where the division is pointwise.

For the division to be performed on efficiently on a quantum computer would require that the magnitude of $`\widehat{g}`$ be constant and non-zero. However even if a fraction of the values of $`\widehat{g}`$ are zero we can still approximate division of $`\widehat{g}`$ by only dividing when $`\widehat{g}`$ is non-zero and doing nothing otherwise.

Deconvolution is a well studied classical problem and perhaps this interpretation will enable us to leverage existing deconvolution techniques to broaden the class of problems amenable to our approach.

## 7 Conclusion

We have presented a general framework for a class of shift problems and a set of sufficient conditions for the problems to be efficiently solved on a quantum computer. However, the sufficient conditions are fairly restrictive although they include the shifted multiplicative character problem over finite fields and rings $`/n`$.

It would be of interest to investigate what other shift problems satisfy the sufficient conditions and whether a less restrictive set of sufficient conditions exists.

## 8 Acknowledgements

I would like to thank Umesh Vazirani for much appreciated advice and encouragement and Sean Hallgren and Wim van Dam for useful discussions.

## 9 Bibliography

## Appendix A Mathematical Background

We start with some definitions and background. For more details see the book by Lidl and Niederreiter , and the book by Tolimieri et al. .

### A.1 Characters of a Group

A character $`\chi `$ of a finite abelian group $`G`$ is a homomorphism from a group $`G`$ to $`(,\times )`$, the group of complex numbers with multiplication. That is

$$\chi (g_1g_2)=\chi (g_1)\chi (g_2)$$

for all $`g_1,g_2G`$. If $`G`$ is cyclic with generator $`g`$, the characters are

$$\chi _k(g^l)=\mathrm{exp}(2\pi ikl/|G|)$$

for $`k=0,\mathrm{},|G|1`$.

The characters of $`G`$ form a group $`\widehat{G}`$, known as the dual group, with multiplication defined as

$$(\chi _1\chi _2)(g)=\chi _1(g)\chi _2(g)$$

for all $`\chi _1,\chi _2\widehat{G}`$, $`gG`$. $`\widehat{G}`$ is isomorphic to $`G`$. In particular, $`|\widehat{G}|=|G|`$, that is the number of characters of $`G`$ is the same as the cardinality of $`G`$.

### A.2 Fourier Transform over a Group

Given a complex valued function $`f`$ over $`G`$, the Fourier transform of $`f`$ over the group $`G`$ is given by

$$\widehat{f}(\chi )=\underset{gG}{}f(g)\chi (g)$$

for all $`\chi \widehat{G}`$.

### A.3 Characters of a Field

In a field $`𝔽_q`$ (where $`q=p^m`$ for some prime $`p`$) we have two operations, multiplication and addition, with corresponding groups. Thus we can define two different groups of characters.

Characters of the multiplicative group $`𝔽_q^{}`$ of $`𝔽_q`$ are called *multiplicative characters* of $`𝔽_q`$. Since $`𝔽_q^{}`$ is cyclic with order $`q1`$, its characters $`\chi _0,\mathrm{}\chi _{q2}`$ can be explicitly represented as

$$\chi _k(g^l)=\mathrm{exp}\left(\frac{2\pi ikl}{q1}\right)$$

for all $`l=0,1,\mathrm{},q2`$, where $`g`$ is a generator of $`𝔽_q^{}`$. It is often convenient to extend the definition of $`\chi _k`$ to include 0 by defining $`\chi _k(0)=0`$. The quadratic character referred to in van Dam and Hallgren  is $`\chi _{\frac{q1}{2}}`$.

Characters of the additive group of $`𝔽_q`$ are called *additive characters* of $`𝔽_q`$. The additive characters $`\psi _a`$ (for all $`a𝔽_q`$) have the form

$$\psi _a(c)=\mathrm{exp}\left(\frac{2\pi i\mathrm{Tr}(ac)}{p}\right)$$

for all $`c𝔽_q`$, where

$$\mathrm{Tr}(x)=\underset{k=0}{\overset{m1}{}}x^{p^k}$$

is the trace function from $`𝔽_q`$ to $`𝔽_p`$ and $`𝔽_p`$ is identified with $`/p`$ for the purposes of evaluating the exponential. $`\psi _1`$ is the canonical additive character of $`𝔽_q`$. We have that $`\psi _a(c)=\psi _1(ac)`$.

### A.4 Characters of $`/n`$

Similarly we can define additive and multiplicative characters in $`/p^m`$ where $`p`$ is an odd222We only consider odd $`p`$ because $`(/2^m)^{}`$ is not cyclic for $`m3`$. In fact, $`(/2^m)^{}`$ is the product of two cyclic groups . prime. $`/p^m`$ with addition is a cyclic group so we can define additive characters $`\psi _0,\mathrm{},\psi _{p^m1}`$

$$\psi _k(x)=\mathrm{exp}\left(\frac{2\pi ikx}{p^m}\right)$$

for all $`x/p^m`$.

$`(/p^m)^{}`$ is a cyclic group, so we can define multiplicative characters $`\chi _0,\mathrm{},\chi _{(p1)p^{m1}1}`$, where

$$\chi _k(g^l)=\mathrm{exp}\left(\frac{2\pi ikl}{(p1)p^{m1}}\right)$$

for all $`l=0,1,\mathrm{},(p1)p^{m1}1`$ and $`g`$ is a generator of $`(/p^m)^{}`$. We can extend the definition of $`\chi _k`$ to include all of $`/p^m`$ by defining $`\chi _k(x)=0`$ if $`x`$ is a multiple of $`p`$.

$`/n`$ with addition is a cyclic group so we can define additive characters $`\psi _0,\mathrm{},\psi _{n1}`$

$$\psi _k(x)=\mathrm{exp}\left(\frac{2\pi ikx}{n}\right)$$

for all $`x/n`$.

If $`n`$ is odd, we can define multiplicative characters over $`/n`$ by observing that if $`n=p_1^{m_1}\mathrm{}p_k^{m_k}`$ then

$$/n/p_1^{m_1}\mathrm{}/p_k^{m_k}.$$

Let $`\varphi `$ be an isomorphism from $`/n`$ to $`/p_1^{m_1}\mathrm{}/p_k^{m_k}`$ with $`\varphi (x)=(\varphi _1(x),\mathrm{},\varphi _k(x))`$ given by $`\varphi _j(x)=xmodp_j^{m^j}`$. Define the multiplicative characters as the product of the multiplicative characters in the corresponding $`/p_j^{m_j}`$. That is

$$\chi _{l_1,\mathrm{},l_k}(x)=\underset{r=1}{\overset{k}{}}\chi _{l_r}^{(r)}(\varphi _r(x)),$$

where $`\chi _{l_r}^{(r)}`$ is a multiplicative character of $`/p_r^{m_r}`$. Noting that all the $`\chi _{l_1,\mathrm{},l_k}`$ are distinct for appropriate ranges of $`l_1,\mathrm{},l_k`$ and that there are exactly the right number of them we see that we have all the multiplicative characters.

### A.5 Periodicities of Multiplicative Characters of $`/p^m`$

The multiplicative characters of $`/p^m`$ have a particular *additive* periodic structure. Every multiplicative character has a period that is a power of $`p`$. That is, for every $`k`$, there is a $`j`$ such that

$$\chi _k(x+p^j)=\chi _k(x)$$

for all $`x/p^m`$.

In fact we have the following theorem  that explicitly gives the period.

###### Theorem 1

Let $`g`$ be a generator of the group of units $`(/p^m)^{}`$ and let $`\chi _k`$ be a multiplicative character of $`/p^m`$ defined

$$\chi _k(x)=\{\begin{array}{cc}0\hfill & \text{if }p|x,\hfill \\ \mathrm{exp}\left(\frac{2\pi ikl}{(p1)p^{m1}}\right)\hfill & \text{if }x=g^l.\hfill \end{array}$$

Let $`j`$ be such that $`\mathrm{gcd}(p^m,k)=p^{mj}`$. Then $`p^j`$ is the additive period of $`\chi _k`$, the smallest $`T`$ such that $`\chi _k(x+T)=\chi _k(x)`$ for all $`x/p^m`$.

Proof: Suppose $`\mathrm{gcd}(p^m,k)=p^{mj}`$ and that the period of $`\chi _k`$ is $`T`$. We first show that $`T|p^j`$ and then that $`T=p^j`$.

If $`p|x`$ then $`p|(x+p^j)`$ and so $`\chi _k(x+p^j)=0=\chi _k(x)`$. If $`x=g^l`$ then because $`p^{mj}|k`$, the value of $`\chi _k(g^l)`$ is determined by the value of $`lmod(p1)p^{j1}`$, which is in turn determined by the value of $`g^lmodp^j`$. But $`g^l+p^jg^lmodp^j`$ and so $`\chi _k(x+p^j)=\chi _k(x)`$. This shows that $`T|p^j`$.

Since $`T|p^j`$, if $`Tp^j`$, we must have $`T=p^j^{}`$ for some $`j^{}<j`$. Then $`\chi _k(1)=\chi _k(1+rp^j^{})`$ for all $`r=0,\mathrm{},p^{mj^{}}1`$. Now

$$\{1+rp^j^{}:r=0,\mathrm{},p^{mj^{}}1\}=\{g^{(p1)p^{j^{}1}l^{}}:l^{}=0,\mathrm{},p^{mj^{}}1\}$$

since all the $`g^{(p1)p^{j^{}1}l^{}}`$ are distinct and $`g^{(p1)p^{j^{}1}l^{}}1modp^j^{}`$. But $`\chi _k(g^{(p1)p^{j^{}1}l^{}})=1`$ for all $`l^{}`$ only if $`k(p1)p^{j^{}1}`$ is a multiple of $`(p1)p^{m1}`$ which implies that $`p^{mj^{}}|k`$. This is a contradiction since $`p^{mj}`$ was the largest power of $`p`$ dividing $`k`$. Thus $`T=p^j`$.  $`\mathrm{}`$

### A.6 Periodicities of Multiplicative Characters of $`/n`$

As we saw in Appendix A.4, a multiplicative character $`\chi _{l_1,\mathrm{},l_k}`$ of $`/n`$ can be decomposed into a product of multiplicative characters $`\chi _{l_1}^{(1)}\mathrm{}\chi _{l_k}^{(k)}`$ of $`/p_1^{m_1},\mathrm{},/p_k^{m_k}`$. The period of $`\chi _{l_1,\mathrm{},l_k}`$ is then the product of the periods of $`\chi _{l_1}^{(1)}\mathrm{}\chi _{l_k}^{(k)}`$.

## Appendix B Fourier Transforms of Multiplicative Characters

### B.1 Finite Field Case

Consider the natural representation of $`𝔽_q^{}`$, the multiplicative group. It is well known that this is cyclic. If $`g`$ is a generator then the elements can be represented as $`\{1,g,g^2,g^3,\mathrm{},g^{q2}\}`$. The multiplicative characters are then exponentials in $`k`$

$$\chi _l(g^k)=\mathrm{exp}\left(\frac{2\pi ikl}{q1}\right).$$

The non-trivial additive characters can be written

$$\psi _{g^m}(g^k)=\mathrm{exp}\left(\frac{2\pi i\text{Tr}(g^mg^k)}{p}\right).$$

Note that these are all translates of the canonical additive character

$$\psi _{g^0}(g^k)=\mathrm{exp}\left(\frac{2\pi i\text{Tr}(g^k)}{p}\right).$$

When we take the Fourier transform of a multiplicative character over the additive group we are expressing an exponential in terms of a basis where the basis functions are translates of the canonical additive character. To compute the change of basis we compute the inner product of the exponential with all the translates of the canonical additive character. This is the same as the inner product of the canonical additive characters with the exponential translated in the opposite direction. But a translated exponential is just the original exponential with a phase shift that is given by the exponential of the size of the translation. Thus

$`\widehat{\chi }_l(\psi _{g^m})`$ $`={\displaystyle \underset{k=0}{\overset{q2}{}}}\psi _{g^m}(g^k)\chi _l(g^k)`$
$`={\displaystyle \underset{k=0}{\overset{q2}{}}}\mathrm{exp}\left({\displaystyle \frac{2\pi i\text{Tr}(g^mg^k)}{p}}\right)\mathrm{exp}\left({\displaystyle \frac{2\pi ikl}{q1}}\right)`$
$`={\displaystyle \underset{k=0}{\overset{q2}{}}}\mathrm{exp}\left({\displaystyle \frac{2\pi i(km)l}{q1}}\right)\mathrm{exp}\left({\displaystyle \frac{2\pi i\text{Tr}(g^k)}{p}}\right)`$
$`=\mathrm{exp}\left({\displaystyle \frac{2\pi iml}{q1}}\right)\widehat{\chi }_l(\psi _{g^0})`$
$`=\overline{\chi _l(g^m)}\widehat{\chi }_l(\psi _{g^0}).`$
### B.2 $`/p^m`$ Case

If a multiplicative character $`\chi _l`$ of $`/p^m`$ has no periodicity, then $`pl`$. An extension of the argument used for the finite field case shows that

$$\widehat{\chi }_l(\psi _y)=\overline{\chi _l(y)}\widehat{\chi }_l(\psi _1).$$

See Tolimieri et al. for details . If $`\mathrm{gcd}(p^m,l)=p^{mj}`$, $`\chi _l`$ has period $`p^l`$ and the previous argument does not work because $`p^m`$, the size of the additive group, and $`l`$ are not relatively prime. However, by projecting $`/p^m`$ onto $`/p^j`$ by sending $`x`$ to $`xmodp^j`$ we transform $`\chi _l`$ to a multiplicative character of $`/p^j`$ with no periodicity. Thus the Fourier transform of $`\chi _l`$ over $`/p^m`$ must be

$$\widehat{\chi }_l(\psi _y)=\{\begin{array}{cc}K\overline{\chi _l(y/p^{mj})}\hfill & \text{if }p^{mj}|y,\hfill \\ 0\hfill & \text{if }p^{mj}y,\hfill \end{array}$$

for some constant $`K`$.

### B.3 $`/n`$ Case

Given a multiplicative character of $`/n`$, $`\chi _{l_1,\mathrm{},l_k}`$ the vector with component $`x`$ equal to $`\chi _{l_1,\mathrm{},l_k}(x)`$ is equal to the tensor product of the corresponding vectors of the $`\chi _{l_1}^{(1)},\mathrm{},\chi _{l_k}^{(k)}`$.

The Fourier transform of $`\chi _{l_1,\mathrm{},l_k}`$ will then be the tensor product of the Fourier transforms of the $`\chi _{l_1}^{(1)},\mathrm{},\chi _{l_k}^{(k)}`$. So if the period of $`\chi _{l_1,\mathrm{},l_k}`$ is $`T`$, the Fourier transform of $`\chi _{l_1,\mathrm{},l_k}`$ is

$$\widehat{\chi }_{l_1,\mathrm{},l_k}(\psi _y)=\{\begin{array}{cc}K\overline{\chi _{l_1,\mathrm{},l_k}(y/T)}\hfill & \text{if }T|y,\hfill \\ 0\hfill & \text{if }Ty,\hfill \end{array}$$

for some constant $`K`$.