text:
# The Energy-Momentum Tensor in Noncommutative Gauge Field Models

## 1 Introduction

In a previous paper  we have analyzed the energy-momentum tensor on noncommutative spaces and we have found that the dilation symmetry is broken due to the presence of the deformation parameter $`\theta ^{\mu \nu }`$ characterizing the noncommutative geometry by

$$[\widehat{x}^\mu ,\widehat{x}^\nu ]=i\theta ^{\mu \nu }.$$
(1)
The existence of a constant, fixed antisymmetric tensor field $`\theta ^{\mu \nu }`$ clearly also breaks the Lorentz symmetry , ,  if $`\theta ^{\mu \nu }`$ does not have a tensorial transformation behaviour with respect to Lorentz transformations. This situation resembles in some sense the axial gauge in gauge field models. There, the presence of the constant, fixed gauge ‘direction’ $`n^\mu `$ breaks the Lorentz invariance, too .
In particular, the occurence of $`\theta ^{\mu \nu }`$ in noncommutative quantum field models induces that the corresponding energy-momentum tensor needs neither be symmetric (for massless models), nor traceless.
The aim of the present work is the investigation of the construction of the energy-momentum tensor in massless and commutative gauge field models and their noncommutative counterparts, in order to work out the different aspects of the stress tensor for both cases.
Generally, the usual Noether procedure for the construction of the canonical energy-momentum tensor in the worst case needs an improvement procedure and the Belinfante trick , ,  in order to get a symmetric and traceless stress tensor. However, due to the idea of Jackiw , , , there is a more direct method to get the correct stress tensor by combining the Noether procedure translations with field dependent gauge transformations.
The paper is organized as follows. In section 2 we demonstrate the power of Jackiw’s recipe for the construction of the energy-momentum tensor for a general $`U(N)`$ non-Abelian gauge field model. Both quantities, the canonical stress tensor and the symmetric one will be discussed in defining appropriate Ward-identity operators  for the description of infinitesimal translations. Additionally, the commutative Yang-Mills model is also characterized by the gauge symmetry implying the existence of a conserved gauge current.
Section 3 is devoted to the discussion of the energy-momentum tensor for noncommutative non-Abelian gauge field models. The methods used for the commutative case can be applied without any difficulties also to the noncommutative counterpart. The results obtained in section 3 are very similar to the corresponding output of the commutative case. However, there is a severe difference: The stress tensors are no longer locally conserved due to the fact that cyclic rotation of Moyal products occuring in the stress tensors is locally impossible. After all, the symmetric version of the energy-momentum tensor is locally covariantly conserved with respect to the covariant derivative of the gauge symmetry.
In sections 4 and 5 we discuss the influence of the so called Seiberg-Witten map on the construction of gauge invariant actions and the corresponding stress tensors. In section 4 we treat the noncommutative non-Abelian field model obtained via the Seiberg-Witten map to lowest order in $`\theta ^{\mu \nu }`$ . Section 5 discusses the special case of the $`\theta `$-deformed Maxwell theory ($`U(1)`$). The construction of the symmetric energy-momentum tensor confirms a recent result obtained by Kruglov .
All investigations are done in the classical approximation without radiative corrections.

## 2 Energy-Momentum Tensor in Ordinary
Yang-Mills Theory

In order to demonstrate the various possible constructions (canonical form, Belinfante procedure, construction modulo a gauge transformation) of the energy-momentum tensor , , , , , let us start with a commutative Yang-Mills model, where the gauge field is matrix-valued, $`A_\mu =A_\mu ^aX^a`$, $`X^a`$ being the corresponding generators of the gauge group $`U(N)`$.
The corresponding infinitesimal gauge transformation is given by

$$\delta _\lambda A_\mu =_\mu \lambda i[A_\mu ,\lambda ]=:D_\mu \lambda ,$$
(2)
implying that the non-Abelian field strength

$$F_{\mu \nu }=_\mu A_\nu _\nu A_\mu i[A_\mu ,A_\nu ]$$
(3)
transforms covariantly,

$$\delta _\lambda F_{\mu \nu }=i[\lambda ,F_{\mu \nu }].$$
(4)
Therefore, the gauge invariant non-Abelian action is given by

$$\mathrm{\Gamma }_{inv}[A]=\frac{1}{4}d^4xtr\left(F_{\mu \nu }F^{\mu \nu }\right)=:\frac{1}{4}d^4xtrF^2$$
(5)
The equation of motion for the gauge field is

$`{\displaystyle \frac{\delta }{\delta A_\nu }}\mathrm{\Gamma }_{inv}[A]=D_\rho F^{\rho \nu }=0.`$ (6)
The symmetry transformation (2) may be expressed by the global Ward-identity (WI)-operator

$$W^G(\lambda )=d^4xtrD_\mu \lambda (x)\frac{\delta }{\delta A_\mu (x)}.$$
(7)
Gauge invariance is stated through $`W^G(\lambda )\mathrm{\Gamma }_{inv}=0.`$ This implies the following local identity for the gauge symmetry,

$$\frac{\delta }{\delta \lambda (x)}W^G(\lambda )\mathrm{\Gamma }_{inv}=0.$$
(8)
This defines the locally conserved current for the gauge symmetry,

$$j_G^\mu =i[A_\rho ,F^{\rho \mu }],_\mu j_G^\mu =i_\mu [A_\rho ,F^{\rho \mu }]=0.$$
(9)
By direct computation and by use of the equation of motion one easily verifies (9).
Now we want to discuss the infinitesimal translation described by the following global WI-operator,

$$W_\mu ^T=d^4xtr_\mu A_\nu (x)\frac{\delta }{\delta A_\nu (x)}.$$
(10)
By applying the WI-operator (10) to the gauge invariant action one gets the canonical energy-momentum tensor due to translational invariance,

$`W_\mu ^T\mathrm{\Gamma }_{inv}`$ $`=`$ $`{\displaystyle d^4xtr\left(^\rho (\frac{1}{2}\{F_{\rho \nu },_\mu A^\nu \}\frac{1}{4}g_{\rho \mu }F^2)\right)}`$ (11)
$`=`$ $`{\displaystyle d^4x^\rho T_{\rho \mu }^c}=0.`$
Thus, the canonical energy-momentum tensor is defined as

$$T_{\rho \mu }^c:=tr\left(\frac{1}{2}\{F_{\rho \nu },_\mu A^\nu \}\frac{1}{4}g_{\rho \mu }F^2\right).$$
(12)
It is simple to show that $`T_{\rho \mu }^c`$ is locally conserved by using the equation of motion.
However, $`T_{\rho \mu }^c`$ is not gauge invariant, not traceless and not symmetric in $`(\rho ,\mu )`$. In order to obtain a symmetric stress tensor one has two possibilities , . Here we follow the method proposed originally by R. Jackiw  in using an alternative representation for infinitesimal translations. Modulo a field dependent gauge transformation a possible description of translations is given by

$$W_\mu ^F=d^4xtrF_{\mu \nu }(x)\frac{\delta }{\delta A_\nu (x)},$$
(13)
leading to

$`W_\mu ^F\mathrm{\Gamma }_{inv}`$ $`=`$ $`{\displaystyle d^4xtr\left(^\rho (\frac{1}{2}\{F_{\rho \nu },F_\mu ^\nu \}\frac{1}{4}g_{\rho \mu }F^2)\right)}`$ (14)
$`=`$ $`{\displaystyle d^4x^\rho T_{\rho \mu }^s}=0,`$
where $`T_{\rho \mu }^s`$ is gauge invariant, symmetric and traceless,

$$T_{\rho \mu }^s:=tr\left(\frac{1}{2}\{F_{\rho \nu },F_\mu ^\nu \}\frac{1}{4}g_{\rho \mu }F^2\right).$$
(15)
One observes that the Jackiw construction unifies the Belinfante and improvement procedure.
Using the splitting

$$F_{\mu \nu }=_\mu A_\nu _\nu A_\mu i[A_\mu ,A_\nu ]=_\mu A_\nu D_\nu A_\mu ,$$
(16)
one gets for the canonical tensor

$$T_{\rho \mu }^c=tr\left(\frac{1}{2}\{F_{\rho \nu },F_\mu ^\nu +D^\nu A_\mu \}\frac{1}{4}g_{\rho \mu }F^2\right),$$
(17)
implying that the difference between the canonical tensor and the symmetric one becomes

$$T_{\rho \mu }^cT_{\rho \mu }^s=\frac{1}{2}tr\{F_{\rho \nu },D^\nu A_\mu \}.$$
(18)
Due to the fact that the WI-operator of the translation is represented by

$$W_\mu ^T=W_\mu ^F+W_\mu ^G=d^4xtr\left(F_{\mu \nu }(x)\frac{\delta }{\delta A_\nu (x)}+D_\nu A_\mu (x)\frac{\delta }{\delta A_\nu (x)}\right),$$
(19)
the field dependent gauge transformation corresponds to the difference $`T_{\rho \mu }^cT_{\rho \mu }^s`$,

$`W_\mu ^G\mathrm{\Gamma }_{inv}`$ $`=`$ $`{\displaystyle d^4xtr\left(D_\nu A_\mu (x)\frac{\delta \mathrm{\Gamma }_{inv}}{\delta A_\nu (x)}\right)}`$ (20)
$`=`$ $`{\displaystyle d^4xtr_\rho \left(\frac{1}{2}\{F_{\rho \nu },D^\nu A_\mu \}\right)}.`$
This is easily checked by explicit calculation with the use of partial integration,

$`W_\mu ^G\mathrm{\Gamma }_{inv}`$ $`=`$ $`{\displaystyle d^4xtrD_\nu A_\mu D_\rho F^{\rho \nu }}`$ (21)
$`=`$ $`{\displaystyle d^4xtr\left(^\rho (\frac{1}{2}\{F_{\rho \nu },D^\nu A_\mu \})D_\rho D_\nu A_\mu F^{\rho \nu }\right)}.`$
With the antisymmetry of $`F^{\rho \nu }`$ the second term is easily shown to vanish. This is very similar to the construction of the stress tensor of the Maxwell theory . Another interesting comment has to be made. If we omit the $`tr`$ symbol in the definition of the energy momentum tensor $`T_{\rho \mu }^s`$,

$$T_{\rho \mu }^s:=\left(\frac{1}{2}\{F_{\rho \nu },F_\mu ^\nu \}\frac{1}{4}g_{\rho \mu }F^2\right),$$
(22)
we get an object which is (due to the equation of motion and the Bianchi identity) $`covariantly`$ conserved,

$$D^\rho T_{\rho \mu }^s=0.$$
(23)
In discussing the noncommutative counterpart we will find that a similar ‘covariant conservation’ is also valid there. With (23) one finds

$$^\rho T_{\rho \mu }^s=i[A^\rho ,T_{\rho \mu }^s],$$
(24)
which is consistent with

$$W_\mu ^F\mathrm{\Gamma }_{inv}=d^4xtr(^\rho T_{\rho \mu }^s)=0.$$
(25)
## 3 Energy-Momentum Tensor in Noncommutative
Yang-Mills Theory

It is now straigthforward to discuss also the noncommutative structure in the spirit of the considerations done in the previous section. In noncommutative gauge field models one has to replace all field products by $``$-products  and one introduces the noncommutative matrix valued gauge field $`\widehat{A}`$. The corresponding gauge invariant action is therefore

$$\widehat{\mathrm{\Gamma }}_{inv}[\widehat{A}]=\frac{1}{4}d^4xtr\left(\widehat{F}_{\mu \nu }\widehat{F}^{\mu \nu }\right),$$
(26)
with the noncommutative field strength

$$\widehat{F}_{\mu \nu }=_\mu \widehat{A}_\nu _\nu \widehat{A}_\mu i[\widehat{A}_\mu ,\widehat{A}_\nu ]_M.$$
(27)
Here the Moyal commutator is given by

$$[\widehat{A}_\mu ,\widehat{A}_\nu ]_M:=\widehat{A}_\mu \widehat{A}_\nu \widehat{A}_\nu \widehat{A}_\mu ,$$
(28)
using the $``$-product,

$$A(x)B(x)=e^{\frac{i}{2}\theta ^{\mu \nu }_\mu ^\xi _\nu ^\eta }A(x+\xi )B(x+\eta )|_{\xi =\eta =0}.$$
(29)
The infinitesimal gauge transformation is defined as

$$\delta _{\widehat{\lambda }}\widehat{A}_\mu =_\mu \widehat{\lambda }i[\widehat{A}_\mu ,\widehat{\lambda }]_M=:\widehat{D}_\mu \widehat{\lambda },$$
(30)
where $`\widehat{\lambda }`$ is the noncommutative counterpart of $`\lambda `$ of equation (2) The equation of motion for the gauge field is then

$`{\displaystyle \frac{\delta }{\delta \widehat{A}_\nu }}\widehat{\mathrm{\Gamma }}_{inv}[\widehat{A}]=\widehat{D}_\rho \widehat{F}^{\rho \nu }=0,`$ (31)
and for the locally conserved gauge current we get

$$\widehat{j}_G^\mu =i[\widehat{A}_\rho ,\widehat{F}^{\rho \mu }]_M.$$
(32)
At the level of noncommutative gauge field models one can perform the same steps as in the previous section. With

$`\widehat{W}_\mu ^T\widehat{\mathrm{\Gamma }}_{inv}`$ $`=`$ $`{\displaystyle \frac{1}{2}}{\displaystyle d^4xtr\left(_\mu \widehat{A}_\nu (x)\frac{\delta \widehat{\mathrm{\Gamma }}_{inv}}{\delta \widehat{A}_\nu (x)}+\frac{\delta \widehat{\mathrm{\Gamma }}_{inv}}{\delta \widehat{A}_\nu (x)}_\mu \widehat{A}_\nu (x)\right)}`$ (33)
$`=`$ $`{\displaystyle d^4xtr\left(^\rho (\frac{1}{2}\{\widehat{F}_{\rho \nu },_\mu \widehat{A}^\nu \}_M\frac{1}{4}g_{\rho \mu }\widehat{F}_{\alpha \beta }\widehat{F}^{\alpha \beta })\right)}`$
we find

$$\widehat{T}_{\rho \mu }^c=\left(\frac{1}{2}\{\widehat{F}_{\rho \nu },_\mu \widehat{A}^\nu \}_M\frac{1}{4}g_{\rho \mu }\widehat{F}_{\alpha \beta }\widehat{F}^{\alpha \beta }\right).$$
(34)
Analogously we have

$`\widehat{W}_\mu ^F\widehat{\mathrm{\Gamma }}_{inv}`$ $`=`$ $`{\displaystyle \frac{1}{2}}{\displaystyle d^4xtr\left(\widehat{F}_{\mu \nu }(x)\frac{\delta \widehat{\mathrm{\Gamma }}_{inv}}{\delta \widehat{A}_\nu (x)}+\frac{\delta \widehat{\mathrm{\Gamma }}_{inv}}{\delta \widehat{A}_\nu (x)}\widehat{F}_{\mu \nu }(x)\right)}`$ (35)
$`=`$ $`{\displaystyle d^4xtr\left(^\rho (\frac{1}{2}\{\widehat{F}_{\rho \nu },\widehat{F}_\mu ^\nu \}_M\frac{1}{4}g_{\rho \mu }\widehat{F}_{\alpha \beta }\widehat{F}^{\alpha \beta })\right)}`$
and

$$\widehat{T}_{\rho \mu }^s:=\left(\frac{1}{2}\{\widehat{F}_{\rho \nu },\widehat{F}_\mu ^\nu \}_M\frac{1}{4}g_{\rho \mu }\widehat{F}_{\alpha \beta }\widehat{F}^{\alpha \beta }\right).$$
(36)
Here $`\{,\}_M`$ represents the Moyal anti-commutator in the sense of (28). Note that in order to define ‘local’ quantities, $`d^4xtr`$—the integration over space-time and the trace over the colour indices—cannot be seperated in noncommutative geometry. After all, (36) is symmetric, traceless and transforms covariantly with respect to (30),. It is also locally $`covariantly`$ conserved,

$$\widehat{D}^\rho \widehat{T}_{\rho \mu }^s=0.$$
(37)
This is shown with the help of the equation of motion and the noncommutative analogon to the Bianchi-identity. We find that the energy-momentum tensors are not locally conserved111Even a ‘formal’ definition of the tensors including the $`tr`$-symbol does not help, since the trace of a Moyal commutator is $`not`$ vanishing locally.,

$$^\rho \widehat{T}_{\rho \mu }^s0^\rho \widehat{T}_{\rho \mu }^c,$$
(38)
which is already known from the works , .

## 4 Enery-Momentum Tensor
via Seiberg-Witten Map

Another possibility to formulate noncommutative gauge field models is based on the fact that one can use the so called Seiberg-Witten (SW-)map , , . This map ensures the gauge equivalence between an ordinary gauge field and its noncommutative counterpart. It implies that the noncommutative gauge field $`\widehat{A}_\mu `$ and also $`\widehat{F}_{\mu \nu }`$ can be expanded in a series in the deformation parameter $`\theta ^{\mu \nu }`$ of the noncommutative space-time geometry, with coefficients depending on the ordinary gauge field. This section discusses the translation invariance of the SW-expansion of the noncommutative $`U(N)`$-Yang Mills (NCYM-)theory. The starting point is equation (26).

$$\widehat{\mathrm{\Gamma }}_{inv}[\widehat{A}]=\frac{1}{4}d^4xtr\left(\widehat{F}_{\mu \nu }\widehat{F}^{\mu \nu }\right).$$
(39)
The SW-map to lowest order in $`\theta ^{\mu \nu }`$ for the noncommutative gauge field is

$$\widehat{A}_\mu =A_\mu \frac{1}{4}\theta ^{\rho \sigma }\{A_\rho ,_\sigma A_\mu +F_{\sigma \mu }\},$$
(40)
implying the following field strength expansion

$$\widehat{F}_{\mu \nu }=F_{\mu \nu }+\frac{1}{4}\theta ^{\rho \sigma }\left(2\{F_{\mu \rho },F_{\nu \sigma }\}\{A_\rho ,D_\sigma F_{\mu \nu }+_\sigma F_{\mu \nu }\}\right).$$
(41)
For the ordinary (commutative, Lie-algebra valued) field $`A_\mu `$ and field strength $`F_{\mu \nu }`$ the corresponding gauge transformations are given by (2) and (4), respectively.
Expanding the $``$-product in (26) we have ,

$`\mathrm{\Gamma }_{inv}^\theta [A]`$ $`=`$ $`{\displaystyle d^4xtr\left(\frac{1}{4}F_{\mu \nu }F^{\mu \nu }\frac{1}{2}\theta ^{\alpha \beta }(F_{\mu \alpha }F_{\nu \beta }F^{\mu \nu }\frac{1}{4}F_{\alpha \beta }F^2)\right)}+𝒪(\theta ^2)`$ (42)
$`=`$ $`{\displaystyle d^4xtr_{inv}^\theta }+𝒪(\theta ^2).`$
The corresponding equation of motion is

$`D_\rho \mathrm{\Pi }^{\rho \nu }`$ $`=`$ $`D_\rho (F^{\rho \nu }{\displaystyle \frac{1}{4}}(\theta ^{\rho \nu }F_{\alpha \beta }F^{\alpha \beta }+\{F^{\rho \nu },\theta ^{\alpha \beta }F_{\alpha \beta }\})`$ (43)
$`+{\displaystyle \frac{1}{2}}(\{\theta ^{\nu \beta }F_{\alpha \beta },F^{\rho \alpha }\}\{\theta ^{\rho \beta }F_{\alpha \beta },F^{\nu \alpha }\}+\{F_\alpha ^\rho ,\theta ^{\alpha \beta }F_\beta ^\nu \}))`$
$`=`$ $`0.`$
The quantity $`\mathrm{\Pi }^{\rho \nu }`$ is antisymmetric,

$$\mathrm{\Pi }^{\rho \nu }=\mathrm{\Pi }^{\nu \rho }=\frac{_{inv}^\theta }{(_\rho A_\nu )},$$
(44)
and $`\mathrm{\Pi }^{\rho 0}`$ is the canonical momentum. The analogous calculations as in section 1 give now

$`W_\mu ^T\mathrm{\Gamma }_{inv}^\theta `$ $`:=`$ $`{\displaystyle d^4xtr_\mu A_\nu (x)\frac{\delta \mathrm{\Gamma }_{inv}^\theta }{\delta A_\nu (x)}}`$ (45)
$`=`$ $`{\displaystyle d^4xtr\left(^\rho (\frac{1}{2}\{\mathrm{\Pi }_{\rho \nu },_\mu A^\nu \}+g_{\rho \mu }_{inv}^\theta )\right)}`$
$`=`$ $`{\displaystyle d^4x^\rho T_{\rho \mu }^{c,\theta }}=0.`$
Thus, the canonical energy-momentum tensor becomes

$$T_{\rho \mu }^{c,\theta }:=tr\left(\frac{1}{2}\{\mathrm{\Pi }_{\rho \nu },_\mu A^\nu \}g_{\rho \mu }_{inv}^\theta \right).$$
(46)
Similarly, one gets

$`W_\mu ^F\mathrm{\Gamma }_{inv}^\theta `$ $`=`$ $`{\displaystyle d^4xtrF_{\mu \nu }(x)\frac{\delta \mathrm{\Gamma }_{inv}^\theta }{\delta A_\nu (x)}}`$ (47)
$`=`$ $`{\displaystyle d^4xtr\left(^\rho (\frac{1}{2}\{\mathrm{\Pi }_{\rho \nu },F_\mu ^\nu \}+g_{\rho \mu }_{inv}^\theta )\right)}`$
$`=`$ $`{\displaystyle d^4x^\rho T_{\rho \mu }^{s,\theta }}=0,`$
implying the following definition,

$$T_{\rho \mu }^{s,\theta }:=tr\left(\frac{1}{2}\{\mathrm{\Pi }_{\rho \nu },F_\mu ^\nu \}g_{\rho \mu }_{inv}^\theta \right).$$
(48)
Both currents (46) and (48) are locally conserverd,

$$^\rho T_{\rho \mu }^{c,\theta }=^\rho T_{\rho \mu }^{s,\theta }=0,$$
(49)
and they are related by a Belinfante like procedure

$`T_{\rho \mu }^{s,\theta }`$ $`=`$ $`T_{\rho \mu }^{c,\theta }+tr\left(D^\nu (A_\mu \mathrm{\Pi }_{\rho \nu })\right)`$ (50)
$`=`$ $`T_{\rho \mu }^{c,\theta }+^\nu \chi _{[\nu \rho ]\mu }.`$
One observes that both versions of the enery-momentum tensor are neither symmetric nor traceless. This is due to the fact that the Lorentz invariance and the dilation symmetry are no longer maintained . However, one has to stress that $`T_{\rho \mu }^{s,\theta }`$ is invariant with respect to infinitesimal gauge transformations (2).

## 5 The $`U(1)`$-case: $`\theta `$-deformed Maxwell theory

The most simple, but still interesting, case of a $`\theta `$-expanded gauge theory is the $`U(1)`$-NCYM-theory, the $`\theta `$-deformed Maxwell theory (without sources). One just replaces in the expressions derived in the previous section the matrix-valued $`U(N)`$ gauge field $`A^aX^a`$ by the ordinary photon field. Omitting the trace symbols we get

$`\mathrm{\Gamma }_{inv}^\theta [A]`$ $`=`$ $`{\displaystyle d^4x\left(\frac{1}{4}F_{\mu \nu }F^{\mu \nu }\frac{1}{2}\theta ^{\alpha \beta }(F_{\mu \alpha }F_{\nu \beta }F^{\mu \nu }\frac{1}{4}F_{\alpha \beta }F^2)\right)}+𝒪(\theta ^2)`$ (51)
$`=`$ $`{\displaystyle d^4x_{inv}^\theta }+𝒪(\theta ^2).`$
Again, with the canonical momentum,

$`\mathrm{\Pi }^{\rho \nu }`$ $`=`$ $`{\displaystyle \frac{_{inv}^\theta }{(_\rho A_\nu )}}=F^{\rho \nu }+{\displaystyle \frac{1}{4}}(\theta ^{\rho \nu }F_{\alpha \beta }F^{\alpha \beta })+{\displaystyle \frac{1}{2}}F^{\rho \nu }\theta ^{\alpha \beta }F_{\alpha \beta }`$ (52)
$`(\theta ^{\nu \beta }F_{\alpha \beta }F^{\rho \alpha }\theta ^{\rho \beta }F_{\alpha \beta }F^{\nu \alpha })F_\alpha ^\rho \theta ^{\alpha \beta }F_\beta ^\nu ,`$
we find the equation of motion ,

$$_\rho \mathrm{\Pi }^{\rho \nu }=0.$$
(53)
The stress tensors read

$`T_{\rho \mu }^{c,\theta }`$ $`=`$ $`\mathrm{\Pi }_{\rho \nu }_\mu A^\nu g_{\rho \mu }_{inv}^\theta ,`$ (54)
$`T_{\rho \mu }^{s,\theta }`$ $`=`$ $`\mathrm{\Pi }_{\rho \nu }F_\mu ^\nu g_{\rho \mu }_{inv}^\theta .`$ (55)
Explicitly we have for $`T_{\rho \mu }^{s,\theta }`$

$`T_{\rho \mu }^{s,\theta }`$ $`=`$ $`g_{\rho \mu }_{inv}^\theta F_{\mu \nu }F_\rho ^\nu (1{\displaystyle \frac{1}{2}}\theta ^{\alpha \beta }F_{\alpha \beta })+{\displaystyle \frac{1}{4}}F_{\mu \nu }\theta _\rho ^\nu F^2`$ (56)
$`+F_{\mu \nu }\theta _{\rho \beta }F_\alpha ^\beta F^{\nu \alpha }(F_{\mu \alpha }F_{\rho \nu }+F_{\rho \alpha }F_{\mu \nu })F_\beta ^\alpha \theta ^{\nu \beta }.`$
The latter equation confirms Kruglov’s result . One has to stress that $`T_{\rho \mu }^{s,\theta }`$ is $`not`$ symmetric and $`not`$ traceless. Additionally, it is remarkable that in expanding the tensor (36) for the $`U(1)`$-case one gets

$`\widehat{T}_{\rho \mu }^s|_{𝒪(\theta )}`$ $`=`$ $`g_{\rho \mu }_{inv}^\theta F_{\mu \nu }F_\rho ^\nu (1{\displaystyle \frac{1}{2}}\theta ^{\alpha \beta }F_{\alpha \beta })`$ (57)
$`(F_{\mu \alpha }F_{\rho \nu }+F_{\rho \alpha }F_{\mu \nu })F_\beta ^\alpha \theta ^{\nu \beta }+\theta ^{\alpha \beta }_\beta (A_\alpha F_{\rho \nu }F_\mu ^\nu )`$
$``$ $`T_{\rho \mu }^{s,\theta }`$
We observe that (ignoring the total derivative) the nonsymmetric parts of $`T_{\rho \mu }^{s,\theta }`$ do not appear in the expansion of $`\widehat{T}_{\rho \mu }^s`$. Moreover, these are exactly the terms where $`\theta _\rho ^\nu `$ carries a free index $`\rho `$. For $`T_{\rho \mu }^{c,\theta }`$ and $`\widehat{T}_{\rho \mu }^c`$ we get the analogous result.
Thus we find that the calculation of the energy-momentum tensor does not commute with the Seiberg-Witten expansion of fields and Moyal products.

## 6 Conclusion

For noncommutative gauge field models we have studied (at the classical level) the construction of the various energy-momentum tensors in order to describe translation invariance of different noncommutative gauge field theories. Due to the presence of the deformation parameter $`\theta ^{\mu \nu }`$ (as a constant, antisymmetric, fixed tensor) Lorentz and dilation invariances are manifestly broken, entailing that the corresponding stress tensors are not symmetric and not traceless. The obtained results may be the basis for the discussion of broken Lorentz and dilation symmetry.


format: text

text:
# Indication for Large Rescatterings in Charmless Rare 𝑩 Decays

## I Introduction

Based on data from the CLEO experiment, it was pointed out in 1999 gamma  that the emerging $`BK\pi `$, $`\pi \pi `$ rates support factorization, if the phase angle $`\gamma `$ (or $`\varphi _3\mathrm{arg}V_{ub}^{}`$ PDG ) of the Cabibbo-Kobayashi-Maskawa (CKM) quark mixing matrix is large. We now have some theoretical basis for factorization QCD ; PQCD  in charmless $`B`$ decays, and it is common for $`B`$ physics practitioners to take $`\varphi _380^{}`$$`90^{}`$, which is in contrast with the $`60^{}`$ value indicated by CKM fits CKM  to other data.

At the turn of the century, the dramatic ascent of the B factories brought the CLEO era to an end. CLEO did make an attempt CLEO\_CP  to measure direct $`CP`$ violating rate asymmetries ($`A_{\mathrm{CP}}`$) in a few modes, where for a $`Bf`$ decay

$$A_{\mathrm{CP}}(f)\frac{(\overline{B}\overline{f})(Bf)}{(\overline{B}\overline{f})+(Bf)}.$$
(1)
The central values of the CLEO measurements differed from factorization expectations, but errors were large. Some other oddities lingered, such as the smallness of $`\pi ^{}\pi ^+`$ rate compared with $`\pi ^{}\pi ^0`$. It was thus suggested delta  that one may need large rescattering, in addition to large $`\varphi _3`$. Though speculative, this had implications beyond the shifted pattern in $`A_{\mathrm{CP}}`$s: $`\pi ^0\pi ^0`$ would become prominent, and $`CP`$ violation in $`\overline{B}{}_{}{}^{0}\pi ^{}\pi ^+`$ could be sizable. A few years later, it is surprising that the speculated patterns seem to be really emerging!

Let us give a snapshot of the current landscape hh\_belle ; hh\_babar ; hh\_cleo ; pipi\_belle ; pipi\_babar ; moriond  (as summarized in Tables 1 and 2). All the $`K\pi `$, $`\pi \pi `$ modes have been measured by both Belle and BaBar experiments to some accuracy, and with good agreement. The $`A_{\mathrm{CP}}`$ in $`K^{}\pi ^+`$ mode is now significant, and seem opposite in sign to the factorization expectation QCD ; the 3$`\sigma `$ effect in $`\overline{K}{}_{}{}^{0}\pi _{}^{}`$ mode reported by Belle is no more. The conflicting signs between Belle and BaBar on $`A_{\mathrm{CP}}`$ in $`K^{}\pi ^0`$ and $`\overline{K}^0\pi ^{}`$ modes keeps these asymmetries rather consistent with zero. Both experiments have hints for $`\pi ^0\pi ^010^6`$, and have measured the mixing dependent $`CP`$ asymmetries in $`\pi ^{}\pi ^+`$ mode. For the latter, the two experiments diverge. We thus scale the error-bars by an $`S`$ factor following the Particle Data Group (PDG) PDG  for these modes. Following Belle, we denote the two measurables as $`A_{\pi \pi }`$ ($`C_{\pi \pi }`$), equivalent to $`A_{\mathrm{CP}}`$ in $`\overline{B}{}_{}{}^{0}\pi ^{}\pi ^+`$, and $`S_{\pi \pi }`$, where

$`A_{\mathrm{CP}}^{\pi \pi }(t)`$ $`=`$ $`{\displaystyle \frac{(\overline{B}{}_{}{}^{0}(t)\pi ^+\pi ^{})(B^0(t)\pi ^+\pi ^{})}{(\overline{B}{}_{}{}^{0}(t)\pi ^+\pi ^{})+(B^0(t)\pi ^+\pi ^{})}}`$ (2)
$`=`$ $`A_{\pi \pi }\mathrm{cos}(\mathrm{\Delta }m_Bt)+S_{\pi \pi }\mathrm{sin}(\mathrm{\Delta }m_Bt).`$
Belle finds $`A_{\pi \pi }1`$ and $`S_{\pi \pi }1`$ pipi\_belle  (hence outside the physical domain), while BaBar finds pipi\_babar  both $`0`$. Note that Belle’s updated numbers are consistent with earlier results, and the discrepancy with BaBar pipi\_babar  remains. The two central values for $`A_{\pi \pi }`$ now do agree in sign, but are opposite to (QCD) factorization expectations QCD .

Independent hint for rescattering CHY  comes from the unexpected emergence of color-suppressed $`\overline{B}{}_{}{}^{0}D^{()0}h^0`$ decays D0h0 , where $`h^0=\pi ^0`$, $`\eta `$ and $`\omega `$; the rates are all larger than expected. In this paper we extend the model of Ref. delta  and explore the implications of present data on both $`\varphi _3`$ and rescattering phases. The pattern change in rates, such as $`\pi ^0\pi ^0`$, $`K^{}K^{+,0}`$, the sizable “opposite sign$`A_{\mathrm{CP}}`$s in various modes, and especially $`A_{\pi \pi }`$ and $`S_{\pi \pi }`$, can be tested in the near future.

## II Formalism

Our picture is that of factorized $`B`$ decay amplitudes followed by final state rescattering (FSI), i.e.

$$i;\text{out}|H_\mathrm{W}|B=\underset{l}{}𝒮_{il}^{1/2}𝒜_l^f,$$
(3)
where $`|i;\text{out}`$ is the out state, $`𝒮`$ is the strong scattering matrix, and $`𝒜_l^f`$ is a factorization amplitude. It was pointed out in Ref. Donoghue  that elastic rescattering effects may not yet be greatly suppressed at $`m_B`$ scale, while inelastic rescattering contributions may be important.

We would clearly lose control if the full structure of Eq. (3) is employed. It is clear that the subset of two body final states from elastic rescatterings stand out against inelastic channels. Furthermore, it has been shown from duality GH  as well as statistical arguments SW  that inelastic FSI amplitudes tend to cancel among themselves and lead to small FSI phases $`20^{}`$. Thus, quasi-elastic scattering may well be still relevant in two-body $`B`$ decays, and we should allow experiment as the final judge. For example, if the factorization amplitudes are already good enough, the data will force us to have $`𝒮^{1/2}1`$, and vice versa.

We extend from the quasi-elastic $`\overline{B}DP`$ CHY  case to the $`\overline{B}PP`$ case, where $`D`$ is the SU$`(3)`$ $`D`$-meson triplet and $`P`$ the pseudoscalar octet. That is, we extend the $`\mathrm{𝟑}\mathrm{𝟖}\mathrm{𝟑}\mathrm{𝟖}`$ FSI formalism developed for color-suppressed $`D^0h^0`$ modes, to $`\mathrm{𝟖}\mathrm{𝟖}\mathrm{𝟖}\mathrm{𝟖}`$ rescattering in light $`PP`$ final states. Bose symmetry then implies that the $`𝒮^{1/2}`$ matrix in Eq. (3) takes up the form

$$𝒮^{1/2}=e^{i\delta _{\mathrm{𝟐𝟕}}}|\mathrm{𝟐𝟕}\mathrm{𝟐𝟕}|+e^{i\delta _\mathrm{𝟖}}|\mathrm{𝟖}\mathrm{𝟖}|+e^{i\delta _\mathrm{𝟏}}|\mathrm{𝟏}\mathrm{𝟏}|,$$
(4)
hence there are just two physical phase differences, which we take as $`\delta \delta _{\mathrm{𝟐𝟕}}\delta _\mathrm{𝟖}`$ and $`\sigma \delta _{\mathrm{𝟐𝟕}}\delta _\mathrm{𝟏}`$. These rescattering phases redistribute the factorized decay amplitudes $`𝒜_l^f`$ according to Eq. (3), but they also can be viewed as a simple two parameter model extension beyond the usual $`BPP`$ amplitudes. The detailed formalism is given elsewhere. There are also some similar works in the literature similar . We shall see that $`|\delta \sigma |50^{}`$ turns out to be the case of interest. As in CHY , we drop the SU$`(3)`$ singlet $`\mathrm{𝟏}`$, or $`\eta _1`$, from the rescattering formulation. For the present case, one anyway has the difficulty in explaining the huge rate observed PDG  for $`B\eta ^{}K`$.

For $`𝒜_l^f`$, the present QCD QCD  or PQCD PQCD  factorization approaches involve effects that are subleading in $`1/m_b`$, such as weak annihilation contributions. To avoid double counting hadronic effects, we shall use absorpt  naive factorization AKL  amplitudes. In fact, for QCD factorization, which is close to naive factorization, removing all subleading effects but keeping the $`1/m_s^{\mathrm{eff}}`$ chiral enhancement seems to give a better fit to $`K\pi `$, $`\pi \pi `$ rates Beneke .

We follow the $`\chi ^2`$ fit strategy of Ref. HSW , but keeping the $`\delta `$ and $`\sigma `$ phases of Eqs. (3) and (4) as additional parameters. As input, we take central values of $`|V_{cb}|`$ and $`|V_{ub}|`$ from Ref. PDG . We focus on $`\overline{B}PP`$ modes, since the $`VP`$, $`VV`$ situation is not yet settled. We thus take only the 7 $`K\pi `$ and $`\pi \pi `$ rates, the better measured $`A_{\mathrm{CP}}`$s in $`K^{}\pi ^{+,0}`$ and $`K^0\pi ^{}`$ modes, and average over the current values reported by BaBar, Belle and CLEO CLEO\_CP ; hh\_belle ; hh\_babar ; hh\_cleo ; pipi\_belle ; pipi\_babar ; moriond , as given in Table 1 and 2. We also constrain $`f_\pi F_0^{BK}/f_KF_0^{B\pi }=0.9\pm 0.1`$ QCD . We use the stringent upper limit moriond  of $`2.2(0.6)\times 10^6`$ for $`K^{}K^{0(+)}`$ of BaBar. The limits are implemented as boundaries. We do not use $`A_{\pi \pi }`$ and $`S_{\pi \pi }`$ as input, since the experimental situation is still controversial. We do not use $`\eta \pi ^{}(K^{})`$ rates and $`A_{\mathrm{CP}}`$s, but give $`\eta _8\pi ^{}(K^{})`$ only.

The fit parameters are $`F_0^{BK}`$, the chiral enhancement parameter $`1/m_s^{\mathrm{eff}}`$ gamma , the FSI phases $`\delta `$ and $`\sigma `$, and possibly $`\varphi _3`$. Because of the $`S_{\pi \pi }`$ controversy, we explore two cases: $`\varphi _3`$ free (Fit 1), or fixed (Fit 2) at $`60^{}`$ CKM .

## III Results

The fitted rates, $`A_{\mathrm{CP}}`$s, and especially $`A_{\pi \pi }`$ and $`S_{\pi \pi }`$, together with inputs, are given in Table 3. Setting $`\delta `$ and $`\sigma `$ to zero but keeping all other parameters as determined by the fit, the results are given in parentheses to indicate FSI cross-feed. Note that $`\sigma `$ appears only in the $`\pi ^{}\pi ^+`$, $`\pi ^0\pi ^0`$, $`K^{}K^+`$, $`K^0\overline{K}^0`$, $`\pi ^0\eta _8`$ and $`\eta _8\eta _8`$ rescattering subset. The $`\chi _{\mathrm{min}.}^2`$ and fitted parameters are given in Table 4. The $`\chi _{\mathrm{min}.}^2/\mathrm{d}.\mathrm{o}.\mathrm{f}.`$ for Fit 1 and 2 are 17/5 (giving $`\varphi _396^{}`$) vs. 25/6, and the former seems better. Both fits are much worse without FSI: $`\chi _{\mathrm{min}.}^2/\mathrm{d}.\mathrm{o}.\mathrm{f}.`$ is 50/7 (65/8) for Fit 1 (2), as seen in the last column of Table 4. For illustration, we obtain output errors for both Tables by scanning the $`\chi ^2\chi _{\mathrm{min}.}^2+1`$ parameter space.

Let us illustrate the roles played by various inputs. The $`K\pi `$ rates are now measured with some precision. As before, together with the large $`K^{}\pi ^+/\pi ^{}\pi ^+`$ ratio, these are the main driving force for large $`\varphi _3`$ gamma ; HSW . What is new is the pull of $`A_{\mathrm{CP}}`$s. With the 3$`\sigma `$ effect from Belle gone, $`A_{\mathrm{CP}}(K^0\pi ^{})`$ is consistent with zero and not very constraining. But the $`A_{\mathrm{CP}}`$s in $`K^{}\pi ^+`$ now has some significance ($`2\sigma `$), with the central value opposite in sign with respect to factorization, which may call for delta  rescattering. We illustrate in Fig. 1 the $`\delta `$ dependence of $`A_{\mathrm{CP}}(K^{}\pi ^{+,0})`$. Indeed, we see that for both fits, a finite, positive $`\mathrm{sin}\delta `$ can turn the two $`A_{\mathrm{CP}}`$s negative. Note that BaBar and CLEO give a negative $`A_{\mathrm{CP}}(K^{}\pi ^0)`$, while the present Belle result flips sign from its previous result and prefers a positive asymmetry. Although $`\mathrm{sin}\delta <0`$ is allowed by rate data, it is disfavored by $`A_{\mathrm{CP}}(K^{}\pi ^+)`$. The two modes compete and settle on the fit output of $`\delta 65^{}`$, i.e. the $`A_{\mathrm{CP}}(K^{}\pi ^+)`$ preference for larger $`\delta `$ is held back by $`A_{\mathrm{CP}}(K^{}\pi ^0)`$. A similar tug of war is seen between the rates of $`\overline{K}{}_{}{}^{0}\pi _{}^{0}`$ (and $`\pi ^{}\pi ^+`$) vs. $`K^{}\pi ^{+,0}`$, $`\overline{K}{}_{}{}^{0}\pi _{}^{}`$.

As remarked earlier, the stringent bounds on $`K^{}K^{0,+}`$ rates require special care. The limits are not Gaussian so should not enter the $`\chi ^2`$ fit, but were enforced as strict bounds. As can be seen from Table 3, while the fitted $`K^{}K^0`$ rate is below the bound, for $`K^{}K^+`$ the Fit 2 output sits right at the bound. For Fit 1 it is also rather close. This implies sensitivity to the bounds and the way they are implemented. In Fig. 2 we give the $`\delta `$ ($`\sigma `$) dependence of $`K^{}K^{0(+)}`$ and the bounds that we employ. Note that a vanishing $`K^+K^{}`$ rate is possible with finite $`\sigma `$. We stress that data is still fluctuating, as both BaBar and Belle have raised their bounds on $`K^{}K^0`$ rates from the summer 2002 results.

Unlike $`K^0K^{}`$ mode which is already $`10^6`$ under factorization, $`K^{}K^+`$ is very suppressed hence sensitive to FSI. Fig. 2(b) illustrates some subtlety of our SU(3) FSI fit. From Eq. (4), if $`\delta _\mathrm{𝟏}`$, $`\delta _\mathrm{𝟖}`$, $`\delta _{\mathrm{𝟐𝟕}}`$ are all randomly sizable, one would expect $`K^{}K^+\pi ^{}\pi ^+>10^6`$, which is realized in Fig. 2(b) for $`|\delta \sigma |60^{}`$. But this is ruled out by the absence of $`K^{}K^+`$ so far. However, as also can be seen from Fig. 2(b), for $`|\delta \sigma |50^{}`$, the $`K^{}K^+`$ rate can be comfortably below the present limit, while $`\delta `$, $`\sigma `$ can be separately large. The subtlety is traced to the SU(3) decomposition

$$(\pi \pi )_{I=0}\left|𝒮^{\frac{1}{2}}\right|(\pi \pi )_{I=0}=\left(\frac{3}{8}e^{i\delta _\mathrm{𝟏}}+\frac{3}{5}e^{i\delta _\mathrm{𝟖}}+\frac{1}{40}e^{i\delta _{\mathrm{𝟐𝟕}}}\right).$$

Thus, because of the small weight of $`\mathrm{𝟐𝟕}\mathrm{𝟐𝟕}`$ in the $`I=0`$ $`\pi \pi \pi \pi `$ amplitude, when $`\delta _\mathrm{𝟖}\delta _\mathrm{𝟏}`$, i.e. $`\delta \sigma `$, one finds $`|(\pi \pi )_{I=0}|𝒮^{\frac{1}{2}}|(\pi \pi )_{I=0}|1`$, and “leakage” to $`|(K\overline{K})_{I=0}`$ is suppressed. Note that $`K^0\overline{K}{}_{}{}^{0}K^0K^{}`$ also remains little perturbed.

While $`\mathrm{sin}\sigma <0`$ is strongly disfavored by $`K^{}K^+`$ mode, the driving force for large $`\sigma `$ rests in the $`\pi \pi `$ sector, where all measurables turn out to be volatile — all three rates and $`A_{\pi \pi }`$, $`S_{\pi \pi }`$. The $`\pi ^{}\pi ^+`$ and $`\pi ^0\pi ^0`$ rates are sensitive to both $`\delta `$ and $`\sigma =\delta _{\mathrm{𝟐𝟕}}\delta _\mathrm{𝟏}`$. To illustrate, we fix $`\delta `$ to the fit values of Table 4 and plot in Fig. 3 the $`\pi ^{}\pi ^+`$, $`\pi ^0\pi ^0`$ rates vs. $`\sigma `$. The two fits are similar and clearly favor large $`\sigma 90,\mathrm{\hspace{0.17em}103}^{}`$, as given in Table 4. The driving force for large $`\sigma `$ is the smallness of $`\pi ^{}\pi ^+`$ rate. For instance, if $`\varphi _3`$ went upward by $`1\sigma `$ in Fit 1, i.e. $`\varphi _3117^{}`$, the stress from $`\pi ^{}\pi ^+`$ rate would be greatly released and $`\sigma `$ can come down to $`31^{}`$. But for Fit 2 where $`\varphi _3`$ is held fixed at $`60^{}`$, one needs more FSI to reduce $`\pi ^{}\pi ^+`$ rate by shifting it partly to $`\pi ^0\pi ^0`$. It is therefore intriguing that both Belle and BaBar have hints for the latter!

At this point we note that the $`\pi ^{}\pi ^0`$ rate in Fit 2 is $`3\sigma `$ below experiment, and accounts for most of the $`\chi ^2`$ difference between Fits 1 and 2. Unless both experiments are wrong, this makes Fit 2 less desirable; further symptoms are the need for larger $`1/m_s^{\mathrm{eff}}`$ and lower $`F_0^{B\pi (K)}`$. The situation comes about because, with low $`\varphi _3`$, it is hard to get low $`\pi ^{}\pi ^+`$ rate, even with rescattering. The fit resorts to reducing $`F_0^{B\pi }`$ by 20% (vs. Fit 1), hence reducing $`\pi \pi `$ rates by 36%. Since $`\pi ^{}\pi ^0`$ rate is independent of $`\varphi _3`$ and FSI, this makes $`\pi ^{}\pi ^0`$ too small.

What is intriguing — and makes considering Fit 2 worthwhile — is $`A_{\pi \pi }`$ and $`S_{\pi \pi }`$. We plot these in Fig. 4 with $`\delta `$ fixed at fit values of Table 4. While we are aware that the two experiments are in conflict, we have forcefully “combined” the present Belle pipi\_belle  and BaBar pipi\_babar  results (with enlarged error bars) in the plots. The experiments do, however, agree on the sign of $`A_{\pi \pi }`$: Belle finds $`0.77\pm 0.27\pm 0.08`$, and BaBar finds $`0.30\pm 0.25\pm 0.04`$ ($`C_{\pi \pi }`$). With $`\sigma 100^{}`$, Fits 1 and 2 return $`A_{\pi \pi }0.12`$, which agree with data in sign. Without the FSI phases, both fits would give opposite sign.

As a measure of direct $`CP`$ violation, $`A_{\pi \pi }`$ is clearly sensitive to FSI phases, but it does not distinguish much between Fits 1 and 2; most results (except $`\pi ^{}\pi ^0`$) are not that different. It is $`S_{\pi \pi }`$, which probes the $`CP`$ phase of the combined mixing and decay amplitudes, that is sensitive to $`\varphi _3`$, as is evident in Fig. 4(b). Various $`A_{\mathrm{CP}}`$s and rates have constrained $`\mathrm{sin}\delta >0`$ and $`\mathrm{sin}\sigma >0`$. We have checked that $`S_{\pi \pi }`$ is not just flat in $`\sigma `$ for $`\mathrm{sin}\sigma >0`$ and $`\delta 65^{}`$, as seen from Fig. 4(b), but is relatively flat for all $`\delta ,\sigma 180^{}`$. The sensitivity with $`\varphi _3`$ gives rise to intriguing results. Fit 1 gives $`\varphi _396^{}`$, and $`S_{\pi \pi }15\%`$ is consistent with BaBar. However, sensitivity to $`\varphi _3`$ brings $`S_{\pi \pi }`$ up to 50% for $`\varphi _3=117^{}`$. For Fit 2, one fixes $`\varphi _3=60^{}`$ to the CKM fit value, and $`S_{\pi \pi }0.9`$ is consistent with Belle. We have included Fit 2 in large part because of the present volatility in $`S_{\pi \pi }`$. Otherwise it has much poorer $`\chi ^2`$.

It is useful to compare with the elastic (SU(2) or isospin) case given in Ref. delta . For the whole range of $`\delta `$ and $`|\delta \sigma |70^{}`$, the summed rates in $`K^{}\pi ^+`$$`\overline{K}{}_{}{}^{0}\pi _{}^{0}`$ ($`\overline{K}{}_{}{}^{0}\pi _{}^{}`$$`K^{}\pi ^0`$) and $`\pi ^{}\pi ^+`$$`\pi ^0\pi ^0`$ systems vary by no more than few% and 20%, respectively. We can reproduce the results of Ref. delta  for this parameter range by taking $`\delta _{K\pi }\delta _{3/2}\delta _{1/2}\mathrm{arg}(1+9e^{i\delta })`$ and $`\delta _{\pi \pi }\delta _2\delta _0\mathrm{arg}(1+24e^{i\delta }+15e^{i\sigma })`$ erratum . We see from Fig. 4(a) that, to reach the Belle and BaBar “average” $`A_{\pi \pi }`$, a very large $`\sigma 180^{}`$ (hence large deviation from SU(2)) would be called for. This situation is not supported by the absence of $`K^{}K^+`$ and the fact that $`\pi ^{}\pi ^+>4\times 10^6`$.

## IV Discussion and Conclusion

Some remarks are now in order. First, the $`S_{\pi \pi }`$ sensitivity to $`\varphi _3`$ and its numerics are similar to other discussions QCD ; CKM ; Fleischer:2002zv , except we show that $`S_{\pi \pi }`$ is insensitive to FSI for $`\mathrm{sin}\delta ,\mathrm{sin}\sigma >0`$. Second, with current data, not only $`\pi ^0\pi ^010^6`$, but also $`K^{}K^0`$, $`K^{}K^+10^6`$ are inevitable for our rescattering model. Besides the rates of $`\pi ^{}\pi ^+`$, $`\pi ^0\pi ^0`$, they are largely driven by $`A_{\mathrm{CP}}(K^{}\pi ^+)`$ (otherwise sign would be wrong). It is also strongly suggested by the need to change sign for $`A_{\pi \pi }`$. With a factorization contribution at $`10^6`$ level, $`K^{}K^0`$ should be seen soon, but for $`K^{}K^+`$, it is possible to get vanishing rates at $`\sigma \delta `$, the “SU(2) limit”. Third, our $`\pi ^{}\eta _8`$ rate is quite low and the $`A_{\mathrm{CP}}`$ is opposite to the experimental result. This may be due to our inability to treat $`\eta _1`$, or indicate an experimental problem, or both. Four, it has been pointed out that subleading, flavor exchange $`PPPP`$ scattering need not be small at $`m_B`$ scale Donoghue . Note the present $`\delta `$ and $`\sigma `$ phases are effective delta  parameters beyond factorization. Their link to the actual $`PPPP`$ phases are nontrivial and has to be studied further. Fifth, a fully SU(3) analysis also hints at large FSI phases He .

Finally, let us compare with (P)QCD factorization approaches. For QCD factorization, removing all subleading effects (hence $``$ naive factorization) gives better fit Beneke  to $`K\pi `$, $`\pi \pi `$ rates. To account for $`A_{\mathrm{CP}}`$s, Ref. QCD  resorts to a sizable complex $`X_{H,A}`$ hadronic parameter, which is a form of large strong phase. PQCD factorization fares better with $`A_{\mathrm{CP}}`$keum  by having a sizable absorptive part in some penguin annihilation diagrams. But it gives a larger $`\pi ^{}\pi ^+`$ and a smaller $`\pi ^{}\pi ^0`$ rate than data, the absence of $`\pi ^0\pi ^0`$, while $`K^{}K^+`$ is always very small ChenLi . Our results can therefore be distinguished from QCD and PQCD factorization approaches.

In summary, we find that a minimal extension of two quasi-elastic SU(3) FSI phases, $`\delta `$ and $`\sigma `$, can suffice to account for current charmless $`B`$ decay data. The observables to be tested in the near future are: sign of $`A_{\mathrm{CP}}`$s, with $`A_{\mathrm{CP}}(K^{}\pi ^0)20\%`$; the rates of $`\pi ^0\pi ^010^6`$, $`K^{}K^+10^6`$; $`A_{\pi \pi }>0`$, and $`S_{\pi \pi }`$ could, depending on $`\varphi _3`$, agree with either BaBar or Belle values. The $`\pi ^{}\pi ^0`$ rate should be double checked. Many $`A_{\mathrm{CP}}`$s are large and have sign flipped, but can only be checked later. More details of the present work would be given elsewhere.

This work is supported in part by grants from NSC, 91-2112-M-002-027, 91-2811-M-002-043, 91-2112-M-033-013, the MOE CosPA Project, and NCTS.


text:
# A Quantum Random Walk Search Algorithm

## I Introduction

Recent studies of quantum random walks have suggested that they may display different behavior than their classical counterparts Aharonov et al. (1993, 2001); Ambainis et al. (2001); Farhi and Gutmann (1998); Childs et al. (2001). One of the promising features of these quantum random walks is that they provide an intuitive framework on which to build novel quantum algorithms. Since many classical algorithms can be formulated in terms of random walks, it is hoped that some of these may be translated into quantum algorithms which run faster than their classical counterparts. However, previous to a very recent paper by Childs et. al. Childs et al. (2002), there had been no quantum algorithms based on the random walk model. In this paper we show that a quantum search algorithm can be derived from a certain kind of quantum random walk. Optimal quantum search algorithms are already well knownGrover (1996, 1997); Bennett et al. (1997). The search algorithm from a quantum random walk we present here shows some differences from the established search algorithms and may possess useful properties with respect to robustness to noise and ease of physical implementation. It also provides a new direction for design of quantum algorithms from random walks, which may eventually lead to entirely new algorithms.

Current research uses two distinct models for quantum random walks, based on either discrete time steps or on continuous time evolution. Discrete time quantum random walks were introduced as a possible new tool for quantum algorithms generalizing discrete classical Markov chains Aharonov et al. (2001). The discrete time walk can be thought of as a succession of unitary operations, each of which has a non-zero transition amplitude only between neighboring nodes of the graph. The relation of these to classical Markov chains provides considerable motivation for exploration of discrete random walks. Within the field of classical algorithms, the application of classical Markov chains in classical algorithms has been quite revolutionary, providing new approximation and optimization algorithms. By analogy, it might reasonably be hoped that similar algorithmic advances could be obtained for quantum algorithms from development of the quantum random walks. The second quantum random walk model is the continuous-time quantum random walk, introduced in Farhi and Gutmann (1998); Childs et al. (2001, 2002). In the continuous-time walk the adjacency matrix of the graph is used to construct a Hamiltonian which gives rise to a continuous time evolution. This model differs from the discrete time walk in that even for small times there is an (exponentially small) probability of transition to non-adjacent nodes. In this paper, we will consider the discrete-time model only.

The paper is organized as follows. Sec. II provides a brief introduction to discrete-time quantum random walks. Sec. III describes the random walk search algorithm and provides a proof of its correctness. Sec. IV summarizes the similarities and differences between the random walk search algorithm and Grover’s search algorithm. Conclusions are presented in Sec. V.

Notation: Following standard computer science notation we will use the following to characterize the growth of certain functions: We will say $`f(n)=O(g(n))`$ if there are positive constants $`c`$ and $`k`$ such that $`0f(n)cg(n)`$ for $`nk`$. Similarly $`f(n)=\mathrm{\Omega }(g(n))`$ if $`0cg(n)f(n)`$ for constants $`c,k0`$ and $`nk`$.

## II Background

The discrete time random walk can be described by the repeated application of a unitary evolution operator $`U`$. This operator acts on a Hilbert space $`^C^S`$ where $`^C`$ is the Hilbert space associated with a quantum coin and $`^S`$ is the Hilbert space associated with the nodes of the graph. The operator $`U`$ can be written as Aharonov et al. (2001)

$$U=SC$$
(1)
where $`S`$ is a permutation matrix which performs a controlled shift based on the state of the quantum coin, and $`C`$ is a unitary matrix which “flips” the quantum coin. This operation can be visualized by analogy to a classical random walk. For each iteration of a discrete time classical random walk on a graph, a coin is flipped. The walker then moves to an adjacent node specified by the outcome of the coin flip. An equivalent process occurs in the quantum random walk, with the modification that the coin is a quantum coin and can therefore exist in a superposition of states. This modification can lead to dramatic differences in behavior between the classical and quantum random walks. However, it should be noted that if the state of the coin is measured after each flip, then the quantum random walk reverts to a classical random walk (and similarly if the state of the nodes is measured after every step).

An important feature of the discrete time quantum random walk that has significance for its use in development of quantum algorithms, is that by virtue of its definition this walk will be efficiently implementable on a quantum computer whenever its classical counterpart is. (By efficient we mean that the walk can be simulated by a circuit with a number of gates that is polynomial in the number of bits (qubits)). This is due to the very similar structure of both these walks. To illustrate this, assume we have an efficient way to implement the classical random walk on the underlying graph, i.e. to perform the coin-flip and subsequent shift. The shift is conditional on the outcome of the coin-flip (which determines the direction of the next step), i.e. we have a classical efficient circuit which performs a controlled shift on the basis states. It is straightforward Nielsen and Chuang (2000) to translate this circuit into a quantum circuit which performs the unitary controlled shift of Eq. (1). Similarly if there is an efficient procedure to flip the classical coin of the random walk, there will be an efficient way to implement a quantum coin. Hence implementation of the discrete time random walk is automatically efficient if the underlying classical walk is efficiently implementable.

Note that if no measurement is made, the quantum walk is controlled by a unitary operator rather than a stochastic one. This implies that there is no limiting stationary distribution Aharonov et al. (2001); Moore and Russell (2002). Nevertheless, several recent works have shown that consistent notions of mixing time can be formulated, and have shown polynomial speed up in these quantum mixing times relative to the classical analog Aharonov et al. (2001); Moore and Russell (2002). Another quantity for which quantum walks have shown speed-up relative to their classical analogs is the hitting time Kempe (2002); Yamasaki et al. (2002). Under certain conditions this speed-up can be exponential compared to the classical analogue. We refer the reader to the recent papers Aharonov et al. (2001), Ambainis et al. (2001), Moore and Russell (2002) and Kempe (2002) for some results obtained from discrete time quantum random walks.

Our random walk search algorithm will be based on a random walk on the $`n`$-cube, i.e. the hypercube of dimension $`n`$ Kempe (2002); Moore and Russell (2002). The hypercube is a graph with $`N=2^n`$ nodes, each of which can be labelled by an $`n`$-bit binary string. Two nodes on the hypercube described by bitstrings $`\stackrel{}{x}`$ and $`\stackrel{}{y}`$ are are connected by an edge if $`\left|\stackrel{}{x}\stackrel{}{y}\right|=1`$, where $`\left|\stackrel{}{x}\right|`$ is the Hamming weight of $`\stackrel{}{x}`$. In other words, if $`\stackrel{}{x}`$ and $`\stackrel{}{y}`$ differ by only a single bit flip, then the two corresponding nodes on the graph are connected. Thus, each of the $`2^n`$ nodes on the $`n`$-cube has degree $`n`$ (i.e. it is connected to $`n`$ other nodes), so the Hilbert space of the algorithm is $`=^n^{2^n}`$. Each state in $``$ can be described by a bit string $`\stackrel{}{x}`$, which specifies the position on the hypercube, and a direction $`d`$, which specifies the state of the coin. The shift operator, $`S`$, maps a state $`|d,\stackrel{}{x}`$ onto the state $`|d,\stackrel{}{x}\stackrel{}{e_d}`$, where $`\stackrel{}{e_d}`$ is the $`d^{th}`$ basis vector on the hypercube. $`S`$ can be written explicitly as,

$$S=\underset{d=0}{\overset{n1}{}}\underset{\stackrel{}{x}}{}|d,\stackrel{}{x}\stackrel{}{e_d}d,\stackrel{}{x}|$$
(2)
To completely specify the unitary evolution operator $`U`$, the coin operator, $`C`$, must also be chosen. Normally, the coin operator is chosen such that the same coin is applied to each node on the graph. This is the case in previous studies of discrete quantum walks on the line Watrous (2001); Aharonov et al. (2001); Ambainis et al. (2001) and on the hypercube Kempe (2002); Moore and Russell (2002). In other words, the coin operator $`C`$ can be written as,

$$C=C_0$$
(3)
where $`C_0`$ is a $`n\times n`$ unitary operator acting on $`^C`$. If $`C`$ is separable according to Eq. (3) then the eigenstates of $`U`$ are simply the tensor product of the eigenstates of a (modified) coin $`C_\stackrel{}{k}`$ and of the Fourier modes of the hypercube (labelled by $`n`$-bit strings $`\stackrel{}{k}`$Moore and Russell (2002). One frequently chosen separable coin is Grover’s “diffusion” operator on the coin space, given by

$$C_0=G=+2|s^Cs^C|,$$
(4)
where $`|s^C`$ is the equal superposition over all $`n`$ directions, i.e. $`|s^C=\frac{1}{\sqrt{n}}_{d=1}^n|d`$ Moore and Russell (2002). This coin operator is invariant to all permutations of the $`n`$ directions, so it preserves the permutation symmetry of the hypercube. The use of the Grover diffusion operator as a coin for the hypercube was proposed in Moore and Russell (2002), where it was pointed out that this operator is the permutation invariant operator farthest away from the identity operator Moore and Russell (2002). So, heuristically, it should provide the most efficient mixing over states, from any given initial state. The non-trivial eigenvalues and eigenvectors of $`U`$ are given by Moore and Russell (2002),

$$e^{\pm i\omega _k}=1\frac{2k}{n}\pm \frac{2i}{n}\sqrt{k\left(nk\right)}$$
(5)
$$|v_\stackrel{}{k},|v_\stackrel{}{k}^{}=\underset{\stackrel{}{x},d}{}\left(1\right)^{\stackrel{}{k}\stackrel{}{x}}\frac{2^{n/2}}{\sqrt{2}}|d,\stackrel{}{x}\times \{\begin{array}{cc}1/\sqrt{k}\hfill & \text{if }k_d=1\hfill \\ i/\sqrt{nk}\hfill & \text{if }k_d=0\hfill \end{array}$$
(6)
Note that the equal superposition over all states, $`|\psi _0=|s^C|s^S`$, where $`|s^S`$ is the equal superposition over the $`2^n`$ nodes, is an eigenvector of $`U`$ with eigenvalue $`1`$. So repeated application of $`U`$ leaves the state $`|\psi _0`$ unchanged.

In order to create a search algorithm using the quantum random walk architecture, we now consider a small perturbation of the unitary operator $`U`$. Specifically, we consider “marking” a single arbitrary node by applying a special coin to that node. In this respect, the coin operator now takes on the function of an oracle. Yet, contrary to the standard oracle which flips the phase of the marked state in the standard setting of a search algorithm, the oracle acts instead by applying a marking coin, $`C_1`$, to the marked node and a different coin, $`C_0`$, to the unmarked nodes. Without loss of generality, we can assume that the marked node corresponds to the all-zero string $`\stackrel{}{x}_{target}=\stackrel{}{0}`$. Then our coin operator becomes

$$C^{}=C_0+\left(C_1C_0\right)|\stackrel{}{0}\stackrel{}{0}|.$$
(7)
The marking coin, $`C_1`$, can be any $`n\times n`$ unitary matrix. For simplicity, we will consider here the case where $`C_1=`$. Then our perturbed unitary evolution operator, $`U^{}`$, is given by

$$\begin{array}{ccc}\hfill U^{}& =& SC^{}\hfill \\ & =& S\left(G\left(G\right)|\stackrel{}{0}\stackrel{}{0}|\right)\hfill \\ & =& U2S\left(|s^Cs^C||\stackrel{}{0}\stackrel{}{0}|\right)\hfill \end{array}$$
(8)
Analysis of the effects of this perturbation leads directly to the definition of the random walk search algorithm, as will be described in the next section.

## III Random Walk Search Algorithm

### III.1 Overview of the Algorithm

We define the search space of the algorithm to be the set of all $`n`$-bit binary strings, $`\stackrel{}{x}=\{0,1\}^n`$. We consider the function $`f\left(\stackrel{}{x}\right)=\{0,1\}`$, such that $`f\left(\stackrel{}{x}\right)=1`$ for exactly one input $`\stackrel{}{x}_{target}`$. Our goal is to find $`\stackrel{}{x}_{target}`$. Using the mapping of $`n`$-bit binary string to nodes on the hypercube, this search problem is then equivalent to searching for a single marked node amongst the $`N=2^n`$ nodes on the $`n`$-cube. For purposes of the proof, we have set the marked node to be $`\stackrel{}{x}_{target}=\stackrel{}{0}`$, but the location of the marked node has no significance.

The random walk search algorithm is implemented as follows:

1. Initialize the quantum computer to the equal superposition over all states, $`|\psi _0=|s^C|s^S`$. This can be accomplished efficiently on the node-space by applying $`n`$ single-bit Hadamard operations to the $`|\stackrel{}{0}`$ state. A similar procedure works for the direction space.
2. Given a coin oracle, $`C^{}`$, which applies the coin $`C_0=G`$ to the unmarked states and the coin $`C_1=`$ to the marked state, apply the perturbed evolution operator, $`U^{}=SC^{}`$, $`t_f=\frac{\pi }{2}\sqrt{2^n}`$ times.
3. Measure the state of the computer in the $`|d,\stackrel{}{x}`$ basis.

It is our claim that with probability $`\frac{1}{2}O\left(1/n\right)`$, the outcome of the measurement will be the marked state. By repeating the algorithm a constant number of times, we can determine the marked state with an arbitrarily small degree of error. In the remainder of this section we provide a proof of this algorithm.

The general outline of the proof that we will present is the following. We need to determine the result of the operation $`(U^{})^t`$ on the initial state $`|\psi _0`$. To do this, we will first simplify the problem by showing that the perturbed walk on the hypercube can be collapsed to a walk on the line (Theorem (1)). Next, by constructing two approximate eigenvectors of $`U^{}`$, $`|\psi _0`$ and $`|\psi _1`$, we will show that there are exactly two eigenvalues of $`U^{}`$ that are relevant (i.e. the initial state $`|\psi _0`$ has high overlap with the space spanned by the corresponding eigenvectors, see Theorem (2) and Theorem (3)). We denote these eigenvalues by $`e^{i\omega _0^{}}`$ and $`e^{i\omega _0^{}}`$. We will then show that the corresponding eigenvectors $`|\omega _0^{}`$ and $`|\omega _0^{}`$ can be well-approximated by linear combinations of the initial state $`|\psi _0`$ and the second state $`|\psi _1`$ (Theorem (4)). As a result, our random walk search algorithm can be approximated by a two-dimensional rotation in the $`|\omega _0^{},|\omega _0^{}`$-plane away from the initial state $`|\psi _01/\sqrt{2}(|\omega _0^{}+|\omega _0^{})`$ and towards $`|\psi _1i/\sqrt{2}(|\omega _0^{}+|\omega _0^{})`$, which constitutes a very close approximation to the target state $`|\stackrel{}{x}_{target}`$. Finally, we show that each application of the evolution operator $`U^{}`$ corresponds to a rotation angle of approximately $`1/\sqrt{2^{n1}}`$ (Theorem (5)). Hence, the search is completed after approximately $`\frac{\pi }{2}\sqrt{2^{n1}}`$ steps, i.e., after $`O\left(\sqrt{N}\right)`$ calls to the oracle, where $`N=2^n`$ is the number of nodes.

### III.2 Proof of Correctness

In general, analytic determination of the eigenspectrum of a large matrix is a daunting task, so we will take advantage of the symmetries inherent in $`U^{}`$ to simplify the problem. Let us first show that the perturbed random walk on the hypercube can be collapsed onto a random walk on the line. Let $`P_{ij}`$ be the permutation operator which swaps the bits $`i`$ and $`j`$, in both the node space and the coin space. In other words, given a state $`|d,\stackrel{}{x}`$, under the permutation operator, $`P_{ij}`$, the $`i^{th}`$ and $`j^{th}`$ bits of $`\stackrel{}{x}`$ are swapped and the directions $`d=i`$ and $`d=j`$ are swapped. Clearly the unperturbed evolution operator $`U`$ commutes with $`P_{ij}`$ since every direction in the unperturbed walk is equivalent.

###### Theorem 1

$`U^{}`$ commutes with $`P_{ij}`$.

*Proof.*

$$\begin{array}{ccc}\hfill P_{ij}^{}U^{}P_{ij}& =& P_{ij}^{}UP_{ij}2P_{ij}^{}S\left(|s^Cs^C||\stackrel{}{0}\stackrel{}{0}|\right)P_{ij}\hfill \\ & =& U\frac{2}{\sqrt{n}}_{d=0}^{n1}P_{ij}^{}|d,\stackrel{}{e_d}d,0|P_{ij}\hfill \\ & =& U^{}\hfill \end{array}$$
(9)
So, $`[U^{},P_{ij}]=0`$.

Because the initial state $`|\psi _0`$ is an eigenvector of $`P_{ij}`$ with eigenvalue $`1`$ for all $`i`$ and $`j`$, and $`[U^{},P_{ij}]=0`$, any intermediate state $`|\psi _t=(U^{})^t|\psi _0`$ must also be an eigenvector of eigenvalue $`1`$ with respect to $`P_{ij}`$. Thus, $`(U^{})^t`$ preserves the symmetry of $`|\psi _0`$ with respect to bit swaps. It is therefore useful to define $`2n`$ basis states, $`|R,0,|L,1,|R,1,\mathrm{},|R,n1,|L,n`$ where

$`|R,x`$ $`=`$ $`\sqrt{{\displaystyle \frac{1}{\left(nx\right)\left(\genfrac{}{}{0pt}{}{n}{x}\right)}}}{\displaystyle \underset{\left|\stackrel{}{x}\right|=x}{}}{\displaystyle \underset{x_d=0}{}}|d,\stackrel{}{x}`$ (10)
$`|L,x`$ $`=`$ $`\sqrt{{\displaystyle \frac{1}{x\left(\genfrac{}{}{0pt}{}{n}{x}\right)}}}{\displaystyle \underset{\left|\stackrel{}{x}\right|=x}{}}{\displaystyle \underset{x_d=1}{}}|d,\stackrel{}{x}`$ (11)
which are also invariant to bit swaps $`P_{ij}`$. These states span the eigenspace of eigenvalue $`1`$ of $`P_{ij}`$. Using these basis states, we can project out all but one spatial degree of freedom and effectively reduce the random walk on the hypercube to a random walk on the line. This is illustrated in Fig. 1. The marked node corresponds now to $`|R,0`$. We can rewrite $`U`$, $`U^{}`$, and $`|\psi _0`$ in this collapsed basis. First note that the shift operator $`S`$ in this basis acts as

$$S=\underset{x=0}{\overset{n1}{}}|R,xL,x+1|+|L,x+1R,x|$$
(12)
and the unperturbed coin acts as

$$C_0=\underset{x=0}{\overset{n}{}}\left(\begin{array}{cc}\mathrm{cos}\omega _x& \mathrm{sin}\omega _x\\ \mathrm{sin}\omega _x& \mathrm{cos}\omega _x\end{array}\right)|xx|$$
(13)
where $`\mathrm{cos}\omega _x=1\frac{2x}{n}`$ and $`\mathrm{sin}\omega _x=\frac{2}{n}\sqrt{x\left(nx\right)}`$ and where the first part acts on the space spanned by $`\{|R,|L\}`$ and the second part acts on the positions $`\{|0,\mathrm{},|n\}`$ on the line. Note that the coin of the collapsed walk is not homogeneous in space any more. The unitary operator $`U`$ on the restricted space acts as

$$\begin{array}{ccc}\hfill U& =& _{x=0}^{n1}|R,x(\mathrm{cos}\omega _{x+1}L,x+1|+\mathrm{sin}\omega _{x+1}R,x+1\left|\right)+\hfill \\ & & _{x=1}^n|L,x(\mathrm{sin}\omega _{x1}L,x1|+\mathrm{cos}\omega _{x1}R,x1\left|\right)\hfill \end{array}.$$
(14)
Similarly,

$$U^{}=U+\mathrm{\Delta }U=U2|L,1R,0|$$
(15)
Note that the only difference between $`U`$ and $`U^{}`$ is in the sign of the matrix element in position ($`|L,1,|R,0`$). Finally,

$$|\psi _0=\frac{1}{\sqrt{2^n}}|R,0+\frac{1}{\sqrt{2^n}}|L,n+\underset{x=1}{\overset{n1}{}}\left(\sqrt{\frac{\left(\genfrac{}{}{0pt}{}{n1}{x1}\right)}{2^n}}|L,x+\sqrt{\frac{\left(\genfrac{}{}{0pt}{}{n1}{x}\right)}{2^n}}|R,x\right)$$
(16)
Since $`U`$ and $`P_{ij}`$ are mutually diagonalizable, the eigenvectors of $`U`$ in the reduced space are also bit-flip invariant. Examining Eq. (5), it is clear that if we take the equal superpositions of all eigenvectors of same eigenvalue $`|v_\stackrel{}{k}`$ such that $`\left|\stackrel{}{k}\right|=k`$, the resulting eigenvector will be bit-swap invariant. Thus we define,

$$|\omega _k=\frac{1}{\sqrt{\left(\genfrac{}{}{0pt}{}{n}{k}\right)}}\underset{\left|\stackrel{}{k}\right|=k}{}|v_\stackrel{}{k}$$
(17)
which are the eigenvectors of $`U`$ with eigenvalues $`e^{i\omega _k}`$ in the collapsed (symmetric) space.

Note that both $`U`$ and $`U^{}`$ are represented by real matrices; therefore, their eigenvalues and eigenvectors will come in complex conjugate pairs.

Having determined these general properties of the perturbed matrix $`U^{}`$, we now turn to the problem of analyzing the eigenvalue spectrum of $`U^{}`$. Let $`𝒜`$ be the arc on the unit circle containing all complex numbers of unit norm with real part greater than $`12/3n`$. In other words,

$$𝒜=\{z\mathrm{Re}z>1\frac{2}{3n},\left|z\right|=1\}$$
(18)
Fig. 2 shows the geometrical representation of $`𝒜`$ together with the eigenvalue spectra of the unperturbed and perturbed matrices for $`n=8`$. We will prove that $`𝒜`$ contains exactly two eigenvalues $`e^{i\omega _0^{}}`$ and $`e^{i\omega _0^{}}`$ of $`U^{}`$. First, we will prove that there are *at most* two eigenvalues with real part greater than $`12/3n`$. Then we will show that there are *at least* two eigenvalues on $`𝒜`$. From these facts, it follows that there are exactly two eigenvalues of $`U^{}`$ on $`𝒜`$.

###### Theorem 2

There are at most two eigenvalues of $`U^{}`$ with real part greater than $`12/3n`$.

*Proof.* We will prove by contradiction. Let us assume that there are three eigenvalues, $`e^{i\omega _0^{}}`$,$`e^{i\omega _1^{}}`$, and $`e^{i\omega _2^{}}`$, with real part greater than $`12/3n`$. Let $`|\omega _0^{}`$, $`|\omega _1^{}`$, and $`|\omega _2^{}`$ be the corresponding eigenvectors. Then,

$$\begin{array}{ccc}\hfill \mathrm{Re}_i\omega _i^{}\left|U^{}\right|\omega _i^{}& =& \mathrm{Re}_ie^{i\omega _i^{}}\omega _i^{}|\omega _i^{}\hfill \\ & >& 32/n\hfill \end{array}$$
(19)
Let us define $`\mathrm{\Omega }`$ to be the subspace spanned by $`|\omega _0^{}`$, $`|\omega _1^{}`$, $`|\omega _2^{}`$. Then we can write Eq. (19) as the partial trace of $`U^{}`$ over $`\mathrm{\Omega }`$,

$$\mathrm{Re}\mathrm{Tr}_\mathrm{\Omega }U^{}>32/n$$
(20)
Let us now define $`|\psi _{}=\frac{1}{\sqrt{2}}\left(|0,R|1,L\right)`$. We can expand the $`|\omega _0^{}`$, $`|\omega _1^{}`$, and $`|\omega _2^{}`$ in terms of $`|\psi _0`$, $`|\psi _{}`$ and a residual vector,

$`|\omega _0^{}`$ $`=`$ $`c_{00}^{}|\psi _0+c_{01}^{}|\psi _{}+c_{02}^{}|r_0^{}`$
$`|\omega _1^{}`$ $`=`$ $`c_{10}^{}|\psi _0+c_{11}^{}|\psi _{}+c_{11}^{}|r_1^{}`$
$`|\omega _2^{}`$ $`=`$ $`c_{20}^{}|\psi _0+c_{21}^{}|\psi _{}+c_{22}^{}|r_2^{}`$ (21)
where $`|r_i^{}`$ is a normalized vector orthogonal to $`|\psi _0`$ and $`|\psi _{}`$. We now observe that, due to the basis invariance of the trace, Eq. (20) holds for any linear combination of $`|\omega _0^{}`$, $`|\omega _1^{}`$, and $`|\omega _2^{}`$. Thus, we can construct three new orthonormal vectors, $`|\alpha _0`$, $`|\alpha _1`$, and $`|\alpha _2`$ by taking linear combinations of $`|\omega _0^{}`$, $`|\omega _1^{}`$, and $`|\omega _2^{}`$ such that,

$$\alpha _2|\psi _0=\alpha _2|\psi _{}=0$$
(22)
In other words, we can expand $`|\alpha _0`$, $`|\alpha _1`$, and $`|\alpha _2`$ as,

$$\begin{array}{ccccc}\hfill |\alpha _0& =& c_{00}|\psi _0& +c_{01}|\psi _{}& +c_{02}|r_0\\ \hfill |\alpha _1& =& c_{10}|\psi _0& +c_{11}|\psi _{}& +c_{12}|r_1\\ \hfill |\alpha _2& =& & & |r_2\end{array}$$
(23)
Since $`|\alpha _0`$, $`|\alpha _1`$, and $`|\alpha _2`$ still form a basis for $`\mathrm{\Omega }`$, from Eq. (20) it follows that,

$$\begin{array}{ccc}\hfill 32/n& <& \mathrm{Re}\underset{i}{}\alpha _i\left|U^{}\right|\alpha _i\hfill \end{array}$$
(24)
Since $`U^{}`$ is a unitary operator, we know that $`\mathrm{Re}\alpha _i\left|U^{}\right|\alpha _i1`$ for all $`|\alpha _i`$. Thus, applying this inequality to the first two terms in the sum, we obtain,

$$\mathrm{Re}\underset{i}{}\alpha _i\left|U^{}\right|\alpha _i2+\mathrm{Re}\alpha _2\left|U^{}\right|\alpha _2$$
(25)
Since, $`U^{}=U+\mathrm{\Delta }U`$, we can write

$$\mathrm{Re}\alpha _2\left|U^{}\right|\alpha _2=\mathrm{Re}\alpha _2\left|U\right|\alpha _2+\mathrm{Re}\alpha _2\left|\mathrm{\Delta }U\right|\alpha _2$$
(26)
Let us first consider $`\alpha _2\left|U\right|\alpha _2`$. We can expand $`|\alpha _2`$ in terms of the unperturbed eigenstates, $`|\alpha _2=_jb_j|\omega _j.`$ So, $`\mathrm{Re}\alpha _2\left|U\right|\alpha _2=_j\left|b_j\right|^2\mathrm{cos}\omega _j.`$ However, since $`\alpha _2|\psi _0=0`$, there is no contribution from the eigenvalue with value $`1`$. The eigenvalue with the next- largest real part is $`e^{i\omega _1}=12/n+i\frac{2}{n}\sqrt{n1}`$. Thus,

$$\mathrm{Re}\alpha _2\left|U\right|\alpha _212/n$$
(27)
Next, we consider, $`\alpha _2\left|\mathrm{\Delta }U\right|\alpha _2`$. Let $`|\psi _+=\frac{1}{\sqrt{2}}\left(|0,R+|1,L\right)`$. Using Eq. (15) we can express $`\mathrm{\Delta }U`$ in terms of $`|\psi _{}`$ and $`|\psi _+`$,

$$\mathrm{\Delta }U=|\psi _{}\psi _{}|+|\psi _{}\psi _+||\psi _+\psi _{}||\psi _+\psi _+|$$
(28)
But since $`\alpha _2|\psi _{}=0`$ (see Eq. (22)),

$$\alpha _2\left|\mathrm{\Delta }U\right|\alpha _2=\left(\left|\psi _+|\alpha _2\right|^2\right)0$$
(29)
Then, $`\mathrm{Re}\alpha _2\left|U^{}\right|\alpha _212/n.`$ Combining Eq. (25), Eq. (27), and Eq. (29), we obtain,

$$\mathrm{Re}\underset{i}{}\alpha _i\left|U^{}\right|\alpha _i32/n.$$
(30)
Since this contradicts Eq. (24), our assumption must be false.

###### Theorem 3

There are at least two eigenvalues of $`U^{}`$ on $`𝒜`$.

*Proof.* We will construct two approximate eigenvectors of $`U^{}`$, $`|\psi _0`$ and $`|\psi _1`$. $`|\psi _0`$ is given by Eq. (16). Using Eq. (15),

$$U^{}|\psi _0=|\psi _02/\sqrt{2^n}|L,1$$
(31)
And,

$$\begin{array}{ccc}\hfill \psi _0\left|U^{}\right|\psi _0& =& \psi _0|\psi _0\psi _0|L,1R,0|\psi _0\hfill \\ & =& 11/2^{n1}\hfill \end{array}$$
(32)
So, apart from a small residual, $`|\psi _0`$ is also “almost” an eigenvector of $`U^{}`$ with eigenvalue $`1`$. Now, we need to find a second approximate eigenvector, $`|\psi _1`$. Let

$$|\psi _1=\left(\underset{x=0}{\overset{n/21}{}}\frac{1}{\sqrt{2\left(\genfrac{}{}{0pt}{}{n1}{x}\right)}}|R,x\frac{1}{\sqrt{2\left(\genfrac{}{}{0pt}{}{n1}{x}\right)}}|L,x+1\right)/c$$
(33)
where $`c`$ is a normalization constant,

$$c=\sqrt{\underset{x=0}{\overset{n/21}{}}\frac{1}{\left(\genfrac{}{}{0pt}{}{n1}{x}\right)}}$$
(34)
Using this definition and Eq. (14), we see that

$$U^{}|\psi _1=|\psi _1\frac{1}{c\sqrt{2\left(\genfrac{}{}{0pt}{}{n1}{n/2}\right)}}\left(|R,n/21+|L,n/2+1\right)$$
(35)
So,

$$\psi _1\left|U^{}\right|\psi _1=1\frac{1}{2c^2\left(\genfrac{}{}{0pt}{}{n1}{n/2}\right)}$$
(36)
It is straightforward to show that $`1<c^2<1+2/n`$ for sufficiently large $`n`$. Thus, except for a small residual, $`|\psi _1`$ is “almost” an eigenvector of $`U^{}`$ with eigenvalue $`1`$.

Now let us verify that there is at least one eigenvalue of $`U^{}`$ on $`𝒜`$. Let us assume that there are no eigenvalues of $`U^{}`$ on $`𝒜`$. Then $`\mathrm{cos}\omega _j^{}<12/3n`$ for all $`j`$. Then using Eq. (32),

$$\begin{array}{ccc}\hfill 11/2^{n1}& =& \mathrm{Re}\psi _0\left|U^{}\right|\psi _0\hfill \\ & =& \underset{j}{}\left|\psi _0|\omega _j^{}\right|^2\mathrm{cos}\omega _j^{}\hfill \\ & <& \left(12/3n\right)\underset{j}{}\left|\psi _0|\omega _j^{}\right|^2\hfill \\ & =& 12/3n\hfill \end{array}$$
(37)
which is wrong for $`n>3`$. Hence our assumption is false and there must be at least one eigenvalue of $`U^{}`$ on $`𝒜`$.

Now let us assume there is exactly one eigenvalue of $`U^{}`$, $`e^{i\omega _0^{}}`$, on $`𝒜`$. Then,

$$\begin{array}{ccc}\hfill 1\frac{1}{2^{n1}}& =& \mathrm{Re}\psi _0\left|U^{}\right|\psi _0\hfill \\ & =& _j\left|\psi _0|\omega _j^{}\right|^2\mathrm{cos}\omega _j^{}\hfill \\ & =& \left|\psi _0|\omega _0^{}\right|^2\mathrm{cos}\omega _0^{}+_{j0}\left|\psi _0|\omega _j^{}\right|^2\mathrm{cos}\omega _j^{}\hfill \\ & & \left|\psi _0|\omega _0^{}\right|^2+\left(1\left|\psi _0|\omega _0^{}\right|^2\right)\left(12/3n\right)\hfill \end{array}$$
(38)
Rearranging terms,

$$\left|\psi _0|\omega _0^{}\right|^21\frac{3n}{2^n}$$
(39)
If we use $`|\psi _1`$ as a trial vector and follow the same arguments, we obtain the inequality

$$\left|\psi _1|\omega _0^{}\right|^21\frac{3n}{4c^2\left(\genfrac{}{}{0pt}{}{n1}{n/2}\right)}.$$
(40)
But since $`|\psi _0`$ and $`|\psi _1`$ are orthonormal, this leads to a contradiction, since,

$$\begin{array}{ccc}\hfill 1& =& \omega _0^{}|\omega _0^{}\hfill \\ & & \left|\psi _0|\omega _0^{}\right|^2+\left|\psi _1|\omega _0^{}\right|^2\hfill \\ & & 2\frac{3n}{2^n}\frac{3n}{4c^2\left(\genfrac{}{}{0pt}{}{n1}{n/2}\right)}\hfill \end{array}$$
(41)
which is not true for large $`n`$. Hence, there must be at least two eigenvalues on the arc $`𝒜`$.

As noted above, the eigenvalues and eigenvectors of $`U^{}`$ come in complex conjugate pairs. In particular the two eigenvalues on $`𝒜`$ must be a complex conjugate pair; let $`e^{\pm i\omega _0^{}}`$ be the two eigenvalues on $`𝒜`$. The corresponding eigenvectors obey $`|\omega _0^{}=|\omega _0^{}^{}`$ (if $`e^{i\omega _0^{}}=e^{i\omega _0^{}}=1`$, then we can construct linear combinations of $`|\omega _0^{}`$ and $`|\omega _0^{}`$ for which this statement is true). We will now show that $`|\pm \omega _0^{}`$ can be well-approximated by linear combinations of $`|\psi _0`$ and $`|\psi _1`$.

###### Theorem 4

$`|\omega _0^{}`$ $`=`$ $`\sqrt{p_0}|\psi _0+\sqrt{p_1}e^{i\eta }|\psi _1+\sqrt{1p_0p_1}|r_0`$
$`|\omega _0^{}`$ $`=`$ $`\sqrt{p_0}|\psi _0+\sqrt{p_1}e^{i\eta }|\psi _1+\sqrt{1p_0p_1}|r_0^{}`$ (42)
where $`p_0=\left|\omega _0^{}|\psi _0\right|^2=\left|\omega _0^{}|\psi _0\right|^2`$, $`p_1=\left|\stackrel{~}{\omega }_0^{}|\psi _1\right|^2=\left|\stackrel{~}{\omega }_0^{}|\psi _1\right|^2`$ and $`|r_0`$ is a normalized vector orthogonal to $`|\psi _0`$ and $`|\psi _1`$. Furthermore, $`1/2p_01/23n/2^{n+1}`$ and $`1/2p_11/2\frac{3n}{8c^2\left(\genfrac{}{}{0pt}{}{n1}{n/2}\right)}`$, with $`e^{i\eta }=i+\mathrm{\Delta }`$, where $`\left|\mathrm{\Delta }\right|=O\left(\frac{n}{\left(\genfrac{}{}{0pt}{}{n1}{n/2}\right)}\right)`$.

*Proof.* Since $`|\psi _0`$ and $`|\psi _1`$ are real vectors, $`\left|\omega _0^{}|\psi _0\right|^2=\left|\omega _0^{}|\psi _0\right|^21/2`$ and $`\left|\omega _0^{}|\psi _1\right|^2=\left|\omega _0^{}|\psi _1\right|^21/2`$. Using Eq. (32),

$$\begin{array}{ccc}\hfill 1\frac{1}{2^{n1}}& =& \mathrm{Re}\psi _0\left|U^{}\right|\psi _0\hfill \\ & =& _j\mathrm{cos}\omega _j^{}\left|\omega _j^{}|\psi _0^2\right|\hfill \\ & =& 2p_0\mathrm{cos}\omega _0^{}+_{j0}\mathrm{cos}\omega _j^{}\left|\omega _j^{}|\psi _0\right|^2\hfill \\ & <& 2p_0+\left(12/3n\right)\left(12p_0\right)\hfill \end{array}$$
(43)
Rearranging terms, we obtain,

$$p_01/2\frac{3n}{2^{n+1}}.$$
(44)
Using Eq. (36) and the same arguments as above we obtain

$$p_11/2\frac{3n}{8c^2\left(\genfrac{}{}{0pt}{}{n1}{n/2}\right)}.$$
(45)
Up to a global phase $`|\omega _0^{}`$ can be written as,

$$|\omega _0^{}=\left|\omega _0^{}|\psi _0\right||\psi _0+\left|\omega _0^{}|\psi _1\right|e^{i\eta }|\psi _1+\sqrt{1p_0p_1}|r_0$$
(46)
which yields Eq. (4) for $`|\omega _0^{}`$ and $`|\omega _0^{}`$.

To estimate $`e^{i\eta }`$ note that since $`|\omega _0^{}`$ and $`|\omega _0^{}`$ are eigenvectors of a unitary matrix, they must be orthogonal. Consequently,

$$\begin{array}{ccc}\hfill 0& =& \omega _0^{}|\omega _0^{}\hfill \\ & =& p_0+p_1\left(e^{i\eta }\right)^2+(1p_0p_1)r_0^{}|r_0\hfill \end{array}$$
(47)
Solving for $`e^{i\eta }`$, we obtain,

$`\mathrm{Re}\left(e^{i\eta }\right)^2`$ $`=`$ $`{\displaystyle \frac{p_0(1p_0p_1)\mathrm{Re}r_0^{}|r_0}{p_1}}`$ (48)
Assume $`\mathrm{Re}r_0^{}|r_00`$. Then, using $`1/(1x)1+2x`$ for small $`x`$ we get

$`1+{\displaystyle \frac{3n}{2^n}}`$ $``$ $`{\displaystyle \frac{p_0}{p_1}}`$ (49)
$``$ $`\mathrm{Re}\left(e^{i\eta }\right)^2{\displaystyle \frac{p_0+\left(\frac{3n}{2^{n+1}}+\frac{3n}{8c^2\left(\genfrac{}{}{0pt}{}{n1}{n/2}\right)}\right)}{p_1}}`$
$``$ $`12\left({\displaystyle \frac{3n}{2^{n+1}}}+{\displaystyle \frac{3n}{8c^2\left(\genfrac{}{}{0pt}{}{n1}{n/2}\right)}}\right)4\left({\displaystyle \frac{3n}{8c^2\left(\genfrac{}{}{0pt}{}{n1}{n/2}\right)}}\right)`$
which in turn implies that $`e^{i\eta }=i+\mathrm{\Delta }`$ with $`\left|\mathrm{\Delta }\right|=O\left(\frac{n}{\left(\genfrac{}{}{0pt}{}{n1}{n/2}\right)}\right)`$. A similar reasoning holds if $`\mathrm{Re}r_0^{}|r_00`$.

As a last ingredient we need to bound the angle $`\omega _0^{}`$. These bounds are provided in the following final theorem.

###### Theorem 5

$`\frac{1}{c\sqrt{2^{n1}}}\beta \omega _0^{}\frac{1}{c\sqrt{2^{n1}}}+\beta `$, where $`\beta =O\left(\frac{n^{3/2}}{2^n}\right)`$

*Proof.* We will approximate $`e^{i\omega _0^{}}=\omega _0^{}\left|U^{}\right|\omega _0^{}`$ by $`\alpha \left|U^{}\right|\alpha `$, where $`|\alpha =1/\sqrt{2}\left(|\psi _0+e^{i\eta }|\psi _1\right)`$. Let us first evaluate $`\left|e^{i\omega _0^{}}\alpha \left|U^{}\right|\alpha \right|`$. We can expand $`U^{}`$ in terms of its eigenvectors to obtain,

$$|e^{i\omega _0^{}}\alpha \left|U^{}\right|\alpha |=|e^{i\omega _0^{}}\underset{j}{}|\omega _j^{}|\alpha |^2e^{i\omega _j^{}}|$$
(50)
We then note that from Eq. (4),

$$\left|\omega _0^{}|\alpha \right|^2=\sqrt{p_0/2}+\sqrt{p_1/2}$$
(51)
So,

$$\begin{array}{ccc}\hfill \left|e^{i\omega _0^{}}\alpha \left|U^{}\right|\alpha \right|& =& |e^{i\omega _0^{}}(\sqrt{p_0/2}+\sqrt{p_1/2})e^{i\omega _0^{}}+\underset{|\omega _j^{}|\omega _0^{}}{}|\omega _j^{}|\alpha |^2e^{i\omega _j^{}}|\hfill \\ & & \left|e^{i\omega _0^{}}\left(1\sqrt{p_0/2}\sqrt{p_1/2}\right)\right|+\underset{|\omega _j^{}|\omega _0^{}}{}\left|\omega _j^{}|\alpha \right|^2\hfill \\ & & 2\left(1\sqrt{p_0/2}\sqrt{p_1/2}\right)\hfill \\ & & 2\left(\frac{3n}{2^{n+1}}+\frac{3n}{8c^2\left(\genfrac{}{}{0pt}{}{n1}{n/2}\right)}\right)\hfill \end{array}$$
(52)
with $`\sqrt{1x}1x`$ for $`0x1`$. Using the fact that the binomial coefficients approach the Gaussian distribution for large $`n`$, such that,

$$\left(\genfrac{}{}{0pt}{}{n}{x}\right)=\sqrt{\frac{2}{\pi n}}e^{\frac{xn/2}{n/2}}2^n$$
(53)
we can rewrite Eq. (52) taking the leading order terms in $`n`$. Recalling that $`c>1`$, we obtain,

$$\left|e^{i\omega _0^{}}\alpha \left|U^{}\right|\alpha \right|=O\left(\frac{n^{3/2}}{2^n}\right)$$
(54)
Eq. (54) is an explicit formula which bounds the distance in the complex plane between the eigenvalue of interest, $`e^{i\omega _0^{}}`$, and the matrix element $`\alpha \left|U^{}\right|\alpha `$. Fig. 3 shows the geometric representation of Eq. (54). Note that,

$$\left|\mathrm{sin}\omega _0^{}\mathrm{Im}\alpha \left|U^{}\right|\alpha \right|=\left|\mathrm{Im}\left(e^{i\omega _0^{}}\alpha \left|U^{}\right|\alpha \right)\right|\left|e^{i\omega _0^{}}\alpha \left|U^{}\right|\alpha \right|$$
(55)
Next, we evaluate $`\mathrm{Im}\alpha \left|U^{}\right|\alpha `$ using Eqs. (31) and (35),

$$\begin{array}{ccc}\hfill \mathrm{Im}\alpha \left|U^{}\right|\alpha & =& \mathrm{Im}\left(e^{i\eta }\psi _0\left|U^{}\right|\psi _1e^{i\eta }\psi _1\left|U^{}\right|\psi _0\right)\hfill \\ & =& \mathrm{Im}\frac{1}{2}\left(\frac{e^{i\eta }}{c\sqrt{2\left(\genfrac{}{}{0pt}{}{n1}{n/2}\right)}}\left(\psi _0|R,n/21+\psi _0|L,n/2+1\right)e^{i\eta }\left(\frac{2}{\sqrt{2^n}}\psi _1|L,1\right)\right)\hfill \\ & =& \mathrm{Im}\frac{e^{i\eta }}{c\sqrt{2^{n1}}}=\frac{1}{c\sqrt{2^{n1}}}O\left(\frac{n}{\sqrt{2^n}\left(\genfrac{}{}{0pt}{}{n1}{n/2}\right)}\right)\hfill \end{array}$$
(56)
Then, using Theorem (4), Eq. (54), and Eq. (56) we can write

$$\left|\mathrm{sin}\omega _0^{}+\frac{1}{c\sqrt{2^{n1}}}+O\left(\frac{n}{\sqrt{2^n}\left(\genfrac{}{}{0pt}{}{n1}{n/2}\right)}\right)\right|=O\left(\frac{n^{3/2}}{2^n}\right)$$
(57)
Using $`\mathrm{sin}x=x+O(x^3)`$ and keeping only leading order terms solving for $`\omega _0^{}`$ gives us,

$$\frac{1}{c\sqrt{2^{n1}}}O\left(\frac{n^{3/2}}{2^n}\right)\omega _0^{}\frac{1}{c\sqrt{2^{n1}}}+O\left(\frac{n^{3/2}}{2^n}\right).\text{ }$$
(58)
We can now quantitatively describe the overall operation of the algorithm. Starting with initial state $`|\psi _0`$, we consider the state of the computer after $`t`$ applications of $`U^{}`$. Then using Theorem (4) we can expand $`|\psi _0`$ as

$$|\psi _0=\sqrt{p_0}(|\omega _0^{}+|\omega _0^{})+\delta |r$$
(59)
where $`\delta =\sqrt{12p_0}=O(\sqrt{n/2^n})`$ and $`|r`$ is a residual normalized vector orthogonal to $`|\omega _0^{}`$ and $`|\omega _0^{}`$. Now

$$\begin{array}{ccc}\hfill \left(U^{}\right)^t|\psi _0& =& \sqrt{p_0}(e^{i\omega _0^{}t}|\omega _0^{}+e^{i\omega _0^{}t}|\omega _0^{})+\delta |r^{}\hfill \\ & =& 2p_0\mathrm{cos}\omega _0^{}t|\psi _02\sqrt{p_0p_1}(\mathrm{sin}\omega _0^{}t+\mathrm{Re}e^{i\omega _0^{}t}\mathrm{\Delta })|\psi _1\hfill \\ & +& \sqrt{1p_0p_1}(e^{i\omega _0^{}t}|r_0+e^{i\omega _0^{}t}|r_0^{})+\delta |r\hfill \\ & =& \mathrm{cos}\omega _0^{}t|\psi _0\mathrm{sin}\omega _0^{}t|\psi _1+O(\frac{n^{3/4}}{\sqrt{2^n}})|\stackrel{~}{r}\hfill \end{array}$$
(60)
where $`|\stackrel{~}{r}`$ is some residual normalized vector (not necessarily orthogonal to $`|\psi _0`$ and $`|\psi _1`$) .

Starting with $`|\psi _0`$ and applying $`U^{}`$ for $`t_f=\frac{\pi }{2\left|\omega _0^{}\right|}`$ steps, we approximately rotate from $`|\psi _0`$ to $`|\psi _1`$. From $`|\psi _1`$ we can obtain $`|\stackrel{}{x}_{target}=|\stackrel{}{0}`$ with high probability $`p`$, since from Eq. (33) and with $`1+1/2nc1+2/n`$ for large $`n`$

$$\begin{array}{ccc}\hfill p& =& \frac{1}{c}_d\left|d,0|\psi _1\right|^2=\frac{1}{c}\left|R,0|\psi _1\right|^2\hfill \\ & & \frac{1/2}{1+2/n}=\frac{1}{2}O\left(1/n\right)\hfill \end{array}$$
(61)
Finally, to obtain $`t_f`$ in terms of $`n`$, we make use of the bounds on $`\omega _0^{}`$ provided by Theorem (5):

$`t_f`$ $`=`$ $`{\displaystyle \frac{\pi c}{2}}\sqrt{2^{n1}}(1\pm O({\displaystyle \frac{n^{3/2}}{\sqrt{2^n}}}))`$ (62)
$`=`$ $`{\displaystyle \frac{\pi }{2}}\sqrt{2^{n1}}(1+O({\displaystyle \frac{1}{n}}))`$
If we set the number of time steps to be $`t_f=\frac{\pi }{2}\sqrt{2^{n1}}`$ (or the closest integer) then

$$\mathrm{sin}\omega _0^{}t_f=\mathrm{sin}\frac{\pi }{2}(1O(\frac{1}{n}))=1O(\frac{1}{n^2}).$$
(63)
So the probability to measure $`|\stackrel{}{x}_{target}`$ after $`t_f=\frac{\pi }{2}\sqrt{2^{n1}}`$ steps is still $`p_{success}=1/2O(1/n)`$. Hence, by repeating the algorithm a constant number of times, the probability of error can be made arbitrarily small. Note the periodic nature of the evolution under $`U^{}`$ (Eq. (60)); this means that if we measure at $`t>t_f`$ the probability of success will decrease and later increase again.

In summary we arrived at the final result that the marked state is identified after $`O(\sqrt{N})`$ calls to the oracle.

## IV Connection to Grover’s Algorithm

The operation of the random walk search algorithm is similar in many ways to the operation of Grover’s search algorithm. Both algorithms begin in the equal superposition state over all bit strings. Both algorithms make use of the Grover diffusion operator, $`G`$, (sometimes known as the Grover iterate). Both algorithms can be viewed as a rotation in a two-dimensional subspace. Both algorithms use an oracle which marks the target state with a phase of $`1`$. Both algorithms have a running time of $`O\left(\sqrt{N}\right)`$. In both algorithms we have to measure at a specific time to obtain maximum probability of success. However, there are several important differences between the two search algorithms. In this section, we call attention to the ways in which the random walk search algorithm is distinct from Grover’s algorithm and consider how these differences affect performance and implementation.

It is well-known that Grover’s algorithm can be mapped exactly onto a rotation in the two-dimensional subspace spanned by the equal-superposition state $`|\psi _0`$ and the marked state $`|0`$ Grover (1996). Each iteration in Grover’s algorithm corresponds to a rotation in this subspace. In this paper, we have shown that the random walk search algorithm can also be viewed as a rotation in a two-dimensional subspace. However, there are two important distinctions. First, the random walk search algorithm can only be *approximately* mapped onto a two-dimensional subspace. Unlike Grover’s algorithm, this mapping is not exact. Second, the two-dimensional subspace in which the random walk search algorithm is approximately contained is spanned by $`|\psi _0`$ and $`|\psi _1`$, not by $`|\psi _0`$ and $`|0`$. Hence, the final state of the algorithm is not exactly the pure marked state, $`|0`$, as it is in Grover’s algorithm. It is a linear combination of states which is composed primarily of the marked state, but also possesses small contributions from its nearest neighbors, second-nearest neighbors, etc. Thus, the random walk search algorithm contains traces of the underlying topology of the hypercube on which it is based.

Another difference between the two algorithms is their use of the Grover diffusion operator, $`G`$. In Grover’s algorithm, this operator is applied to the entire $`2^n`$-dimensional search space (corresponding to the node space in the random walk search algorithm). On the other hand, Grover’s diffusion operator, $`G`$, in the random walk algorithm is used as the quantum coin, and acts only on the $`n`$-dimensional coin space. This fact may be of practical use for certain physical implementations since many physical implementations of quantum computers contain multiple types of qubits, which have different natural gate sets. We could exploit this variety using the random walk search algorithm by choosing the coin space to be represented by qubits on which it is convenient to implement the Grover diffusion operator.

Another similarity between the two algorithms is the implementation of the oracle. In Grover’s algorithm, the oracle marks the target state with a phase of $`1`$. To arrive at this random walk search algorithm, we chose the marking coin $`C_1`$ to be the $``$ coin. This choice was actually motivated because it yielded a result that was amenable to analysis, and while the emergence of Grover s algorithm appears natural in hindsight, it was not obvious at the outset. However, more generally, it is not clear whether this choice of marked coin is either optimal or unique. In fact, numerical simulations have shown us that many different types of marking coins will yield search algorithms. Unfortunately, analytic treatment of the quantum random walk for more complicated coins has proven substantially more difficult than the instance analyzed here for $`C_1=`$. It is an open question what (constant factor) gains might be made by using different marking coins to implement the search.

## V Conclusions

In this paper, we have shown that the random walk search algorithm can search a list of $`2^n`$ items in time proportional to $`\sqrt{2^n}`$. The lower bound on a quantum search of an $`N`$-item list is known to be $`\mathrm{\Omega }\left(\sqrt{N}\right)`$Bennett et al. (1997). Thus, up to a constant factor, the random walk search algorithm is optimal. However, although after repetition of the algorithm a constant number of times the result is arbitrarily close to the result of Grover’s search, the random walk search algorithm is not identically equivalent to Grover’s algorithm. In particular, the final solution obtained by the random walk search still retains some of the underlying character of the hypercube on which it was based, with a small admixture of states other than the solution at the marked node.

The random walk search analyzed here was based on a discrete walk on the hypercube. In general a similar methodology can be applied to any regular graph, e.g., a two-dimensional hexagonal lattice with periodic boundary conditions, a three-dimensional rectangular lattice with periodic boundary conditions, etc. We have numerical evidence indicating that this methodology will yield quantum search algorithms when applied to other regular $`n`$-dimensional lattices. Future studies will investigate the extent of optimality of such search algorithms.

The intriguing possibility of finding novel algorithms based on the random walk also remains an open question. The results described here indicate that the random walk search algorithm provides a suggestive framework for new algorithms. Though the optimality of Grover’s algorithm precludes the construction of an improved oracle-based search algorithm based on a quantum walk, nevertheless, many other oracle problems still exist for which a quantum walk may be advantageous. For instance, the lower bound on quantum search holds only for oracles which provide “yes/no” information Bennett et al. (1997). Our choice of marking coin here has a clear relation to an identifiable component of Grover’s algorithm. In general, the marking coin can be an arbitrary $`n\times n`$ unitary matrix. The marking coin provides a intuitive means by which to introduce a large amount of information to an oracle problem. Thus, it is possible that unique coins with interesting properties may give rise to an entirely new algorithm. Overall we conclude that the quantum random walk provides a means for insight into existing quantum algorithms and offers a potentially vast source for development of new algorithms.

###### Acknowledgements.

NS thanks the University of California, Berkeley, for a Berkeley Fellowship. This effort is sponsored by the Defense Advanced Research Projects Agency (DARPA) and the Air Force Laboratory, Air Force Material Command, USAF, under agreement number F30602-01-2- 0524. We also thank NSF ITR/SY award 0121555.