text:
# Quantum Walks driven by many coins

## I Introduction

In the classical discrete random walk, a particle is located at one of a set of positions. In response to a random event (such as the flipping of a coin), the particle moves in one direction or another. This sequence is repeated, and the motion of the particle is analyzed statistically. These systems provide good models for diffusion and other stochastic processes.

Considerable work has been done recently on quantum random walks. Quantum walks differ from classical walks in that their evolution is unitary and therefore reversible. Two classes of models have been studied: continuous Farhi and Gutmann (1998); Childs et al. (2002a, b) and discrete Aharonov et al. (1993); Meyer (1996); Nayak and Vishwanath (2000); Aharonov et al. (2001); Ambainis et al. (2001); Meyer and Blumer (2001); Moore and Russell (2001); MacKay et al. (2002); Kempe (2002); Konno et al. (2002); Konno (2002a, b); Travaglione and Milburn (2002); Du et al. (2002); Yamasaki et al. (2002); Sanders et al. (2002); Dür et al. (2002); Bach et al. (2002); Kendon and Tregenna (2002a), random walks. This paper is concerned solely with the discrete case.

A naïve generalization of the classical random walk behaves in a rather boring way: if its evolution is unitary, it can only move in one direction and keep on going that way Meyer (1996). To produce nontrivial behavior, we introduce an extra “coin” degree of freedom (usually a single quantum bit) into the system. Just as in the classical random walk, the outcome of a “coin flip” determines which way the particle moves; but in the quantum case, both the “flip” of the coin and the conditional motion of the particle are represented by unitary transformations; thus, there can be interference between different classical paths.

This paper is concerned with quantum walks on the infinite line. The particle is initially located at position $`x=0`$ and is free to travel off to infinity in either direction. We will primarily consider the position of the particle after some number of flips $`t`$. At this point, we assume that the position is measured. We will look at both the probability distribution $`p(x,t)=|x|\psi (t)|^2`$, and at the long-time behavior of the moments $`\widehat{x}`$ and $`\widehat{x}^2`$ as functions of $`t`$.

Unitary random walks behave quite differently from classical random walks. For a classical walk, $`p(x,t)`$ has approximately the form of a Gaussian distribution (actually, a binomial distribution), with a width which spreads like $`\sqrt{t}`$; the variance $`\overline{x^2}\overline{x}^2`$ grows linearly with time. The variance in the quantum walk, by contrast, grows quadratically with time; and the distribution $`p(x,t)`$ has a complicated, oscillatory form. Both of these are effects of interference between the possible paths of the particle.

It should be possible to recover the classical behavior as some kind of limit of the quantum system. There are two obvious ways to regain the classical result. If the quantum coin is measured at every step, then the record of the measurement outcomes singles out a particular classical path. By averaging over all possible measurement records, one recovers the usual classical behavior MacKay et al. (2002).

Alternatively, rather than re-using the same coin every time, one could replace it with a new quantum coin for each flip. After a time $`t`$ one would have accumulated $`t`$ coins, all of them entangled with the position of the particle. By measuring them, one could reconstruct an unique classical path; averaging over the outcomes would once again produce the classical result. It is actually unnecessary, however, to measure the coins. Simply by tracing them out, one leaves the particle in the mixed state

$$\rho =\underset{x}{}p(x,t)|xx|,$$
(I.1)
where $`p(x,t)`$ is the probability distribution obtained after $`t`$ steps of a classical random walk.

It is therefore certainly possible to recover the classical limit. But these two approaches give two different routes from quantum to classical. We might increase the number of coins used to generate the walk, cycling among $`M`$ different coins, in the limit using a new coin at each step. Or we might weakly measure the coin after each step, reaching the classical limit with strong, projective measurements. This is equivalent to having the coin decohere with time.

In this paper we look at quantum random walks with multiple coins. (The case with a decoherent coin is considered elsewhere Brun et al. (2002b, a); systems with decoherence of the particle have also been considered Dür et al. (2002); Kendon and Tregenna (2002a, b).) We begin by reviewing the approaches to solving the single-coin walk. We extend these to walks with multiple coins, and derive expressions for the amplitudes of an $`M`$-coin walk which we can evaluate numerically. We look at the long-time behavior of the moments of position both numerically and analytically, and compare it to the usual classical random walk.

## II The one-coin quantum walk

Since our results will utilize the amplitudes for the single-coin quantum walk, we first go quickly over the single-coin derivation. We then make use of this in the following section to write down exact expressions for the multi-coin case.

There are two main approaches to analyzing quantum walks. One is to use Fourier analysis, which gives a good qualitative insight into the behavior of the system, but gives solutions for the wavefunction in terms of some rather unpleasant integrals. Indeed, no exact solution to them is known, and so they must be approximated in the limit as $`t\mathrm{}.`$ The approximation methods become progressively more impractical as the number of coins increases; we examine these asymptotic expressions in Appendix B.

The other approach employs combinatorics. This gives expressions which are opaque, but are exact for all times. However, evaluating these expressions exactly is prohibitive for long times, and so approximation methods are again required for the long time limit.

### II.1 Fourier Analysis of Quantum Walks

Following the analysis in Nayak and Vishwanath (2000) we consider the Hadamard walk, in which each coin performs the evolution

$`|\mathrm{R}`$ $``$ $`\widehat{H}|\mathrm{R}={\displaystyle \frac{1}{\sqrt{2}}}\left(|\mathrm{R}+|\mathrm{L}\right)`$
$`|\mathrm{L}`$ $``$ $`\widehat{H}|\mathrm{L}={\displaystyle \frac{1}{\sqrt{2}}}\left(|\mathrm{R}|\mathrm{L}\right)`$ (II.1)
at each time step for which that coin is active, where $`\mathrm{R}`$ and $`\mathrm{L}`$ can be respectively thought of as the “heads” and “tails” states of the coin, or equivalently as an internal chirality state of the particle. The value of the coin controls the direction in which the particle moves. When the coins shows “R” the particle moves right; when it shows “L” the particle moves left.

Let $`\{|x\}`$ be the position states of the particle, where the values $`x`$ are integers. We define a unitary shift operator

$$\widehat{S}|x=|x+1,\widehat{S}^1|x=\widehat{S}^{}|x=|x1.$$
(II.2)
If $`\widehat{𝒫}_R=|RR|`$ and $`\widehat{𝒫}_L=|LL|`$ are projectors onto the two states of the coin, then one step of the quantum walks is given by the unitary operator

$$\widehat{E}=(\widehat{S}\widehat{𝒫}_R+\widehat{S}^{}\widehat{𝒫}_L)(\widehat{I}\widehat{H}).$$
(II.3)
If the initial state of the position and coin is $`|\mathrm{\Psi }_0`$, then after $`t`$ steps of the walk the state is

$$|\mathrm{\Psi }(t)=\widehat{E}^t|\mathrm{\Psi }_0.$$
(II.4)
For the purposes of this paper, we will usually assume that the coin starts in the state $`|R`$.

Consider the wave function of the position of the particle. For a one coin walk, this wavefunction has just two amplitude components, which are labeled by their chiralities:

$$\mathrm{\Psi }(x,t)=\left(\begin{array}{c}a_R(x,t)\\ a_L(x,t)\end{array}\right).$$
(II.5)
In Dirac notation this is

$$|\mathrm{\Psi }(t)=\underset{x}{}|x\left(a_R(x,t)|R+a_L(x,t)|L\right).$$
(II.6)
We would like to solve for $`a_{L,R}(x,t)`$ explicitly. We can do this by diagonalizing the operator $`\widehat{E}`$. Following the analysis in Nayak and Vishwanath (2000), we use the spatial discrete Fourier transformation, $`\stackrel{~}{a}_{L,R}(k,t)`$ for $`k[\pi ,\pi ]`$

$`|\mathrm{\Psi }(t)`$ $`=`$ $`{\displaystyle _\pi ^\pi }|k\left(\stackrel{~}{a}_R(k,t)|R+\stackrel{~}{a}_L(k,t)|L\right){\displaystyle \frac{dk}{2\pi }},`$
$`\stackrel{~}{a}_{L,R}(k,t)`$ $`=`$ $`{\displaystyle \underset{x=\mathrm{}}{\overset{\mathrm{}}{}}}a_{L,R}(x,t)e^{ikx},`$
$`|k`$ $`=`$ $`{\displaystyle \underset{x=\mathrm{}}{\overset{\mathrm{}}{}}}|xe^{ikx},`$ (II.7)
where the usual integral is replaced by a sum, as the variable $`x`$ is discrete. We note that these “momentum” states $`|k`$ are eigenstates of the shift operator $`\widehat{S}`$ and its inverse:

$$\widehat{S}|k=e^{ik}|k,\widehat{S}^{}|k=e^{ik}|k.$$
(II.8)
These states are not normalizable; but we can think of them as the limit of the case where the number of position states is large but finite.

In this momentum basis, the effect of the evolution is given by the matrix

$$\widehat{H}_k=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}e^{ik}& e^{ik}\\ e^{ik}& e^{ik}\end{array}\right).$$
(II.9)
Since this is just a 2-by-2 matrix, it is easily diagonalized, and the final state found in terms of its eigenvectors and eigenvalues. The method of solution is now straightforward in principle, though complicated in detail. One first represents the initial state in the $`\{|k\}`$ basis; applies the diagonal form of the matrix $`H_k`$ $`t`$ times; and re-expresses the result in the original $`\{|x\}`$ and $`|R,|L`$ bases.

Nayak and Vishwanath Nayak and Vishwanath (2000) carried out this program and got exact results. For an initial state $`|\mathrm{\Psi }_0=|0|R`$,

$`a_L(x,t)`$ $`=`$ $`{\displaystyle \frac{1+(1)^{x+t}}{2}}{\displaystyle _\pi ^\pi }{\displaystyle \frac{dk}{2\pi }}\left(1+{\displaystyle \frac{\mathrm{cos}k}{\sqrt{1+\mathrm{cos}^2k}}}\right)e^{i(\omega _kt+kx)},`$
$`a_R(x,t)`$ $`=`$ $`{\displaystyle \frac{1+(1)^{x+t}}{2}}{\displaystyle _\pi ^\pi }{\displaystyle \frac{dk}{2\pi }}{\displaystyle \frac{e^{ik}}{\sqrt{1+\mathrm{cos}^2k}}}e^{i(\omega _kt+kx)}.`$ (II.10)
In the exponents, we define the frequencies $`\omega _k`$ by $`\mathrm{sin}\omega _k=\sqrt{1/2}\mathrm{sin}k`$, taking $`\omega _k[\pi /2,\pi /2]`$.

These integrals, while exact, are difficult to evaluate. Nayak and Vishwanath found an approximation to these results, valid in the limit of large $`t`$, by making an asymptotic expansion of the integrals, to get the approximate expressions

$`a_L(x,t)`$ $``$ $`{\displaystyle \frac{1+(1)^{x+t}}{\sqrt{8\pi t(1x^2/t^2)\sqrt{12x^2/t^2}}}}`$
$`\times (1x/t)(\mathrm{exp}i(t\varphi (x/t)+\pi /4)+\mathrm{c}.\mathrm{c}.),`$
$`a_R(x,t)`$ $``$ $`{\displaystyle \frac{1+(1)^{x+t}}{\sqrt{8\pi t(1x^2/t^2)\sqrt{12x^2/t^2}}}}`$ (II.11)
$`\times ((x/t+i\sqrt{12x^2/t^2})\mathrm{exp}i(t\varphi (x/t)+\pi /4)+\mathrm{c}.\mathrm{c}.).`$
The results are conveniently represented in terms of a variable $`\alpha =x/t`$. This approximation is valid only within the range $`\sqrt{1/2}<\alpha <\sqrt{1/2}`$; outside this range the amplitude becomes negligibly small. The phase $`\varphi (\alpha )`$ is given by

$$\varphi (\alpha )=\mathrm{arcsin}\sqrt{\frac{12\alpha ^2}{22\alpha ^2}}+\alpha \mathrm{arcsin}\sqrt{\frac{12\alpha ^2}{11\alpha ^2}}.$$
(II.12)
### II.2 Combinatorial Analysis

We can do a completely different analysis of the one-coin walk, using a combinatorial rather than a Fourier argument, similar to that done in Meyer (1996) and Ambainis et al. (2001). Suppose we start with $`x=0`$ and the coin in state $`|R`$. We see how the state evolves after the first few flips of the coin:

$`|\mathrm{\Psi }_0`$ $`=`$ $`|0|R,`$
$`|\mathrm{\Psi }(1)`$ $`=`$ $`\sqrt{1/2}\left(|1|R+|1|L\right),`$
$`|\mathrm{\Psi }(2)`$ $`=`$ $`\sqrt{1/2^2}\left(|2|R+|0|L+|0|R|2|L\right).`$ (II.13)
At time $`t`$ there will be $`2^t`$ terms, each with amplitude $`\pm \sqrt{1/2^t}`$. Each of these terms corresponds to a possible path for a classical random walk. To get the amplitude for a particular position $`x`$, conditioned on the coin showing R or L, one must sum up the amplitudes for all the paths which end at the position $`x`$ with the appropriate coin face showing. This amounts to a nice problem in combinatorics.

For the coin to reach position $`x`$ at time $`t`$, it must have moved to the left a total of $`N_L=(tx)/2`$ times, and to the right a total of $`N_R=(t+x)/2`$ times. For a term corresponding to a given classical path, it turns out that the phase depends only on the values of $`N_L`$ and $`N_R`$, and the number $`C`$ of clusters of consecutive L flips. The details of the derivation are given in Appendix A, so we just quote the answer here:

$`a_L(x,t)`$ $`={\displaystyle \frac{1}{\sqrt{2^t}}}\left[{\displaystyle \underset{C=1}{\overset{\mathrm{`}\mathrm{`}N\mathrm{"}}{}}}(1)^{N_LC}\left({\displaystyle \genfrac{}{}{0pt}{}{N_L1}{C1}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{N_R}{C1}}\right)\right],`$
$`a_R(x,t)`$ $`={\displaystyle \frac{1}{\sqrt{2^t}}}\left[{\displaystyle \underset{C=1}{\overset{\mathrm{`}\mathrm{`}N\mathrm{"}}{}}}(1)^{N_LC}\left({\displaystyle \genfrac{}{}{0pt}{}{N_L1}{C1}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{N_R}{C}}\right)\right],`$ (II.14)
where the summation is to $`N_L`$ for $`x0`$ and to $`N_R+1`$ for $`x<0`$ (but only for $`N_L0`$; for $`N_L=0`$ the amplitude is always $`2^{t/2}`$). We can, of course, re-express $`N_R`$ and $`N_L`$ as functions of $`x`$ and $`t.`$

If we had started instead with the coin in the state $`|L`$, the amplitudes would then become

$`b_L(x,t)`$ $`={\displaystyle \frac{1}{\sqrt{2^t}}}\left[{\displaystyle \underset{C=1}{\overset{\mathrm{`}\mathrm{`}N\mathrm{"}}{}}}(1)^{N_LC}\left({\displaystyle \genfrac{}{}{0pt}{}{N_L1}{C1}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{N_R}{C1}}\right){\displaystyle \frac{N_R2C+2}{N_R}}\right],`$
$`b_R(x,t)`$ $`={\displaystyle \frac{1}{\sqrt{2^t}}}\left[{\displaystyle \underset{C=1}{\overset{\mathrm{`}\mathrm{`}N\mathrm{"}}{}}}(1)^{N_LC}\left({\displaystyle \genfrac{}{}{0pt}{}{N_L1}{C1}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{N_R}{C}}\right){\displaystyle \frac{N_R2C}{N_R}}\right],`$ (II.15)
where the summation is to $`N_L`$ for $`x0`$ and to $`N_R+1`$ for $`x<0`$, and $`N_L=0`$ is done separately, as before.

The solution given by Eq. (II.2) looks very different from that given by Eq. (II.10); it is rather extraordinary that they should describe exactly the same outcome. Moreover, a long-time approximation similar to Eq. (II.11) can be derived from Eq. (II.2), by using the asymptotics of Jacobi polynomials. See Ambainis et al. (2001) for details.

If the coin starts in an arbitrary state

$$\psi _{\mathrm{init}}=\alpha |R+\beta |L$$
(II.16)
the amplitudes will be

$`g_L(x,t)`$ $`=\alpha a_L(x,t)+\beta b_L(x,t)`$ (II.17)
$`g_R(x,t)`$ $`=\alpha a_L(x,t)+\beta b_L(x,t),`$ (II.18)
respectively.

## III Walks with multiple coins

For a walk driven by $`M`$ coins, the wavefunction has $`2^M`$ components; for example, a two coin walk will be described by the wavefunction

$$|\mathrm{\Psi }(x,t)=\left(\begin{array}{c}a_{RR}(x,t)\\ a_{RL}(x,t)\\ a_{LR}(x,t)\\ a_{LL}(x,t)\end{array}\right).$$
(III.1)
At each step, the particle moves in the direction dictated by the coin that is active at that step, with the other coins remaining inert until it is their turn once again. We will initially assume that we cycle through the coins in a deterministic, regular way, although we will discover later that we can relax that condition in certain specific ways.

The unitary transformation which results from flipping the $`m`$th coin is

$$\widehat{E}_m=(\widehat{S}\widehat{𝒫}_{Rm}+\widehat{S}^{}\widehat{𝒫}_{Lm})(\widehat{I}\widehat{H}_m),$$
(III.2)
where $`\widehat{H}_m`$ is the Hadamard transformation on the $`m`$th coin, and $`\widehat{𝒫}_{L,Rm}`$ is the projector onto the $`m`$th coin being in state L or R, respectively. If we cycle among the coins, doing a total of $`t`$ flips ($`t/M`$ flips with each coin), then the state will be

$$|\mathrm{\Psi }(Mt)=(\widehat{E}_M\mathrm{}\widehat{E}_1)^{t/M}|\mathrm{\Psi }_0.$$
(III.3)
We have simulated this system numerically for different numbers $`M`$ of coins. The probability distributions $`p(x,t)`$ agree with the classical results only up to $`t=M`$; beyond that, they diverge sharply, with the multicoin distributions exhibiting highly oscillatory behavior and rapid spreading (linear with $`t`$), similar to the behavior of the single-coin case. (See figure 1.)

How can we understand these $`M`$-coin results? An important thing to notice is that these $`M`$ unitary transformations $`\{\widehat{E}_m\}`$ all commute:

$$[\widehat{E}_m,\widehat{E}_n]=0.$$
(III.4)
Because of that, the order in which they are listed is irrelevant. We can equally well write

$$|\mathrm{\Psi }(Mt)=(\widehat{E}_M)^{t/M}\mathrm{}(\widehat{E}_1)^{t/M}|\mathrm{\Psi }_0.$$
(III.5)
We can either let the walk evolve for $`t`$ steps using $`M`$ coins, or we could use one coin for $`t/M`$ steps, and then replace the coin with another one, and use that for another $`t/M`$ steps, and so on, until we’ve used all $`M`$ coins. The final probability distribution will be the same.

Suppose we decide to use our coins cyclically. Then it can be seen that at the end of the walk, the $`M`$ coins act as a quantum memory of the last $`M`$ moves that the particle made. The “which path” information from before then is lost, so we will see interference between paths arising from moves dating from before that time.

Now consider $`M`$ walks controlled by one coin each, concatenated in the following recipe: Do the first one-coin walk. Measure the final state of the coin only, doing nothing that would give any further information about the position of the particle. Reset the coin state to the appropriate starting state for the next walk, and use the conditioned state produced by the measurement as the starting state for the next one-coin walk. Repeat this procedure until you’ve concatenated $`M`$ walks in this way. The *final* probability distribution obtained after the last coin has been measured will be exactly the same as the on obtained after measuring the $`M`$ coins from the single cyclic $`M`$ coin walk.

How can we use this to solve the multicoin walk? Assume (for the moment) that the coins all start in the state $`|R`$, and the particle starts in the state $`|0`$. We flip the coins $`t/M`$ times each (with $`t/M`$ even for convenience). After each coin has been flipped $`t/M`$ times, we measure it, and find it in state L or R. We then define conditional evolution operators for the particle position:

$`\widehat{A}_L(t)`$ $`=`$ $`{\displaystyle \underset{j=t/2M}{\overset{t/2M1}{}}}a_L(2j,t/M)\widehat{S}^{2j}`$
$`\widehat{A}_R(t)`$ $`=`$ $`{\displaystyle \underset{j=t/2M+1}{\overset{t/2M}{}}}a_R(2j,t/M)\widehat{S}^{2j},`$ (III.6)
where $`x=2j.`$ If we flipped $`M`$ coins $`t/M`$ times each and then measured them, getting $`N`$ results R and $`MN`$ results L, then the particle must have ended up in the (unnormalized) state

$$\left[\widehat{A}_R(t)\right]^N\left[\widehat{A}_L(t)\right]^{MN}|0.$$
(III.7)
The probability of the particle arriving at the final position $`x`$ at time $`Mt`$ is then $`p(x,Mt)=|\mathrm{\Psi }(x,Mt)|^2,`$ which is

$$p(x,Mt)=\underset{N=0}{\overset{M}{}}\left(\genfrac{}{}{0pt}{}{M}{N}\right)|x|\left[\widehat{A}_R(t)\right]^N\left[\widehat{A}_L(t)\right]^{MN}|0|^2.$$
(III.8)
Note that this distribution doesn’t depend on the order in which the coins were flipped, nor the order in which the measurement results occurred, provided that the measurement on coin $`m`$ was made after it had been flipped exactly $`t/M`$ times.

For the amplitudes $`a_{L,R}(x,t)`$ in (III.6), we can use any of the expressions (II.10), (II.11), or (II.2), whichever is convenient. We can also calculate them numerically; Eq. (III.8) provides a much more practical method of numerical calculation for multicoin systems than direct simulation, which requires a Hilbert space that grows exponentially in dimension with the number of coins. By contrast, the difficulty of evaluating (III.8) grows only linearly with the number of coins. We have used this to simulate systems with large numbers of coins, which would otherwise be impractical; see, e.g., figure 2.

One can find asymptotic expressions for $`p(x,t)`$ at long times which are analogous to the single-coin expressions (II.11), though the difficulties mount rapidly with the number of coins. We plot the approximate solution for two coins in figure 3, which matches the numerical results of figure 1b quite well. For details of the calculation, see Appendix B.

While having points of similarity, these multicoin walks differ from the tensor product walks studied in MacKay et al. (2002), in which each component in the tensor product corresponds to a different spatial dimension. There are also points of similarity to quantum Parrondo games, as studied in Meyer and Blumer (2001).

## IV Moments of the distributions

While the probability distributions $`p(x,t)`$ for the quantum random walk clearly differ markedly from their classical counterparts, it is difficult to use this to give a quantitative criterion for quantum vs. classical behavior. In particular, we would like to know if the quantum walks become “more classical” in any meaningful sense as we let $`Mt`$. It would be useful to look at one or two numbers instead of the entire probability distribution in answering this question.

One obvious criterion suggested by the single-coin case is to look at the long-time behavior of the moments of $`p(x,t)`$, and see if (for instance) the variance increases linearly or quadratically with time. Since it becomes more and more difficult to calculate $`p(x,t)`$ as we increase $`M`$, this might seem like an unhelpful approach; but as it happens, we can extract expressions for the long time behavior of the moments without having to evaluate $`p(x,t)`$ itself Brun et al. (2002b).

Note that in the following two subsections, we fix the number of coins $`M`$ (or more generally the dimension $`D`$ of the “coin”) and then go to the long-time limit. What constitutes a long time will depend on the choice of $`M`$ or $`D`$. In the final subsection, we let the number of coins used (or the dimension of the “coin”) increase with time, and look at the long-time limit in that case.

### IV.1 The general case

Let’s consider a very general linear random walk, which includes the multicoin case as a subcase. Let the “coin” be a $`D`$-dimensional system with an initial state $`|\mathrm{\Phi }_0`$; let $`\widehat{𝒫}_{R,L}`$ be two orthogonal projectors on the Hilbert space of the coin, such that $`\widehat{𝒫}_R+\widehat{𝒫}_L=\widehat{I}`$, and $`\mathrm{Tr}\widehat{𝒫}_R=\mathrm{Tr}\widehat{𝒫}_L=D/2`$. We also define a unitary transformation $`\widehat{U}`$ which “flips” the coin. Then one step of the quantum random walk is given by the unitary operator

$$\widehat{E}\left(\widehat{S}\widehat{𝒫}_R+\widehat{S}^{}\widehat{𝒫}_L\right)\left(\widehat{I}\widehat{U}\right),$$
(IV.1)
where $`\widehat{S},\widehat{S}^{}`$ are the usual shift operators (II.2) on the particle position. The full initial state of the system (particle and coin) is

$$|\mathrm{\Psi }_0=|0|\mathrm{\Phi }_0.$$
(IV.2)
We can identify the eigenvectors $`|k`$ of $`\widehat{S},\widehat{S}^{}`$, with eigenvalues $`\mathrm{exp}(ik)`$, as defined in (II.7). In particular,

$$|0=_\pi ^\pi \frac{dk}{2\pi }|k.$$
(IV.3)
In the $`k`$ basis, the evolution operator becomes

$`\widehat{E}\left(|k|\mathrm{\Phi }\right)`$ $`=`$ $`|k\left(\mathrm{e}^{ik}\widehat{𝒫}_R+\mathrm{e}^{ik}\widehat{𝒫}_L\right)\widehat{U}|\mathrm{\Phi },`$ (IV.4)
$``$ $`|k\widehat{U}_k|\mathrm{\Phi },`$
where $`\widehat{U}_k`$ is a unitary operator on the coin degree of freedom.

Let the quantum random walk proceed for $`t`$ steps. Then the state evolves to

$`|\mathrm{\Psi }_0=|0|\mathrm{\Phi }_0`$ $``$ $`\widehat{E}^t|\mathrm{\Psi }_0`$ (IV.5)
$`={\displaystyle _\pi ^\pi }{\displaystyle \frac{dk}{2\pi }}|k\left(\widehat{U}_k\right)^t|\mathrm{\Phi }_0|\mathrm{\Psi }(t).`$
The probability to reach a point $`x`$ at time $`t`$ is

$`p(x,t)`$ $`=`$ $`\mathrm{\Psi }(t)|\left(|xx|\widehat{I}\right)|\mathrm{\Psi }(t)`$ (IV.6)
$`=`$ $`{\displaystyle \frac{1}{(2\pi )^2}}{\displaystyle 𝑑k𝑑k^{}k|xx|k^{}\mathrm{\Phi }_0|\left(\widehat{U}_k^{}\right)^t\left(\widehat{U}_k^{}\right)^t|\mathrm{\Phi }_0}`$
$`=`$ $`{\displaystyle \frac{1}{(2\pi )^2}}{\displaystyle 𝑑k𝑑k^{}\mathrm{e}^{ix(kk^{})}\mathrm{\Phi }_0|\left(\widehat{U}_k^{}\right)^t\left(\widehat{U}_k^{}\right)^t|\mathrm{\Phi }_0}.`$
This will, in general, be difficult to calculate. However, all we are interested in are the moments of this distribution:

$`\widehat{x}^m_t`$ $`=`$ $`{\displaystyle \frac{1}{(2\pi )^2}}{\displaystyle \underset{x}{}}x^mp(x,t)`$ (IV.7)
$`=`$ $`{\displaystyle \frac{1}{(2\pi )^2}}{\displaystyle \underset{x}{}}x^m{\displaystyle 𝑑k𝑑k^{}\mathrm{e}^{ix(kk^{})}\mathrm{\Phi }_0|\left(\widehat{U}_k^{}\right)^t\left(\widehat{U}_k^{}\right)^t|\mathrm{\Phi }_0}.`$
We can then invert the order of operations and do the $`x`$ sum first. This sum can be exactly carried out in terms of derivatives of the delta function:

$$\frac{1}{2\pi }\underset{x}{}x^m\mathrm{e}^{ix(kk^{})}=(i)^m\delta ^{(m)}(kk^{}).$$
(IV.8)
Inserting this result back into our expression for $`x^m_t`$ yields

$$\widehat{x}^m_t=\frac{(i)^m}{2\pi }𝑑k𝑑k^{}\delta ^{(m)}(kk^{})\mathrm{\Phi }_0|\left(\widehat{U}_k^{}\right)^t\left(\widehat{U}_k^{}\right)^t|\mathrm{\Phi }_0.$$
(IV.9)
We can then integrate this by parts to obtain expressions such as

$`\widehat{x}^m_t`$ $`=`$ $`{\displaystyle \frac{(i)^m}{2\pi }}{\displaystyle 𝑑k𝑑k^{}\delta ^{(m)}(kk^{})\mathrm{\Phi }_0|\left(\widehat{U}_k^{}\right)^t\left(\widehat{U}_k^{}\right)^t|\mathrm{\Phi }_0}`$ (IV.10)
$`=`$ $`{\displaystyle \frac{(i)^m}{2\pi }}{\displaystyle 𝑑k𝑑k^{}\delta (kk^{})\mathrm{\Phi }_0|\left(\widehat{U}_k^{}\right)^t\left[\frac{d^m}{dk_{}^{}{}_{}{}^{m}}\left(\widehat{U}_k^{}\right)^t\right]|\mathrm{\Phi }_0}`$
$`=`$ $`{\displaystyle \frac{(i)^m}{2\pi }}{\displaystyle 𝑑k\mathrm{\Phi }_0|\left(\widehat{U}_k^{}\right)^t\left[\frac{d^m}{dk^m}\left(\widehat{U}_k\right)^t\right]|\mathrm{\Phi }_0}`$
For the first moment we get

$$\widehat{x}_t=\frac{i}{2\pi }𝑑k\mathrm{\Phi }_0|\left(\widehat{U}_k^{}\right)^t\left[\frac{d}{dk}\left(\widehat{U}_k\right)^t\right]|\mathrm{\Phi }_0,$$
(IV.11)
where

$`{\displaystyle \frac{d\widehat{U}_k}{dk}}`$ $`=`$ $`\left(i\mathrm{e}^{ik}\widehat{𝒫}_R+i\mathrm{e}^{ik}\widehat{𝒫}_L\right)\widehat{U}=i(\widehat{𝒫}_R\widehat{𝒫}_L)\widehat{U}_ki\widehat{Z}\widehat{U}_k`$
$`{\displaystyle \frac{d\widehat{U}_k^{}}{dk}}`$ $`=`$ $`i\widehat{U}_k^{}(\widehat{𝒫}_R\widehat{𝒫}_L)i\widehat{U}_k^{}\widehat{Z}`$
$`\widehat{Z}`$ $``$ $`\widehat{𝒫}_R\widehat{𝒫}_L=\widehat{I}2\widehat{𝒫}_L.`$ (IV.12)
Substituting this into (IV.11) gives us

$$\widehat{x}_t=\frac{1}{2\pi }\underset{j=1}{\overset{t}{}}𝑑k\mathrm{\Phi }_0|\left(\widehat{U}_k^{}\right)^j\widehat{Z}\left(\widehat{U}_k\right)^j|\mathrm{\Phi }_0.$$
(IV.13)
We can carry out a similar integration by parts to get the second moment:

$`\widehat{x}^2_t`$ $`=`$ $`{\displaystyle \frac{1}{2\pi }}{\displaystyle 𝑑k\mathrm{\Phi }_0|\left[\frac{d}{dk}\left(\widehat{U}_k^{}\right)^t\right]\left[\frac{d}{dk}\left(\widehat{U}_k\right)^t\right]|\mathrm{\Phi }_0}`$ (IV.14)
$`=`$ $`{\displaystyle \frac{1}{2\pi }}{\displaystyle \underset{j=1}{\overset{t}{}}}{\displaystyle \underset{j^{}=1}{\overset{t}{}}}{\displaystyle 𝑑k\mathrm{\Phi }_0|\left(\widehat{U}_k^{}\right)^j\widehat{Z}\left(\widehat{U}_k\right)^{jj^{}}\widehat{Z}\left(\widehat{U}_k\right)^j^{}|\mathrm{\Phi }_0}.`$
Can we now evaluate these expressions? Let us suppose that we can find the eigenvectors $`|\varphi _{kl}`$ and corresponding eigenvalues $`\mathrm{exp}(i\theta _{kl})`$ of $`\widehat{U}_k`$. We expand the initial state

$$|\mathrm{\Phi }_0=\underset{l}{}c_{kl}|\varphi _{kl}.$$
(IV.15)
After $`t`$ steps

$$\left(\widehat{U}_k\right)^t|\mathrm{\Phi }_0=\underset{l}{}c_{kl}|\varphi _{kl}\mathrm{e}^{i\theta _{kl}t}.$$
(IV.16)
Substituting this into the equation for the first moment (IV.13) we get

$$x_t=t+\frac{1}{\pi }𝑑k\underset{l,l^{}}{}c_{kl}^{}c_{kl^{}}\varphi _{kl}|\widehat{𝒫}_L|\varphi _{kl^{}}\underset{j=1}{\overset{t}{}}\mathrm{e}^{i(\theta _{kl^{}}\theta _{kl})j}.$$
(IV.17)
If the unitary matrix is nondegenerate, then most of the terms in (IV.17) will be oscillatory; hence, over time, they will average to zero. Only the diagonal terms in the above sum are nonoscillatory. We can therefore write

$`x_t`$ $`=`$ $`C_1t+\mathrm{oscillatory}\mathrm{terms},`$
$`C_1`$ $`=`$ $`1+{\displaystyle \frac{1}{\pi }}{\displaystyle 𝑑k\underset{l}{}|c_{kl}|^2\varphi _{kl}|\widehat{𝒫}_L|\varphi _{kl}}.`$ (IV.18)
Making the same substitutions in the equation for the second moment (IV.14), we get

$$x^2_t=\frac{1}{2\pi }𝑑k\underset{l,l^{},l^{\prime \prime }}{}c_{kl}^{}c_{kl^{}}\varphi _{kl}|\widehat{Z}|\varphi _{kl^{\prime \prime }}\varphi _{kl^{\prime \prime }}|\widehat{Z}|\varphi _{kl^{}}\underset{j,j^{}=1}{\overset{t}{}}\mathrm{e}^{i(\theta _{kl^{\prime \prime }}\theta _{kl})j}\mathrm{e}^{i(\theta _{kl^{}}\theta _{kl^{\prime \prime }})j^{}}.$$
(IV.19)
Once again, most of these terms are oscillatory. There are two sets of nonoscillatory terms: terms with $`l=l^{}=l^{\prime \prime }`$ (which give a quadratic dependence on $`t`$) and terms with $`j=j^{}`$ and $`l=l^{}`$ (which give a linear dependence). Therefore we can write the second moment as

$`x^2_t`$ $`=`$ $`C_2t^2+\mathrm{oscillatory}\mathrm{terms}+O(t),`$
$`C_2`$ $`=`$ $`1{\displaystyle \frac{2}{\pi }}{\displaystyle 𝑑k\underset{l}{}|c_{kl}|^2\varphi _{kl}|\widehat{𝒫}_L|\varphi _{kl}\varphi _{kl}|\widehat{𝒫}_R|\varphi _{kl}}.`$ (IV.20)
Of course, if the spectrum of $`\widehat{U}_k`$ is degenerate, we will have to modify (IV.20) and (IV.18) to include appropriate cross terms. This does not, however, alter the qualitative behavior. We see that generically in the long time limit, the first moment of the quantum random walk on the line will undergo a linear drift, and the variance will grow quadratically with time, so long as the coin is a finite-dimensional system.

### IV.2 The multicoin model

Now let us specialize to the case of our multicoin model. In this case our coin is a tensor-product of $`M`$ 2-level coins, with a Hilbert space of $`2^M`$ dimensions. The “flip operator” is

$$\widehat{U}=\left[\widehat{H}\widehat{I}^{M1}\right]\widehat{P},$$
(IV.21)
where $`\widehat{H}`$ is the usual Hadamard operator (II.1) and $`\widehat{P}`$ is a cyclic permutation of the $`M`$ coins:

$$\widehat{P}(|\psi _0|\psi _1\mathrm{}|\psi _{M1})=|\psi _1\mathrm{}|\psi _{M1}|\psi _0).$$
(IV.22)
The two projectors onto the flip results are

$`\widehat{𝒫}_R`$ $`=`$ $`|RR|\widehat{I}^{M1},`$
$`\widehat{𝒫}_L`$ $`=`$ $`|LL|\widehat{I}^{M1}.`$ (IV.23)
When we switch to the $`k`$ representation, these give us the effective unitary evolution

$$\widehat{U}_k=\left[\widehat{H}_k\widehat{I}^{M1}\right]\widehat{P},$$
(IV.24)
where $`\widehat{H}_k`$ is given by (II.9). In the case $`M=1`$, $`\widehat{U}_k=\widehat{H}_k`$.

The eigenvectors of $`\widehat{H}_k`$ are

$$|\pm =\frac{1}{\sqrt{2}}\left(1+\mathrm{cos}^2k\pm \mathrm{cos}k\sqrt{1+\mathrm{cos}^2k}\right)^{1/2}\left(\begin{array}{c}\mathrm{e}^{ik}\\ \sqrt{2}\mathrm{e}^{\pm i\omega _k}\mathrm{e}^{ik}\end{array}\right),$$
(IV.25)
with eigenvalues $`\mathrm{e}^{i(\pi +\omega _k)}`$, $`\mathrm{e}^{i\omega _k}`$, respectively, where we define $`\omega _k`$ to satisfy

$$\mathrm{sin}\omega _k\frac{1}{\sqrt{2}}\mathrm{sin}k,\pi /2<\omega _k<\pi /2.$$
(IV.26)
A basis for the full $`M`$-coin space is given by product vectors of $`|+`$ and $`|`$. (E.g., for $`M=2`$ the basis vectors would be $`|,|+,|+,|++`$.) Can we find the eigenvectors and eigenvalues of $`\widehat{U}_k`$ in terms of this basis?

Note first that if we apply $`\widehat{U}_k`$ to such a basis vector, we get another basis vector multiplied by a phase. Second, if we apply $`\widehat{U}_k`$ to a basis vector $`M`$ times, we get the same basis vector back, multiplied by a phase.

Two obvious eigenvectors appear at once: the vectors

$`|++\mathrm{}+`$ $``$ $`|+^M,`$
$`|\mathrm{}`$ $``$ $`|^M,`$ (IV.27)
are both eigenvectors of $`\widehat{U}_k`$ with eigenvalues $`\mathrm{e}^{i(\pi +\omega _k)}`$, $`\mathrm{e}^{i\omega _k}`$, respectively. Let us suppose for the moment that $`M`$ is a prime number. Then for all basis vectors $`|\varphi `$ other than those two, the vectors

$$\left(\widehat{U}_k\right)^j|\varphi ,0jM1$$
(IV.28)
are all distinct. Together they span an $`M`$-dimensional subspace which is preserved under the action of $`\widehat{U}_k`$. If $`|\varphi `$ contains exactly $`m`$ $`|`$s and $`(Mm)`$ $`|+`$s, then every vector in this subspace is an eigenvector of $`(\widehat{U}_k)^M`$ with eigenvalue $`\mathrm{exp}i((Mm)(\pi +\omega _k)m\omega _k)`$. This implies that the subspace is spanned by $`M`$ eigenvectors of $`\widehat{U}_k`$ with eigenvalues

$$\lambda _n=\mathrm{e}^{i(m\omega _k+(Mm)(\pi +\omega _k)+2\pi n)/M},0n<M.$$
(IV.29)
Let’s restrict ourselves to this $`M`$-dimensional subspace for the moment. Starting with our original basis state $`|\varphi `$, we label the basis states which span this space

$$|\varphi _j=\widehat{P}^j|\varphi .$$
(IV.30)
The eigenvectors of $`\widehat{U}_k`$ must have the form

$$|\chi _n=\frac{1}{\sqrt{M}}\underset{j=0}{\overset{M1}{}}e^{i\nu _{nj}}|\varphi _j.$$
(IV.31)
Plugging the above expression and equation (IV.29) into the equation

$$\widehat{U}_k|\chi _n=\lambda _n|\chi _n$$
(IV.32)
gives the result

$$\nu _{nj+1}=\nu _{nj}\left(m\omega _k(Mm)(\pi +\omega _k)2\pi n\right)/M+\theta _{j+1},$$
(IV.33)
where we define $`\theta _j`$ to be $`\mathrm{e}^{i\omega _k}`$ if the first factor of $`|\varphi _j`$ is $`|`$ and to be $`\mathrm{e}^{i(\pi +\omega _k)}`$ if the first factor is $`|+`$. Since the overall phase is arbitrary, we take $`\nu _0=0`$, which gives us

$$\nu _{nj}=\frac{j}{M}\left(m\omega _k(Mm)(\pi +\omega _k)+2\pi n\right)+\underset{j^{}=1}{\overset{j}{}}\theta _j^{}.$$
(IV.34)
For each value of $`m`$, $`1mM1`$, there are $`\frac{1}{M}\left(\genfrac{}{}{0pt}{}{M}{m}\right)`$ such $`M`$-dimensional subspaces which are preserved by the action of $`\widehat{U}_k`$; each eigenvalue is thus $`\frac{1}{M}\left(\genfrac{}{}{0pt}{}{M}{m}\right)`$-fold degenerate. However, this doesn’t complicate the expressions (IV.18) and (IV.20), because the cross-terms vanish:

$$\varphi _{kl}|\widehat{𝒫}_R|\varphi _{kl^{}}=\varphi _{kl}|\widehat{𝒫}_L|\varphi _{kl^{}}=0$$
(IV.35)
for all such degenerate eigenvectors $`|\varphi _{kl},|\varphi _{kl^{}}`$. Thus, we can use the expressions we’ve already derived.

Using the results in Eq. (IV.34) we can calculate the necessary matrix elements:

$`\chi _n|\widehat{𝒫}_L|\chi _n`$ $`=`$ $`{\displaystyle \frac{1}{M}}[m|LL|+(Mm)+|LL|+]`$
$`=`$ $`{\displaystyle \frac{1}{M}}[{\displaystyle \frac{m(\sqrt{1+\mathrm{cos}^2k}\mathrm{cos}k)^2}{2(1+\mathrm{cos}^2k\mathrm{cos}k\sqrt{1+\mathrm{cos}^2k})}}`$
$`+{\displaystyle \frac{(Mm)(\sqrt{1+\mathrm{cos}^2k}+\mathrm{cos}k)^2}{2(1+\mathrm{cos}^2k+\mathrm{cos}k\sqrt{1+\mathrm{cos}^2k})}}],`$
$`\chi _n|\widehat{𝒫}_R|\chi _n`$ $`=`$ $`{\displaystyle \frac{1}{M}}[m|RR|+(Mm)+|RR|+]`$ (IV.36)
$`=`$ $`{\displaystyle \frac{1}{M}}[{\displaystyle \frac{m}{2(1+\mathrm{cos}^2k\mathrm{cos}k\sqrt{1+\mathrm{cos}^2k})}}`$
$`+{\displaystyle \frac{Mm}{2(1+\mathrm{cos}^2k+\mathrm{cos}k\sqrt{1+\mathrm{cos}^2k})}}].`$
We also need the amplitudes of the coin’s initial state. If

$$|\mathrm{\Phi }_0=|\psi _0\mathrm{}|\psi _0=|\psi _0^M,$$
(IV.37)
then

$$|\mathrm{\Phi }_0|\chi _n|^2=|\psi _0||^{2m}|\psi _0|+|^{2(Mm)}\underset{j,j^{}}{}\frac{1}{M}\mathrm{e}^{i(\nu _{nj}\nu _{nj^{}})}.$$
(IV.38)
Note that

$$\underset{n=0}{\overset{M1}{}}\mathrm{e}^{i(\nu _{nj}\nu _{nj^{}})}=M\delta _{jj^{}}.$$
(IV.39)
We now have everything we need to get the moments!

To evaluate the expression (IV.18) to get $`C_1`$ we calculate

$`{\displaystyle \underset{l}{}}|c_{kl}|^2\varphi _{kl}|\widehat{𝒫}_L|\varphi _{kl}`$ $`=`$ $`{\displaystyle \underset{m=1}{\overset{M1}{}}}{\displaystyle \frac{1}{M}}\left({\displaystyle \genfrac{}{}{0pt}{}{M}{m}}\right){\displaystyle \underset{n=0}{\overset{M1}{}}}|\mathrm{\Phi }_0|\varphi _n|^2\varphi _n|\widehat{𝒫}_L|\varphi _n`$ (IV.40)
$`+|\psi _0||^2|LL|+|\psi _0|+|^2+|LL|+`$
$`=`$ $`{\displaystyle \underset{m=0}{\overset{M}{}}}\left({\displaystyle \genfrac{}{}{0pt}{}{M}{m}}\right)|\psi _0||^{2m}|\psi _0|+|^{2(Mm)}`$
$`\times {\displaystyle \frac{1}{M}}[{\displaystyle \frac{m(\sqrt{1+\mathrm{cos}^2k}\mathrm{cos}k)^2}{2(1+\mathrm{cos}^2k\mathrm{cos}k\sqrt{1+\mathrm{cos}^2k})}}`$
$`+{\displaystyle \frac{(Mm)(\sqrt{1+\mathrm{cos}^2k}+\mathrm{cos}k)^2}{2(1+\mathrm{cos}^2k+\mathrm{cos}k\sqrt{1+\mathrm{cos}^2k})}}].`$
We can simplify this considerably by noting that this equation (IV.40) has the form

$$\underset{m=0}{\overset{M}{}}\left(\genfrac{}{}{0pt}{}{M}{m}\right)p^m(1p)^{Mm}[(m/M)(AB)+B]=pA+(1p)B,$$
(IV.41)
where

$`p`$ $`=`$ $`|\psi _0||^2,`$
$`A`$ $`=`$ $`{\displaystyle \frac{(\sqrt{1+\mathrm{cos}^2k}\mathrm{cos}k)^2}{2(1+\mathrm{cos}^2k\mathrm{cos}k\sqrt{1+\mathrm{cos}^2k})}},`$
$`B`$ $`=`$ $`{\displaystyle \frac{(\sqrt{1+\mathrm{cos}^2k}+\mathrm{cos}k)^2}{2(1+\mathrm{cos}^2k+\mathrm{cos}k\sqrt{1+\mathrm{cos}^2k})}},`$ (IV.42)
and we’ve invoked some combinatorial identities

$`{\displaystyle \underset{m=0}{\overset{M}{}}}\left({\displaystyle \genfrac{}{}{0pt}{}{M}{m}}\right)p^m(1p)^{Mm}`$ $`=`$ $`\left(p+(1p)\right)^M=1,`$
$`{\displaystyle \underset{m=0}{\overset{M}{}}}\left({\displaystyle \genfrac{}{}{0pt}{}{M}{m}}\right)p^m(1p)^{Mm}(m/M)`$ $`=`$ $`p{\displaystyle \underset{m=0}{\overset{M1}{}}}\left({\displaystyle \genfrac{}{}{0pt}{}{M1}{m}}\right)p^m(1p)^{Mm1}=p.`$ (IV.43)
This leaves us with the simple expression

$`{\displaystyle \underset{l}{}}|c_{kl}|^2\varphi _{kl}|\widehat{𝒫}_L|\varphi _{kl}`$ $`=`$ $`[{\displaystyle \frac{|\psi _0||^2(\sqrt{1+\mathrm{cos}^2k}\mathrm{cos}k)^2}{2(1+\mathrm{cos}^2k\mathrm{cos}k\sqrt{1+\mathrm{cos}^2k})}}`$ (IV.44)
$`+{\displaystyle \frac{|\psi _0|+|^2(\sqrt{1+\mathrm{cos}^2k}+\mathrm{cos}k)^2}{2(1+\mathrm{cos}^2k+\mathrm{cos}k\sqrt{1+\mathrm{cos}^2k})}}],`$
in which all $`M`$ dependence is gone!

Let us choose the initial condition $`|\psi _0=|R`$. Then

$`|\psi _0||^2`$ $`=`$ $`{\displaystyle \frac{1}{2(1+\mathrm{cos}^2k\mathrm{cos}k\sqrt{1+\mathrm{cos}^2k})}}`$
$`|\psi _0|+|^2`$ $`=`$ $`{\displaystyle \frac{1}{2(1+\mathrm{cos}^2k+\mathrm{cos}k\sqrt{1+\mathrm{cos}^2k})}}.`$ (IV.45)
We can plug this into the above equation (IV.44); after a bit of algebra, this boils down to the result

$$\underset{l}{}|c_{kl}|^2\varphi _{kl}|\widehat{𝒫}_L|\varphi _{kl}=\frac{1}{2(1+\mathrm{cos}^2k)},$$
(IV.46)
This gives us the final equation for $`C_1`$,

$$C_1=1+\frac{1}{2\pi }\frac{dk}{1+\mathrm{cos}^2k}=1+1/\sqrt{2},$$
(IV.47)
which exactly matches the observed numerical results. (See figure 4.)

We can do a similar derivation for the second moment, in order to get $`C_2`$. For this we use

$`{\displaystyle \underset{l}{}}|c_{kl}|^2\varphi _{kl}|\widehat{𝒫}_L|\varphi _{kl}\varphi _{kl}|\widehat{𝒫}_R|\varphi _{kl}`$
$`={\displaystyle \underset{m=0}{\overset{M}{}}}\left({\displaystyle \genfrac{}{}{0pt}{}{M}{m}}\right)|\psi _0||^{2m}|\psi _0|+|^{2(Mm)}`$
$`\times {\displaystyle \frac{1}{M}}[{\displaystyle \frac{m(\sqrt{1+\mathrm{cos}^2k}\mathrm{cos}k)^2}{2(1+\mathrm{cos}^2k\mathrm{cos}k\sqrt{1+\mathrm{cos}^2k})}}`$
$`+{\displaystyle \frac{(Mm)(\sqrt{1+\mathrm{cos}^2k}+\mathrm{cos}k)^2}{2(1+\mathrm{cos}^2k+\mathrm{cos}k\sqrt{1+\mathrm{cos}^2k})}}]`$
$`\times {\displaystyle \frac{1}{M}}[{\displaystyle \frac{m}{2(1+\mathrm{cos}^2k\mathrm{cos}k\sqrt{1+\mathrm{cos}^2k})}}`$
$`+{\displaystyle \frac{(Mm)}{2(1+\mathrm{cos}^2k+\mathrm{cos}k\sqrt{1+\mathrm{cos}^2k})}}].`$ (IV.48)
We can again simplify by observing that (IV.48) has the form

$`{\displaystyle \underset{m=0}{\overset{M}{}}}\left({\displaystyle \genfrac{}{}{0pt}{}{M}{m}}\right)p^m(1p)^{Mm}[(m/M)(AB)+B][A+(m/M)(BA)]`$
$`=AB+p(1p){\displaystyle \frac{M1}{M}}(AB)^2.`$ (IV.49)
If we specialize once more to $`|\psi _0=|0`$, we can make similar algebraic simplifications to get

$`C_2`$ $`=`$ $`1{\displaystyle \frac{1}{2\pi }}{\displaystyle 𝑑k\left[\frac{1+2\mathrm{cos}^2k}{(1+\mathrm{cos}^2k)^2}\frac{1}{M}\frac{\mathrm{cos}^2k}{(1+\mathrm{cos}^2k)^2}\right]}`$ (IV.50)
$`=`$ $`1{\displaystyle \frac{5}{4\sqrt{2}}}+{\displaystyle \frac{1}{M}}{\displaystyle \frac{1}{4\sqrt{2}}}.`$
Of course, numerically we calculated not the second moment but the variance of $`x`$. Given our results,

$$\widehat{x}^2_t\widehat{x}_{t}^{}{}_{}{}^{2}=(C_2C_1^2)t^2+O(t)+\mathrm{osc}.\mathrm{terms},$$
(IV.51)
we get the result

$$C_2C_1^2=\frac{32\sqrt{2}+1/M}{4\sqrt{2}}.$$
(IV.52)
Note that this doesn’t vanish as $`M`$ becomes large!

The derivation used above was only strictly valid for prime $`M`$. However, it turns out that the additional complications arising from composite $`M`$ all cancel out, yielding the same expressions for $`C_1`$ and $`C_2`$. Upon comparison to the numerical results, we see that these analytical expressions for the first moment and the variance match the simulations extremely well. (See figure 5.)

### IV.3 Constant flips per coin

We see that in the long time limit, an $`M`$-coin quantum random walk with fixed $`M`$ has qualitative behavior similar to that one of the one-coin walk, and is markedly nonclassical. A reasonable question to ask is, how long is a long time? Suppose we flip each coin at most $`d`$ times, and add more coins as we go to long times, so that $`M`$ and $`t`$ are both growing in a fixed ratio $`t/Md`$. Does this still behave nonclassically? The fact that $`C_2C_1^2`$ does not vanish as $`M\mathrm{}`$ makes this conjecture plausible. If so, how big must $`d`$ be for this nonclassical behavior to manifest itself?

Let us now consider a quantum random walk on a line driven by a sequence of two-level coins, each flipped $`d`$ times. By the reordering principle described in section III, this is the same as having a single coin which is measured and reset to the initial state $`|\mathrm{\Phi }_0`$ after every $`d`$ steps. We describe this evolution by a superoperator $``$ which acts on the density matrix of the particle and coin:

$`\rho \rho ^{}`$ $`=`$ $`\rho `$ (IV.53)
$`=`$ $`{\displaystyle \underset{n}{}}\widehat{A}_n\left(\widehat{E}\right)^d\rho \left(\widehat{E}^{}\right)^d\widehat{A}_n^{},`$
where $`\widehat{E}`$ is the usual unitary evolution (II.3), and

$`\widehat{A}_0`$ $`=`$ $`\widehat{I}|\mathrm{\Phi }_0R|,`$
$`\widehat{A}_1`$ $`=`$ $`\widehat{I}|\mathrm{\Phi }_0L|.`$ (IV.54)
The superoperator $``$ represents $`d`$ steps of the walk. Note that

$$\rho =\mathrm{Tr}_{\mathrm{coin}}\left\{\left(\widehat{E}\right)^d\rho \left(\widehat{E}^{}\right)^d\right\}|\mathrm{\Phi }_0\mathrm{\Phi }_0|.$$
(IV.55)
We rewrite this in terms of the eigenvectors $`|k`$ of $`\widehat{S},\widehat{S}^{}`$. In the $`k`$ basis, a general density operator for the joint particle/coin system is written

$$\rho =\frac{dk}{2\pi }\frac{dk^{}}{2\pi }|kk^{}|\chi _{kk^{}},$$
(IV.56)
and the evolution superoperator becomes

$`\rho `$ $`=`$ $`{\displaystyle \frac{dk}{2\pi }\frac{dk^{}}{2\pi }|kk^{}|\underset{n=R,L}{}|\mathrm{\Phi }_0n|\left(\widehat{H}_k\chi _{kk^{}}\widehat{H}_k^{}^{}\right)|n\mathrm{\Phi }_0|}`$ (IV.57)
$``$ $`{\displaystyle \frac{dk}{2\pi }\frac{dk^{}}{2\pi }|kk^{}|_{kk^{}}\chi _{kk^{}}},`$
where $`_{kk^{}}`$ is now a superoperator on the coin degree of freedom alone.

The initial state of the system (particle and coin) is

$`\rho _0`$ $`=`$ $`|\mathrm{\Psi }_0\mathrm{\Psi }_0|=|00||\mathrm{\Phi }_0\mathrm{\Phi }_0|`$ (IV.58)
$`=`$ $`{\displaystyle \frac{dk}{2\pi }\frac{dk^{}}{2\pi }|kk^{}||\mathrm{\Phi }_0\mathrm{\Phi }_0|}.`$
Let the quantum random walk proceed for $`t`$ steps. Then the state evolves to

$$\rho _t=\frac{dk}{2\pi }\frac{dk^{}}{2\pi }|kk^{}|_{kk^{}}^{t/d}|\mathrm{\Phi }_0\mathrm{\Phi }_0|.$$
(IV.59)
The probability to reach a point $`x`$ at time $`t`$ is

$`p(x,t)`$ $`=`$ $`\mathrm{Tr}\left\{(|xx|\widehat{I})\rho _t\right\}`$ (IV.60)
$`=`$ $`{\displaystyle \frac{1}{(2\pi )^2}}{\displaystyle 𝑑k𝑑k^{}k|xx|k^{}\mathrm{Tr}\left\{_{kk^{}}^{t/d}|\mathrm{\Phi }_0\mathrm{\Phi }_0|\right\}}`$
$`=`$ $`{\displaystyle \frac{1}{(2\pi )^2}}{\displaystyle 𝑑k𝑑k^{}\mathrm{e}^{ix(kk^{})}\mathrm{Tr}\left\{_{kk^{}}^{t/d}|\mathrm{\Phi }_0\mathrm{\Phi }_0|\right\}}.`$
We are interested in the moments of this distribution.

$`\widehat{x}^m_t`$ $`=`$ $`{\displaystyle \underset{x}{}}x^mp(x,t)`$ (IV.61)
$`=`$ $`{\displaystyle \frac{1}{(2\pi )^2}}{\displaystyle \underset{x}{}}x^m{\displaystyle 𝑑k𝑑k^{}\mathrm{e}^{ix(kk^{})}\mathrm{Tr}\left\{_{kk^{}}^{t/d}|\mathrm{\Phi }_0\mathrm{\Phi }_0|\right\}}.`$
Just as before, we invert the order of operations and do the $`x`$ sum first, which yields

$$\widehat{x}^m_t=\frac{(i)^m}{2\pi }𝑑k𝑑k^{}\delta ^{(m)}(kk^{})\mathrm{Tr}\left\{_{kk^{}}^{t/d}|\mathrm{\Phi }_0\mathrm{\Phi }_0|\right\}.$$
(IV.62)
We can then integrate this by parts. In carrying out this integration by parts, we will need

$`{\displaystyle \frac{d}{dk}}_{kk^{}}\rho `$ $`=`$ $`i{\displaystyle \underset{n}{}}\widehat{A}_n\left({\displaystyle \underset{j=0}{\overset{d1}{}}}(\widehat{H}_k)^j\widehat{Z}(\widehat{H}_k^{})^j\right)(\widehat{H}_k)^d\rho (\widehat{H}_k^{})^d\widehat{A}_n^{}`$ (IV.63)
$`=`$ $`i|\mathrm{\Phi }_0\mathrm{\Phi }_0|\mathrm{Tr}\left\{\left({\displaystyle \underset{j=0}{\overset{d1}{}}}(\widehat{H}_k)^j\widehat{Z}(\widehat{H}_k^{})^j\right)(\widehat{H}_k)^d\rho (\widehat{H}_k^{})^d\right\},`$
where $`\widehat{H}_k`$ is given by (II.9) and $`\widehat{Z}`$ by (IV.12).

Using this, we can carry out the integration by parts for the first moment to get

$`\widehat{x}_t`$ $`=`$ $`{\displaystyle \frac{1}{2\pi }}{\displaystyle \underset{j=0}{\overset{t/d1}{}}}{\displaystyle 𝑑k\mathrm{Tr}\left\{\widehat{Z}_{kd}_{kk}^j|\mathrm{\Phi }_0\mathrm{\Phi }_0|\right\}}`$ (IV.64)
$`=`$ $`{\displaystyle \frac{1}{2\pi }}{\displaystyle \underset{j=0}{\overset{t/d1}{}}}{\displaystyle 𝑑k\mathrm{Tr}\left\{\widehat{Z}_{kd}|\mathrm{\Phi }_0\mathrm{\Phi }_0|\right\}}`$
$`=`$ $`{\displaystyle \frac{t}{d}}{\displaystyle \frac{dk}{2\pi }\mathrm{\Phi }_0|\widehat{Z}_{kd}|\mathrm{\Phi }_0},`$
where we define

$$\widehat{Z}_{kd}=\underset{l=1}{\overset{d}{}}(\widehat{H}_k^{})^l\widehat{Z}(\widehat{H}_k)^l.$$
(IV.65)
Generically, then, we see from (IV.64) that the first moment of position grows linearly with time provided $`\mathrm{\Phi }_0|\widehat{Z}_{kd}|\mathrm{\Phi }_0`$ is nonzero.

We can carry out a similar integration by parts to get the second moment:

$`\widehat{x}^2_t`$ $`=`$ $`{\displaystyle \frac{1}{2\pi }}{\displaystyle }dk\left[{\displaystyle \underset{j=0}{\overset{t/d1}{}}}\mathrm{Tr}\{\left(\widehat{Z}_{kd}\right)^2_{kk}^j|\mathrm{\Phi }_0\mathrm{\Phi }_0|)\right\}`$ (IV.66)
$`+{\displaystyle \underset{j=0}{\overset{t/d1}{}}}{\displaystyle \underset{j^{}=0}{\overset{j1}{}}}\mathrm{Tr}\left\{\widehat{Z}_{kd}_{kk}^{jj^{}}((_k^j^{}|\mathrm{\Phi }_0\mathrm{\Phi }_0|)\widehat{Z}_{kd}+\widehat{Z}_{kd}_{kk}^j^{}|\mathrm{\Phi }_0\mathrm{\Phi }_0|)\right\}]`$
$`=`$ $`{\displaystyle \frac{1}{2\pi }}{\displaystyle }dk[(t/d)\mathrm{\Phi }_0|\left(\widehat{Z}_{kd}\right)^2|\mathrm{\Phi }_0+(t^2/d^2t/d)\mathrm{\Phi }_0|\widehat{Z}_{kd}|\mathrm{\Phi }_0^2.`$
So here we expect the second moment to grow quadratically with time, qualitatively like the single-coin walk.

Let’s choose the initial condition $`|\mathrm{\Phi }_0=|R`$, and look at a few values of $`d`$. We are interested in the coefficients $`C_1`$ and $`C_2`$, where

$`\widehat{x}_t`$ $`=`$ $`C_1t,`$
$`\widehat{x}^2_t`$ $`=`$ $`C_2t^2+O(t).`$ (IV.67)
From the equations (IV.64), (IV.66), we get

$`C_1`$ $`=`$ $`{\displaystyle \frac{1}{d}}{\displaystyle \frac{dk}{2\pi }R|\widehat{Z}_{kd}|R},`$
$`C_2`$ $`=`$ $`{\displaystyle \frac{1}{d^2}}{\displaystyle \frac{dk}{2\pi }R|\widehat{Z}_{kd}|R^2}.`$ (IV.68)
From the definitions of $`\widehat{Z}_{kd}`$ and $`\widehat{H}_k`$ we can work out the values of $`C_{1,2}`$ in specific cases.

For $`d=1`$, the matrix element $`R|\widehat{Z}_{k1}|R=0`$, so both $`C_1`$ and $`C_2`$ vanish. We recover the classical case.

For $`d=2`$, the matrix element $`R|\widehat{Z}_{k2}|R=\mathrm{cos}2k`$, so $`C_1`$ vanishes in this case as well. However, $`C_2=1/80`$. So even with only two flips per coin, the variance already grows quadratically with time.

For $`d=3`$, the matrix element $`R|\widehat{Z}_{k3}|R=\mathrm{cos}2k+\mathrm{sin}^22k`$, so both $`C_1`$ and $`C_2`$ are nonzero. In this case, $`C_1=1/6`$ and $`C_2=7/72`$.

If we let both $`d`$ and $`t/d`$ become large, then we can evaluate (IV.64) and (IV.66) to get $`C_11+\sqrt{1/2}`$ and $`C_215/\sqrt{32}`$, which are in agreement with our earlier results for large $`M`$ in the multicoin case.

## V Conclusions

We have examined one possible path from quantum to classical behavior: the use of multiple coins (or, more generally, higher-dimensional systems) to drive the walk and reduce the effects of interference. We have seen that quantum behavior, as typified by quadratic growth of the variance with time, persists except in the extreme limit of a new coin for every step. Furthermore, quadratic growth of the variance seems to be a generic feature of such unitary walks.

From the multicoin example we might speculate that classical behavior is only recovered in the limit where the coin system retains enough information about the walk to reconstruct a unique classical path for the particle. Since there are $`2^t`$ such paths up to time $`t`$, the coin must have a Hilbert space dimension which grows exponentially in time in order to exhibit classical behavior.

Another plausible route to classical behavior adds decoherence to the coin, which also effectively suppresses interference effects. The results of this study are presented elsewhere Brun et al. (2002a).

###### Acknowledgements.

We would like to thank Bob Griffiths, Lane Hughston, Viv Kendon, Michele Mosca, and Bruce Richmond for useful conversations. TAB acknowledges financial support from the Martin A. and Helen Chooljian Membership in Natural Sciences, and DOE Grant No. DE-FG02-90ER40542. AA was supported by NSF grant CCR-9987845, and by the State of New Jersey. HAC was supported by MITACS, the Fields Institute, and the NSERC CRO project “Quantum Information and Algorithms.”

## Appendix A Combinatorial derivation of one-coin walk

Assume that the coin starts at $`x=0`$. After $`t`$ coin flips, the particle might have reached locations anywhere between $`x=t,t+2,\mathrm{},t2,t.`$ The number of paths that finish at a point $`x`$ after $`t`$ steps is

$$\mathrm{\#}\text{paths}=\left(\genfrac{}{}{0pt}{}{t}{(tx)/2}\right).$$
(A.1)
Paths ending with the coin in state $`|L`$ cannot interfere with paths ending with the coin in state $`|R.`$

A given path can be written as a sequence $`S`$ of $`t`$ symbols, $`L`$ or $`R`$ like this one:

$$LRRLR\underset{\begin{array}{c}\text{a cluster}\\ \text{of}\mathrm{\hspace{0.33em}3}Ls\end{array}}{\underset{}{LLL}}RR\mathrm{}$$
(A.2)
We let $`N_L(S)`$ be the number of $`L`$’s in $`S`$ and $`N_R(S)`$ the number of $`R`$’s. Then

$`N_L(S)+N_R(S)=t,`$ $`N_R(S)N_L(S)=x,`$ (A.3)
so we can write

$`N_R(S)=(t+x)/2,`$ $`N_L(S)=(tx)/2.`$ (A.4)
Each path has an associated phase factor, which can take the values $`\pm 1.`$ A factor of $`1`$ is acquired whenever the coin flips two successive lefts, so a pair $`LL`$ contributes a phase factor of $`1,`$ the sequence $`LLL`$ produces a factor of $`+1,`$ and $`LLLL`$ results in a $`1,`$ and so on. Each cluster of $`m`$ $`L`$s contributes a factor of $`(1)^{m1}`$ to the phase for that path.

Let $`C(S)`$ be the number of $`L`$-clusters in $`S.`$ (An $`L`$-cluster must contain at least one $`L.`$) Swapping an $`L`$ from one cluster to another changes the phase contributed by each cluster by $`1,`$ thus having no overall effect on the phase of the path as a whole. Therefore, only the number of $`L`$-clusters and the total number of $`L`$s matters.

If the number of $`L`$-clusters is $`C`$ and the total number of $`L`$s is $`N_L,`$ then these could be arranged thus

$$\underset{C1\text{singletons}}{\underset{}{LLL\mathrm{}L}}\underset{\begin{array}{c}N_L(C1)\\ \text{consecutively}\end{array}}{\underset{}{LL\mathrm{}L}}.$$
(A.5)
This path will have a phase of

$$\phi (S)=(1)^{N_L(C1)1}=(1)^{N_LC}.$$
(A.6)
So when $`N_LC`$ is odd the overall phase is $`1.`$

Each cluster must have at least one $`R`$ between itself and the next cluster. Call these groups of $`R`$s “partitions.” Every sequence $`S`$ is then a succession of alternating clusters and partitions. Let

$$P(S)=\mathrm{\#}\text{of partitions in}S.$$
(A.7)
Clearly $`C(S)`$ cannot be higher than $`N_L(S),`$ and $`P(S)`$ cannot be higher than $`N_R(S).`$ Also, it must be the case that

$$P(S)=C(S)\text{or}C(S)\pm 1.$$
(A.8)
Allocating $`N_L`$ $`L`$s among $`C`$ clusters can be done in $`\left(\genfrac{}{}{0pt}{}{N_L1}{C1}\right)`$ ways; similarly, $`N_R`$ $`R`$s can be allocated among $`P`$ partitions in $`\left(\genfrac{}{}{0pt}{}{N_R1}{P1}\right)`$ ways. For a given $`C`$ and $`P`$, then, the total number of paths must be

$$\mathrm{\#}\text{paths}=\left(\genfrac{}{}{0pt}{}{N_L1}{C1}\right)\left(\genfrac{}{}{0pt}{}{N_R1}{P1}\right).$$
(A.9)
Let us now fix $`t`$ and $`x,`$ and hence also $`N_L`$ and $`N_R.`$ What values of $`C`$ and $`P`$ are possible, and how many paths have each value?

Case I: $`x>0N_R>N_L.`$ The number of clusters, $`C,`$ can range from $`0`$ (only when $`x=t`$) to $`N_L.`$ The number of partitions $`P`$ can be $`C,C+1`$ or $`C1,`$ except when $`C=0,1.`$

Case II: $`x<0N_L>N_R.`$ This time $`C`$ can range from $`1`$ to $`N_R+1.`$ Likewise, $`P`$ can take values of $`C,C+1,C1`$ except at the extremes.

Case III: $`x=0N_L=N_R`$ and $`C`$ and $`P`$ can be anything from $`1`$ to $`N_L=N_R.`$

Consider now the arrangements of clusters and partitions. There are four distinct possible arrangements.

Arrangement 1: $`P=C1.`$

$$\left[\text{cluster}\right]\text{partition}\left[\text{cluster}\right]\text{partition}\mathrm{}\left[\text{cluster}\right].$$
(A.10)
Arrangement 2: $`P=C`$, starting with a partition. This looks like

$$\text{partition}\left[\text{cluster}\right]\text{partition}\mathrm{}\left[\text{cluster}\right].$$
(A.11)
Arrangement 3: $`P=C,`$ starting with a cluster.

$$\left[\text{cluster}\right]\text{partition}\left[\text{cluster}\right]\mathrm{}\text{partition}.$$
(A.12)
Arrangement 4: $`P=C+1.`$

$$\text{partition}\left[\text{cluster}\right]\text{partition}\left[\text{cluster}\right]\mathrm{}\text{partition}.$$
(A.13)
We adopt the convention

$$\left(\genfrac{}{}{0pt}{}{a}{b}\right)=0,\text{if}b>a,b<0,\text{or}a<0.$$
(A.14)
Then we can write that the amplitude to reach $`x`$ after $`t`$ coin flips, ending in an $`L`$ is:

$$a_L(x,t)=\frac{1}{\sqrt{2^t}}\left[\underset{C=1}{\overset{\mathrm{`}\mathrm{`}N\mathrm{"}}{}}(1)^{N_LC}\left(\genfrac{}{}{0pt}{}{N_L1}{C1}\right)\left\{\left(\genfrac{}{}{0pt}{}{N_R1}{C2}\right)+\left(\genfrac{}{}{0pt}{}{N_R1}{C1}\right)\right\}\right],$$
(A.15)
where the summation is to $`N_L`$ for $`x0`$ and to $`N_R+1`$ for $`x<0.`$

Likewise, the amplitude to reach $`x`$ in $`t`$ flips, ending in an $`R`$ is

$$a_R(x,t)=\frac{1}{\sqrt{2^t}}\left[\underset{C=1}{\overset{\mathrm{`}\mathrm{`}N\mathrm{"}}{}}(1)^{N_LC}\left(\genfrac{}{}{0pt}{}{N_L1}{C1}\right)\left\{\left(\genfrac{}{}{0pt}{}{N_R1}{C1}\right)+\left(\genfrac{}{}{0pt}{}{N_R1}{C}\right)\right\}\right],$$
(A.16)
but only if $`N_L0`$; that case (which corresponds to $`t=x`$) always has amplitude $`2^{t/2}`$.

We can use the binomial relations

$`\left({\displaystyle \genfrac{}{}{0pt}{}{N_R1}{C2}}\right)+\left({\displaystyle \genfrac{}{}{0pt}{}{N_R1}{C1}}\right)`$ $`=\left({\displaystyle \genfrac{}{}{0pt}{}{N_R}{C1}}\right)`$
$`\left({\displaystyle \genfrac{}{}{0pt}{}{N_R1}{C1}}\right)+\left({\displaystyle \genfrac{}{}{0pt}{}{N_R1}{C}}\right)`$ $`=\left({\displaystyle \genfrac{}{}{0pt}{}{N_R}{C}}\right),`$ (A.17)
to simplify these somewhat to give the final equations (II.2).

If we had started instead with the coin in the state $`|L`$, all sequences which begin with an $`L`$ (i.e., arrangements 1 and 3) would pick up an extra minus sign. The amplitudes then become those given by the equations (II.2).

## Appendix B Asymptotic approximation to the Fourier integrals

Following the analysis in Nayak and Vishwanath (2000), the Fourier analysis of the many coin quantum walk can be completed in the same way. We represent the state of the particle in the $`\{|k\}`$ basis, and make use of the eigenvectors and eigenvalues of $`\widehat{H}_k`$, as given by (IV.25) and (IV.26). We will also use the identity

$$\pm \sqrt{2}e^{i\omega _k}e^{ik}=\pm \sqrt{1+\mathrm{cos}^2(k)}\mathrm{cos}(k)$$
(B.1)
We can now use the tensor-product structure of the evolution matrix and the integral simplifications in Nayak and Vishwanath (2000) to simplify the integrals for $`a_R`$ and $`a_L.`$ The expression for $`a_R`$ becomes

$$_\pi ^\pi \left(1\frac{\mathrm{cos}(k)}{\sqrt{1+\mathrm{cos}^2(k)}}\right)e^{i((\omega _k+\pi )tkx)}𝑑k=(1)^{x+t}_\pi ^\pi \left(1+\frac{\mathrm{cos}(k^{})}{\sqrt{1+\mathrm{cos}^2(k^{})}}\right)e^{i(\omega _k^{}t+k^{}x)}𝑑k^{}$$
(B.2)
where $`k^{}=k\pi ,\omega _k^{}=\omega _k`$ and we are free to move the limits of integration because the integral is over a whole period of the function. The two terms in the integral for $`a_L`$ can be simplified in a similar way:

$$\begin{array}{c}_\pi ^\pi \frac{e^{ik}(\sqrt{1+\mathrm{cos}^2(k)}+\mathrm{cos}(k))}{((1+\mathrm{cos}^2(k))+\mathrm{cos}(k)\sqrt{1+\mathrm{cos}^2(k)})}e^{i(\omega _k+\pi )tkx}𝑑k\hfill \\ \hfill =(1)^{x+t}_\pi ^\pi \frac{e^{ik^{}}}{2\sqrt{1+\mathrm{cos}^2(k^{})}}e^{i(\omega _k^{}t+k^{}x)}𝑑k^{}.\end{array}$$
(B.3)
Before we can write down a closed form for the $`M`$-coin momentum wave-function, we need one more construction. This is a timelike parameter that we’ll call $`|\tau |`$. Let $`t_i`$ be the total number of turns that coin $`i`$ has. The tensor product structure of the evolution matrix for the multicoin system means that the eigenvalues for the combined system are just products of the eigenvalues for the one coin system. So we’ll see things like

$`\lambda _𝐤^t`$ $`=e^{i\omega _kt_1}e^{i(\omega _k+\pi )t_2}e^{i\omega _kt_3}e^{i(\omega _k+\pi )t_4}e^{i(\omega _k+\pi )t_5}\mathrm{}`$ (B.4)
$`=(1)^{t_2+t_4+t_5}e^{i\omega _k(t_1t_2+t_3t_4t_5\mathrm{})}.`$ (B.5)
If we now write

$$(t_1t_2+t_3t_4t_5\mathrm{})=\mathrm{`}\mathrm{`}\tau \mathrm{"}$$
(B.6)
we can see that, up to a minus sign, we will obtain expressions of much the same form as in the one coin case, but parametrized by $`\tau `$ instead of $`t,`$ where $`\tau `$ is defined

$$\tau \{\pm t_1\pm t_2\pm \mathrm{}\pm t_M\},$$
(B.7)
with each $`\pm `$ independent. The modulus sign arises naturally when the integral expressions for the wavefunction are simplified in a way analogous to the one coin case, as $`\tau `$ can be chosen to be positive without loss of generality. When performing the simplification, it is also convenient to introduce the integer $`j_\tau ,`$ which is useful because for each $`\tau `$ we get terms like

$$\left(1+\frac{\mathrm{cos}^2(k)}{\sqrt{1+\mathrm{cos}^2(k)}}\right)^{\mathrm{\#}(t_is\text{ ending in }L)}\left(1\frac{\mathrm{cos}^2(k)}{\sqrt{1+\mathrm{cos}^2(k)}}\right)^{\mathrm{\#}(t_is\text{ ending in }L)}$$
(B.8)
These are of the form $`(a+b)^r(ab)^s,`$ and $`j_\tau `$ counts the $`(a^2b^2)^{|rs|}`$ terms in the expansion of that product. These are of the form $`(\frac{1}{1+\mathrm{cos}^2(k)})^{|rs|}`$ and so they only appear in the denominator. The term raised to the power of $`n2j_\tau `$ is just the two sets of left-overs from that (one multiplied by $`e^{i(\omega _k|\tau |+kx)}`$ and the other by $`e^{i((\omega _k+\pi )|\tau |kx)})`$ which have then been combined using the integral simplification identities as before.

We can now write down the wavefunction for a particle that started out with all the coins in the state $`|R`$ and ended in them in (any) one of the $`\left(\genfrac{}{}{0pt}{}{M}{n}\right)`$ components with $`n`$ coins in the state $`R:`$

$$\begin{array}{c}|\psi _{n,(Mn)}(x,t)=\hfill \\ \hfill \underset{\tau }{}\frac{1+(1)^{x+|\tau |}}{2^M}_\pi ^\pi \frac{dk}{2\pi }\left(\frac{e^{ik(Mn)}\left(\mathrm{cos}(k)+\sqrt{1+\mathrm{cos}^2(k)}\right)^{n2j_\tau }}{(1+\mathrm{cos}^2(k))^{M/2}}\right)e^{i(\omega _k|\tau |+kx)},\end{array}$$
(B.9)
where the sum over $`\tau `$ indicates a sum over all $`2^M`$ possible signs in (B.7).

To write down the wavefunction for a particle that started with its coins in any state in the computational basis for the coins, we need yet another definition. We will introduce the notation $`\sigma `$ to be the $`L`$-sign weight of $`\tau ,`$ which will be the number of minuses in that particular $`\tau .`$ So for

$`\tau `$ $`=t_1+t_2t_3+t_4t_5t_6+t_7,`$
initial coin state $`=RLRLLLR,`$ (B.10)
we define $`\sigma =2.`$ In other words, for all the coins that started out in the state $`L,`$ count the number of minuses in front of the number of turns taken by those coins for that $`\tau .`$ Ignore any minuses for coins that start in the state $`R.`$ Without loss of generality, $`\sigma `$ can be taken to be in $`[0,M/2],`$ as only $`|\tau |`$ actually matters in the wavefunction.

Then the wavefunction for a walk starting with its $`M`$ coins in a state in the computational basis of the coins, where there are initially $`q`$ coins in the state $`L`$ and $`Mq`$ in the state $`R`$ will be

$$\begin{array}{c}|\psi _{n,(Mn):\mathrm{coins}}(x,t)=\underset{\tau }{}\frac{1+(1)^{x+|\tau |}}{2^M}\hfill \\ \hfill \times _\pi ^\pi \frac{dk}{2\pi }e^{i\sigma \pi }(\sqrt{1+\mathrm{cos}^2(k)}\mathrm{cos}(k))^{Mq\sigma }(\sqrt{1+\mathrm{cos}^2(k)}+\mathrm{cos}(k))^\sigma \\ \hfill \times \left(\frac{e^{ikn}\left(\mathrm{cos}(k)+\sqrt{1+\mathrm{cos}^2(k)}\right)^{n2j_\tau }e^{ikq}}{(1+\mathrm{cos}^2(k))^{M/2}}\right)e^{i(\omega _k|\tau |+kx)}.\end{array}$$
(B.11)
The wavefunction for a general starting state can be obtained from those for the computational basis states by forming the corresponding linear combination.

If $`\tau `$ is an asymptotic parameter: i.e., $`\tau \mathrm{}`$ as $`t\mathrm{}`$ then these integrals may be approximated using the method of stationary phase. If $`\tau =0`$ or $`\tau =`$ constant (which can happen if the coins are used cyclically: for example if we have two coins, then we will get terms where $`t_1t_2=0`$ or $`1`$ for all time) then the integrals must be performed by some other method. It is these constant-$`\tau `$ cases that produce the “stationary” central spikes seen in the simulations for an even number of coins (more on these below).

If we restrict to the special case where $`t_1=t_2=\mathrm{}=t_m=t/M`$ is an integer, then equation (B.9) simplifies somewhat to

$$\begin{array}{c}|\psi _{n,(Mn)}(x,t)=_{r=0}^{M/2}_{j=0}^{n/2}\left(\genfrac{}{}{0pt}{}{M}{r}\right)\frac{1+(1)^{x+(M2r)t/M}}{2^M}\times \hfill \\ \hfill _\pi ^\pi \frac{dk}{2\pi }\left(\frac{\left(\mathrm{cos}(k)+\sqrt{1+\mathrm{cos}^2(k)}\right)^{n2j}e^{ik(Mn)}}{(1+\mathrm{cos}^2(k))^{M/2}}\right)e^{i(\omega _k(M2r)t/M+kx)}.\end{array}$$
(B.12)
All of the time-dependent integrals are of the form

$$I(\alpha ,\tau )=_\pi ^\pi \frac{dk}{2\pi }g(k)e^{i\phi (k,\alpha _\tau )|\tau |},$$
(B.13)
i.e., these are one-parameter families of generalized Fourier integrals, with parameter $`\alpha _\tau =x/\tau .`$ They can therefore be approximated in the limit as $`\tau \mathrm{}`$ by the method of stationary phase, as used in Nayak and Vishwanath (2000), and references therein, principally Bleistein and Handelsman (1975) and Bender and Orszag (1978). When each coin is used the same number of times, it can be seen that the spikes are equally spaced between $`t/\sqrt{2}`$ and $`t/\sqrt{2}.`$ It can also be shown that the height of the peaks scales like $`1/\sqrt[3]{t}.`$

The asymptotic behavior of the time-dependent terms in the above components is as follows. Just as in the one coin case, the integral displays three different types of behavior, depending on $`\alpha _\tau ,`$ and we refer readers interested in the details of the analysis to Nayak and Vishwanath (2000). For the purposes of calculating the moments of the distribution, we can treat the support of the integral as confined to the region $`\alpha _\tau (\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}})`$ to a good approximation, and so we will only do the calculations for $`\alpha _\tau `$ in this range. All the integrals have the same form, and differ only by a linear rescaling.

The values of $`k`$ corresponding to the two stationary points of $`\phi (\alpha _\tau )`$ are $`\pm k_{\alpha \tau },`$ where $`k`$ is a function of $`\alpha _\tau `$, and

$$\mathrm{cos}(k_{\alpha \tau })=\frac{\alpha _\tau }{\sqrt{1\alpha _\tau ^2}}.$$
(B.14)
We also write

$`\phi (\alpha _\tau )=(\omega _{k_{\alpha \tau }}+\alpha _\tau k_{\alpha \tau })`$ $`\omega _{k_{\alpha \tau }}=\mathrm{arcsin}\left(\sqrt{{\displaystyle \frac{12\alpha _\tau ^2}{2(1\alpha _\tau ^2)}}}\right),`$ (B.15)
and note that

$`|\omega _{k_{\alpha \tau }}^{\prime \prime }|`$ $`=(1\alpha _\tau ^2)\sqrt{12\alpha _\tau ^2}`$ (B.16)
$`1+{\displaystyle \frac{\mathrm{cos}(k)}{\sqrt{1+\mathrm{cos}^2(k)}}}`$ $`=1\alpha _\tau `$ (B.17)
$`{\displaystyle \frac{e^{ik}}{\sqrt{1+\mathrm{cos}^2(k)}}}`$ $`=\alpha _\tau +i\sqrt{12\alpha _\tau ^2}.`$ (B.18)
Using these, we can now write down our asymptotic approximations for the time-dependent components. Let us consider the two-coin walk as an example. The time-dependent components $`\stackrel{~}{\psi }(x,t)`$ for the two-coin wavefunction are then

$$|\stackrel{~}{\psi }_{RR}(x,t)=\frac{1+(1)^{(\alpha +1)t}}{\sqrt{2\pi t(1\alpha ^2)\sqrt{12\alpha ^2}}}(1\alpha )^2\mathrm{cos}(\phi (\alpha )t+\pi /4),$$
(B.19)
$$\begin{array}{c}|\stackrel{~}{\psi }_{LR}=|\stackrel{~}{\psi }_{RL}=\frac{1+(1)^{(\alpha +1)t}}{\sqrt{2\pi t(1\alpha ^2)\sqrt{12\alpha ^2}}}\hfill \\ \hfill \times ((\alpha (\alpha 1)\mathrm{cos}(\phi (\alpha )t+\pi /4)+(\alpha 1)\sqrt{12\alpha ^2}\mathrm{sin}(\phi (\alpha )t+\pi /4)),\end{array}$$
(B.20)
and

$$\begin{array}{c}|\stackrel{~}{\psi }_{LL}=\frac{1+(1)^{(\alpha +1)t}}{\sqrt{2\pi t(1\alpha ^2)\sqrt{12\alpha ^2}}}\hfill \\ \hfill \times \left((3\alpha ^21)\mathrm{cos}(\phi (\alpha )t+\pi /4)+2\alpha \sqrt{12\alpha ^2}\mathrm{sin}(\phi (\alpha )t+\pi /4)\right),\end{array}$$
(B.21)
where we have dropped the $`\tau `$ subscript on $`\alpha `$ because there is only one set of asymptotic integrals for this system. These expressions can be used to calculate $`p(x,t)`$ in the long time limit; we plot this result in figure 3.

More generally, for those components which can be obtained using the method of stationary phase, we can write

$$\begin{array}{c}|\psi _{n,(Mn)}(x,t_1,\mathrm{},t_M)=\underset{\tau }{}\frac{(1+(1)^{x+|\tau |})(1\alpha _\tau )^{(n2j_\tau )}(1\alpha _\tau ^2)^{(M+j_\tau n/2)}}{2^{M1}\sqrt{2\pi |\tau |(1\alpha _\tau ^2)\sqrt{12\alpha _\tau ^2}}}\hfill \\ \hfill \times \mathrm{cos}(\phi (\alpha _\tau )|\tau |+(Mn)k_{\alpha _\tau }+\pi /4),\end{array}$$
(B.22)
where $`|\psi _{n,(Mn)}(x,t_1,\mathrm{},t_M)`$ denotes any of the $`\left(\genfrac{}{}{0pt}{}{M}{n}\right)`$ components of the wavefunction which end up with $`n`$ coins in the state $`R`$ and $`(Mn)`$ coins in the state $`L.`$

If $`M`$ is an even number, the wavefunction will have components $`\widehat{\psi }(x)`$ that are central spikes which perform periodic motion for a cyclic walk as the walk cycles through the coins. If the coins are used in some other order, these spikes are the final positions of part of the wavefunction. In any event, these central spikes make no contribution to the moments of the distribution.

Let us write the total wavefunction $`\psi (x,t)=\widehat{\psi }(x)+\stackrel{~}{\psi }(x,t),`$ where $`\stackrel{~}{\psi }(x,t)`$ denotes the rest of the components. For the two-coin case, the central spike components are as follows:

$$|\widehat{\psi }_{RR}(x)=\frac{(1)^{t_1}+(1)^{t_2}}{8\pi }_\pi ^\pi \frac{e^{ikx}}{1+\mathrm{cos}^2(k)}𝑑k$$
(B.23)
$$\begin{array}{c}|\widehat{\psi }_{LR}(x)=\frac{(1)^{t_1}+(1)^{t_2}}{8\pi }_\pi ^\pi \frac{e^{ik(x1)}\mathrm{cos}(k)}{1+\mathrm{cos}^2(k)}𝑑k+\hfill \\ \hfill \frac{(1)^{t_1}(1)^{t_2}}{8\pi }_\pi ^\pi \frac{e^{ik(x1)}}{\sqrt{1+\mathrm{cos}^2(k)}}𝑑k\end{array}$$
(B.24)
$$|\widehat{\psi }_{LL}(x)=\frac{(1)^{t_1}+(1)^{t_2}}{8\pi }_\pi ^\pi \frac{e^{ik(x2)}}{1+\mathrm{cos}^2(k)}𝑑k.$$
(B.25)
These integrals shrink to zero very rapidly away from $`x=0,`$ but they are still visibly non-zero out as far as $`x=\pm 6`$ or so.

These time-independent stationary spike integrals are similar in form to the time-dependent ones, but this time the method of stationary phase isn’t helpful. That asymptotic approximation method can only tell us about their behavior as $`x\mathrm{}.`$ Since we already know that they’re independent of time, we can say that these represent something that stays in the vicinity of the origin and doesn’t go anywhere: so we already know they’ll tend to zero very rapidly for large $`x`$. This means that we’re only interested in their behavior for a few points in the vicinity of the origin. Since the kernel of the integrand oscillates fairly slowly for small values of $`x,`$ it is practical to evaluate these terms numerically.


format: text

text:
# Chern-Simons number asymmetry from CP-violation during tachyonic preheating∗∗Presented by A. Tranberg

## Abstract

We consider the creation of non-zero Chern-Simons number in a model of the early Universe, where the Higgs field experiences a fast quench at the end of inflation. We perform numerical lattice simulations in the Abelian Higgs model in 1+1 dimensions and in the SU(2)-Higgs model in 3+1 dimensions with an added effective CP-violating term. We also comment on the appropriate choice of vacuum initial conditions for classical simulations.

We consider a scenario of baryogenesis in the early Universe, where inflation ends at the electroweak scale . After inflation, the fields are in the ground state at zero temperature (no reheating from the inflaton). Higgs symmetry breaking happens through a quench causing the Higgs field to go through a spinodal instability. CP (and C) is broken by an effective term in the action. Baryon number (B) is not conserved due to Chern-Simons number ($`N_{\text{cs}}`$) changing transitions in the electroweak sector, through the relation $`B(t)B(0)=3\left[N_{\text{cs}}(t)N_{\text{cs}}(0)\right]`$. The three criteria for baryogenesis are thus fulfilled.

We study two models of this system: The Abelian-Higgs model with C and P violation in 1+1 dimensions and the SU(2)-Higgs model with CP violation in 3+1 dimensions. We apply the classical approximation in which quantum averages are replaced by averaging over an ensemble of classical initial conditions, evolved using classical equations of motion. This approximation is valid since large occupation numbers $`n_k`$ are generated by the spinodal instability (see below).

We assume that the end of inflation triggers electroweak symmetry breaking by a rapid change of the effective mass in the Higgs potential $`V(\varphi )=\mu _{\text{eff}}^2\varphi ^{}\varphi +\lambda (\varphi ^{}\varphi )^2`$. We model it by an instantaneous change of the sign of the mass at $`t=0`$, $`\mu _{\text{eff}}^2\mu ^2`$. For $`t>0`$ the original ground state is unstable, and momentum modes with $`|k|<\mu `$ grow exponentially through the spinodal instability. This proceeds until the quartic term becomes important and the fields eventually thermalize in the broken phase at a low temperature.

For small couplings, we can initially neglect the quartic term and gauge fields and solve the quantum evolution of the unstable Higgs field exactly . In terms of correlation functions, the result is ($`\omega _k^\pm =\sqrt{k^2\pm \mu ^2}`$):

$`\varphi _𝐤\varphi _𝐤^{}={\displaystyle \frac{1}{2\omega _k^+}}\left[1+\left({\displaystyle \frac{\omega _k^{+2}}{\omega _k^2}}1\right)\mathrm{sin}^2\left(\omega _k^{}t\right)\right]`$ $`=`$ $`\left(n_k+{\displaystyle \frac{1}{2}}\right){\displaystyle \frac{1}{\omega _k}}`$
$`\pi _𝐤\pi _𝐤^{}={\displaystyle \frac{\omega _k^2}{2\omega _k^+}}\left[1+\left({\displaystyle \frac{\omega _k^{+2}}{\omega _k^2}}1\right)\mathrm{cos}^2\left(\omega _k^{}t\right)\right]`$ $`=`$ $`\left(n_k+{\displaystyle \frac{1}{2}}\right)\omega _k`$
$`\pi _𝐤\varphi _𝐤^{}={\displaystyle \frac{\omega _k^{}}{4\omega _k^+}}\left({\displaystyle \frac{\omega _k^{+2}}{\omega _k^2}}1\right)\mathrm{sin}\left(2\omega _k^{}t\right){\displaystyle \frac{i}{2}}`$ $`=`$ $`\stackrel{~}{n}_k{\displaystyle \frac{i}{2}}`$
where we have defined effective time-dependent particles numbers $`n_k`$, $`\stackrel{~}{n}_k`$ and frequencies $`\omega _k`$. For $`k`$ in the unstable region ($`|k|<\mu `$), $`\omega _k^{}=i\sqrt{\mu ^2k^2}`$ and $`n_k`$ and $`\stackrel{~}{n}_k`$ grow exponentially $`\mathrm{exp}\left(2\sqrt{\mu ^2k^2}t\right)`$. At some time during the rolling down, we can switch to a classical description through an ensemble of classical initial conditions. The classical correlation functions are taken to be the real parts of the quantum ones.

The initial quantum state ($`t=0`$) has $`n_k=\stackrel{~}{n}_k=0`$. For $`t>0`$, $`\stackrel{~}{n}_k0`$ and the uncorrelated variables are $`\xi _𝐤^\pm =\left(\pi _𝐤/\sqrt{\omega _k}\pm \sqrt{\omega _k}\varphi _𝐤\right)/\sqrt{2}`$. At $`t=t_{ro}`$ we draw sets of random numbers $`\xi _𝐤^\pm `$ from the distribution:

$`P(\xi _𝐤^\pm )\mathrm{exp}\left\{{\displaystyle \frac{1}{2}}{\displaystyle \underset{|k|<\mu }{}}\left({\displaystyle \frac{\xi _𝐤^+\xi _𝐤^+}{n_k+\frac{1}{2}+\stackrel{~}{n}_k}}+{\displaystyle \frac{\xi _𝐤^{}\xi _𝐤^{}}{n_k+\frac{1}{2}\stackrel{~}{n}_k}}\right)\right\}`$
As t grows, $`\stackrel{~}{n}_kn_k+\frac{1}{2}`$, and we obtain the classical relation $`\xi _𝐤^{}0`$, or $`\pi _𝐤=\omega _k\varphi _𝐤`$.

The classical approximation of the dynamics is valid for sufficiently large $`t_{ro}`$. However, if the assumption of small coupling is correct, the classical evolution is equal to the quantum spinodal evolution, and it should not matter which $`t_{ro}`$ we choose. A special case is $`t_{ro}=0`$, where $`n_k+\frac{1}{2}=\frac{1}{2}`$. We call this the “Just the half” case. For all $`t_{ro}`$, we only initialize modes with $`|k|<\mu `$. Eventually, the quartic term will become important and the approximation breaks down. $`t_{ro}`$ can therefore not be too large (Fig. 1, left plot).

In the bulk of our study of the CP- violation we chose to describe the state just before the quench by a Bose-Einstein (BE) distribution at low temperature:

$`n_k+{\displaystyle \frac{1}{2}}n_k^{BE}={\displaystyle \frac{1}{e^{\omega _k^{BE}/T}1}}`$ $`,`$ $`\omega _k\omega _k^{BE}=\sqrt{\mu ^2+k^2}`$
The Abelian Higgs model in 1+1 dimensions is defined by the action:

$`S={\displaystyle }dtdx[{\displaystyle \frac{1}{4e^2}}F_{\mu \nu }F^{\mu \nu }+(D_\mu \varphi )^{}D^\mu \varphi \mu ^2\varphi ^{}\varphi +\lambda (\varphi ^{}\varphi )^2`$
$`+{\displaystyle \frac{\kappa }{2}}ϵ_{\mu \nu }F^{\mu \nu }\varphi ^{}\varphi ]`$
The last term violates C and P. We used BE initial conditions at $`T/m_H=0.1`$ with $`\lambda /\mu ^2=1/8`$. The initial gauge field is given by solving the Gauss constraint. We used averages over an ensemble of 1000 initial configurations.

For non-zero $`\kappa `$ we can estimate the initial effect of the C/P breaking term from the equations of motion, with the result $`N_{\text{cs}}(t_{in})=\kappa (m_W^2Lm_H)/(m_H^26\sqrt{8}\pi )`$, where $`\varphi ^{}\varphi (t_{in})=\mu ^2/3\lambda `$. Indeed we see such an initial dip (Fig. 1, right plot). The final (at $`tm_H=600`$) $`N_{\text{cs}}`$ is linear in $`\kappa `$ (Fig. 2) and depends sensitively on $`m_H/m_W`$ (Figs. 2,3).

The SU(2)-Higgs model is given by the action:

$`S_{cl}={\displaystyle }d^4x[{\displaystyle \frac{1}{2g^2}}\text{Tr}F_{\mu \nu }F^{\mu \nu }+(D_\mu \varphi )^{}D^\mu \varphi \mu ^2\varphi ^{}\varphi +\lambda (\varphi ^{}\varphi )^2`$
$`+\kappa \varphi ^{}\varphi \text{Tr}F^{\mu \nu }\stackrel{~}{F}_{\mu \nu }]`$
$`\stackrel{~}{F}_{\mu \nu }`$ is the dual field strength and $`\varphi `$ the Higgs doublet field. The last term breaks CP. We used initial conditions similar to the 1+1 dimensional case. The results for $`m_H=m_W`$ are shown in Figs. 4, 5.

We can estimate the final temperature after symmetry breaking from $`\frac{\pi ^2}{30}g_{}T^4=V(0)=\frac{m_H^4}{16\lambda }`$. Using $`n_B=\frac{3N_{\text{cs}}}{V},s=\frac{2\pi ^2}{45}g_{}T^3`$ with $`g_{}=80`$, $`Lm_H=21`$, $`\lambda =1/18`$, we find ($`k=16\pi ^2\kappa `$)

$`<N_{\text{cs}}>_{k=3/m_H^2}0.2{\displaystyle \frac{n_B}{n_\gamma }}(\kappa )7\times 10^3\kappa m_W^25\times 10^5\kappa \text{TeV}^2`$
This result seems quite reasonable, and requires that $`\kappa 10^7/m_W^2`$. For additional information on tachyonic preheating, see the accompanying contribution .

Acknowledgments: This work was supported in part by FOM. AT enjoyed support from the ESF network COSLAB.


text:
# Large-field versus discontinuous instantons in spin orientation tunneling

## I Introduction

The purpose of this short note is to clarify the differences between certain types of instantons that arise in the study of spin orientation tunneling in molecular magnets. The problem derives from the specific phenomenon of tunnel splitting or gap oscillations in the molecular ion \[(tacn)6Fe8O2(OH)12\]8+ (abbreviated to Fe8 henceforth) werns , but our considerations should apply to other molecular magnetic system as well.

The simplest model Hamiltonian that leads to gap oscillations is

$$_0=k_1J_z^2+k_2J_y^2g\mu _B𝐉𝐇,$$
(1)
where $`𝐉`$ is a dimensionless spin operator, $`k_1>k_2>0`$, and $`𝐇`$ is an external magnetic field. It is known that for $`𝐇\widehat{𝐳}`$, the tunnel splitting, or gap, between the two lowest eigen states of $`_0`$ oscillates as a function of $`H_z`$, vanishing whenever gargepl

$$H_z=\frac{1}{J}\left(Jn\frac{1}{2}\right)H_c.$$
(2)
Here,

$$\lambda =k_2/k_1,\mathrm{and}H_c=2k_1J/g\mu _B.$$
(3)
For Fe8, for which $`J=10`$, $`k_1=0.338`$ K, and $`k_2=0.246`$ K, this would imply that the splitting is quenched at 10 values of $`H_z>0`$, equally spaced by 0.263 T. This quenching phenomenon is nicely interpreted in terms of interfering semiclassical paths, or instantons wilk .

In reality, only four quenches are seen in Fe8, and the spacing between the quenches is $`0.41`$ T, 50% larger than predicted by Eq. (2). Both these facts are accounted for by a slightly modified Hamiltonian

$$_1=_0C[(J_z+iJ_y)^4+\mathrm{h}.\mathrm{c}.],$$
(4)
with $`C=0.29\mu `$K, as is easily verified by explicit numerical diagonalization. The fact that only 4 quenches are seen is paradoxical, however. The relative phase between the interfering instantons is a topological quantity, so that it must equal $`J\pi `$ at $`H=0`$, and tend to 0 as $`HH_c`$. There is no apparent way to get other than 10 quenches. The resolution is that the $`C`$ term, though small, has a dramatic effect: any non zero $`C`$ leads to the existence of instantons that are discontinuous at the end points kg2 . One of these instantons ends up being the dominant one by virtue of having the lowest action beyond a certain field ($`0.25H_c`$ for Fe8), and since it has no interfering partner, there are no more quenches of the splitting beyond this field. In this way, the discontinuous or jump instantons may be said to shunt the interference effect. The jump instantons have discontinuities, and thus do not have to respect the topology.

In private correspondence to us, E. Chudnovsky has alleged that jump instantons were first introduced by him and Hidalgo in an earlier study of the simpler Hamiltonian (1) at high fields ecxmh . We disagree. The instanton studied by Chudnovsky and Hidalgo (CH) is of exactly the standard continuous type arising in the study of a particle tunneling in a symmetric one-dimensional double well, but its nature is obscured by the subtleties of spin trajectories, and the singularities of the spherical polar coordinate system on the sphere. These subtleties are vexing and the source of innumerable pitfalls, so it seems useful to us to elaborate on the instantons in question, and show explicitly that they are continuous. We also use the opportunity to correct a misconception in a still earlier study of the same problem, i.e., Eq. (1) at high fields, by one of us agprb99 .

## II Details

We consider only fields parallel to $`\widehat{𝐳}`$, and define the reduced field

$$h=H/H_c,$$
(5)
and the special value

$$h^{}=(1\lambda )^{1/2}.$$
(6)
CH study the problem for $`h>h^{}`$, and Chudnovsky is asserting that the instantons in that study have jumps. We give three arguments to show that this is not so.

The first and mathematically simplest way is to consider fields just less than $`H_c`$. We write

$$h=(1\eta )$$
(7)
where $`0<\eta 1`$. The expectation value of $`J_z`$ in the low energy states is then extremely close to $`J`$, so we can approximate

$$J_xJq,J_yp,$$
(8)
where $`p`$ and $`q`$ are momentum and position operators with the commutator $`[q,p]=i`$. It is self-consistently verifiable that $`J_y\eta `$, $`J_x\eta ^{1/2}`$, so that we can write $`J_z(J^2J_x^2J_y^2)^{1/2}`$. Expanding the term $`g\mu _bHJ_z`$ to order $`J_y^2`$ and $`J_x^4`$, rewriting in terms of $`q`$ and $`p`$, and omitting an additive constant, we arrive at the equivalent Hamiltonian

$$_{\mathrm{equiv}}=\frac{1}{2m}p^2+\frac{1}{4}k_1hJ^2q^4\eta k_1J^2q^2.$$
(9)
Here,

$$m=[2(k_2\eta k_1)]^1(2k_2)^1.$$
(10)
Equation (9) is the Hamiltonian for the particle in a quartic double well. The minima of the well are at $`\pm q_0=\pm (2\eta )^{1/2}.`$ The instantons for this problem are known, and the one that runs from $`q_0`$ to $`q_0`$ is given by

$`q(t)`$ $`=`$ $`q_0\mathrm{tanh}\gamma t,`$ (11)
$`p(t)`$ $`=`$ $`im\gamma q_0\mathrm{tanh}\gamma t\mathrm{sech}^2\gamma t.`$ (12)
Here, $`t`$ is an imaginary time, and $`\gamma =(2k_1k_2\eta )^{1/2}J`$. If we transcribe these results back into $`J_x`$, $`J_y`$, and $`J_z`$, it is manifest that the spin trajectory goes continuously from one minimum of the classical energy to the other without any jumps. There is nothing in the physical character of the problem to indicate a qualitative change as $`H`$ is reduced, so as long as one is in the field range where the gap does not oscillate ($`h>h^{}`$), the instantons should be continuous.

In our second argument, we study the instantons for all $`H`$. Since these lie on the complex unit sphere, it is highly advantageous to use stereographic coordinates,

$$z=\mathrm{tan}\frac{1}{2}\theta e^{i\varphi },\overline{z}=\mathrm{tan}\frac{1}{2}\theta e^{i\varphi },$$
(13)
where $`\theta `$ and $`\varphi `$ are the customary spherical polar coordinates. If a direction $`\widehat{𝐧}`$ has coordinates $`(\theta ,\varphi )`$, and if $`|\widehat{𝐧}`$ is the spin coherent state with maximal spin projection along $`\widehat{𝐧}`$, then up to normalization and phase, $`|\widehat{𝐧}`$ is identical to $`|ze^{zJ_{}}|J,J`$ where $`𝐉^2|J,J=J(J+1)|J,J`$ and $`J_z|J,J=J|J,J`$. A point on the complex unit sphere is parametrized by complex $`\theta `$ and $`\varphi `$, which means that $`z`$ and $`\overline{z}`$ need not be complex conjugates; rather, they are independent complex variables. Either coordinate system shows that the complex unit sphere is a four-dimensional manifold, but the $`(z,\overline{z})`$ system handles coordinate singularities better. In terms of $`z`$ and $`\overline{z}`$, the cartesian components of $`𝐉`$ are given by

$$(J_x,J_y,J_z)=\frac{J}{1+\overline{z}z}(z+\overline{z},i(z\overline{z}),1\overline{z}z).$$
(14)
The south pole is the point $`z=\overline{z}=\mathrm{}`$; if $`z\mathrm{}`$ with $`\overline{z}`$ finite, $`𝐉J(\overline{z}^1,i\overline{z}^1,1)`$; if $`\overline{z}\mathrm{}`$ with $`z`$ finite, $`𝐉J(z^1,iz^1,1)`$.

We have found the instantons for this problem in Ref. gkps,  among other places, but we restate the results along with some attendant formulas for ready reference, and to enable readers to verify the key results for themselves. Let us define

$$E(\overline{z},z)=z||z/z|z.$$
(15)
Then the Euler-Lagrange equations of motion for the instantons are given by

$$\dot{\overline{z}}=\frac{(1+\overline{z}z)^2}{2J}\frac{E}{z},\dot{z}=\frac{(1+\overline{z}z)^2}{2J}\frac{E}{\overline{z}}.$$
(16)
With the Hamiltonian (1),

$$E(\overline{z},z)=k_1J^2\left[\frac{(1\overline{z}z)^2\lambda (z\overline{z})^22h(1\overline{z}^2z^2)}{(1+\overline{z}z)^2}\right],$$
(17)
so that

$`\dot{z}`$ $`=`$ $`{\displaystyle \frac{k_1J}{(1+\overline{z}z)}}\left[2z(1\overline{z}z)+\lambda (z\overline{z})(1+z^2)+2hz(1+\overline{z}z)\right],`$ (18)
$`\dot{\overline{z}}`$ $`=`$ $`{\displaystyle \frac{k_1J}{(1+\overline{z}z)}}\left[2\overline{z}(1\overline{z}z)+\lambda (\overline{z}z)(1+\overline{z}^2)+2h\overline{z}(1+\overline{z}z)\right].`$ (19)
The minima of $`E`$ are at $`\overline{z}=z=\pm z_0`$ where $`z_0=[(1h)/(1+h)]^{1/2}`$. There are two solutions to the equations of motion that run from $`z_0`$ to $`z_0`$. The first is given by

$`z^{(1)}(t)`$ $`=`$ $`z_0\mathrm{tanh}\tau ,`$ (20)
$`\overline{z}^{(1)}(t)`$ $`=`$ $`z_0{\displaystyle \frac{\sqrt{\lambda }\mathrm{tanh}\tau +\sqrt{1h^2}}{\sqrt{\lambda }+\sqrt{1h^2}\mathrm{tanh}\tau }},`$ (21)
while the second is given by

$`z^{(2)}(t)`$ $`=`$ $`z_0{\displaystyle \frac{\sqrt{\lambda }\mathrm{tanh}\tau \sqrt{1h^2}}{\sqrt{\lambda }\sqrt{1h^2}\mathrm{tanh}\tau }},`$ (22)
$`\overline{z}^{(2)}(t)`$ $`=`$ $`z_0\mathrm{tanh}\tau .`$ (23)
We have defined $`\tau =\omega t/2`$, with $`\omega =2k_1J[\lambda (1h^2)]^{1/2}`$. Readers can verify by direct substitution into the equations of motion that these are indeed solutions. Also, we have

$$z^{(2)}(t)=\overline{z}^{(1)}(t),\overline{z}^{(2)}(t)=z^{(1)}(t).$$
(24)
For $`h<h^{}`$, the two solutions can be seen to be distinct by noting that in the first $`\overline{z}`$ diverges at some $`t`$ with $`z`$ remaining finite, while in the other the converse happens. The action for these two instantons differs by a field dependent phase, which gives rise to the gap oscillation.

For $`h>h^{}`$, on the other hand, the two solutions are physically identical. To see this, let us note that we can write

$`z^{(1)}=z_0\mathrm{tanh}\tau ,`$ $`\overline{z}^{(1)}=z_0\mathrm{tanh}(\tau +\tau _0),`$ (25)
$`z^{(2)}=z_0\mathrm{tanh}(\tau \tau _0),`$ $`\overline{z}^{(2)}=z_0\mathrm{tanh}\tau ,`$ (26)
where,

$$\tau _0=\mathrm{tanh}^1\sqrt{\frac{1h^2}{\lambda }}.$$
(27)
If $`h>h^{}`$, $`\tau _0`$ is real, so the two solutions are related by a simple translation in time. Such translations are automatically included in the sum over multiinstanton paths, so there is only one type of instanton.

More importantly, the instanton is entirely continuous. We plot the components of $`𝐉`$ versus $`\tau `$ in Fig. 1. As can be seen, there is no discontinuity in any component. This figure should be compared with Fig. 2 of Ref. kg2, , which pertains to the problem with the $`C`$ term in Eq. (4), and shows instantons with patent jumps.

Thirdly, let us consider the problem in spherical polar coordinates, as is also done by CH, and in Ref. agprb99, . CH proceed by integrating out $`\mathrm{cos}\theta `$, which is feasible as the integral is Gaussian. The resulting action for $`\varphi `$ is like that of a massive particle. If one now seeks instantons for this problem analogously to the particle in a quartic double well say, and insists on a solution $`\varphi (\tau )`$ in which $`\varphi `$ is real, one discovers that the variable $`\tau `$ cannot be real, but rather must follow a Z-shaped contour in the complex plane, consisting of two segments parallel to the real axis, joined by a segment along the imaginary axis complext . This is very different, however, from a discontinuity in $`\varphi `$ itself. Indeed, CH seem aware of this point, for they say “It is clear from the shape of the potential that all three parts of the trajectory join smoothly, because $`\varphi (\tau )`$ and $`\dot{\varphi }(\tau )`$ coincide at the joints.” We agree with this. And, it is clear that if one finds the dominant path for $`\mathrm{cos}\theta (\tau )`$, i.e., the value of $`\mathrm{cos}\theta `$ for which the original Gaussian factor is maximal, one will discover that $`\mathrm{cos}\theta (\tau )`$ is also continuous. To eliminate any doubt, we show this by examining the explicit solution for the instanton from Ref. agprb99, . In our present notation, this reads

$`\mathrm{cos}\varphi `$ $`=`$ $`i{\displaystyle \frac{(h^2+\lambda 1)^{1/2}\mathrm{tanh}2\tau }{(1h^2\lambda \mathrm{tanh}^22\tau )^{1/2}}}`$ (28)
$`\mathrm{cos}\theta `$ $`=`$ $`{\displaystyle \frac{h(1h^2\lambda \mathrm{tanh}^22\tau )(1h^2)\lambda ^{1/2}(h^2+\lambda 1)^{1/2}\mathrm{sech}\mathrm{\hspace{0.17em}2}\tau }{1h^2\lambda +h^2\lambda \mathrm{sech}^22\tau }}.`$ (29)
From these one can construct the combinations $`\mathrm{tan}\frac{1}{2}\theta e^{\pm i\varphi }`$ to obtain $`z`$ and $`\overline{z}`$. After a certain amount of algebra, we obtain

$$\left(\begin{array}{c}z(t)\\ \overline{z}(t)\end{array}\right)=z_0\frac{\mathrm{tanh}\tau \pm \alpha }{1\pm \alpha \mathrm{tanh}\tau },$$
(30)
where

$$\alpha =\frac{(h^2+\lambda 1)^{1/2}\lambda ^{1/2}}{(1h^2)^{1/2}}.$$
(31)
If we now note that

$$\mathrm{tanh}^1\alpha =\tau _0/2,$$
(32)
we see that Eq. (30) is the same as Eqs. (20) and (21) up to a shift in $`\tau `$. Again, we see that there is no discontinuity in the instanton.

It is a separate issue as to what contour what chooses for $`\tau `$. If, instead of the real line, one lets $`\tau `$ run on the Z-shaped contour in Ref. agprb99, , $`z`$ will run from $`z_0`$ to $`z_0`$ along some contour other than the real line, while $`\overline{z}`$ will run along some other contour, such that

$$\overline{z}(t)=\frac{\sqrt{\lambda }z(t)(1h)}{\sqrt{\lambda }(1+h)z(t)}$$
(33)
\[This can be verified directly from Eq. (30), and it is a consequence of energy conservation along the instanton.\] Since the kinetic term in the action can be written as a contour integral over $`z`$,

$$S=J\frac{1}{1+\overline{z}z}\left[\overline{z}(z)z\frac{d\overline{z}}{dz}\right]𝑑z$$
(34)
it follows that any deformation of the $`z`$-contour that does not cross any singularities of $`\overline{z}(z)`$ is allowed. This is indeed the case for us, as for $`h>h^{}`$, the pole at $`z=\sqrt{\lambda }/(1+h)`$ lies outside the segment $`[z_0,z_0]`$ on the real line.

We conclude by clarifying the misconception in Ref. agprb99, . The discussion above shows that there is only one instanton when $`h>h^{}`$, whereas, in the earlier work it is implicit that there are two, with equal, real Euclidean actions chact2 . However, the central thesis of that work, and the calculation of the action itself, are completely unaffected.

One further point is that at exactly at $`h=h^{}`$, standard instanton calculations of the Hamiltonian (1) cease to be valid, because two distinct instantons merge into one. This is rather like the phenomenon of merging critical points in the steepest descent approximation for ordinary integrals bleihan . We expect existing formulas for the tunnel splitting to be inaccurate in a narrow window of fields near $`h=h^{}`$. The gap can undoubtedly be bridged via a uniform asymptotic approximation, which could be developed using the discrete phase integral method as in Ref. agdpi, . In the methodology of that paper, what happens as we cross the point $`h=h^{}`$ from below is that the width of the unusual forbidden region, in which the wavefunctions are exponentially damped with oscillations, shrinks to zero. In this case, one should join the wavefunctions on the two sides of this region using one quadratic turning point connection formula as opposed to two linear turning point formulas. We leave this as an exercise for the reader.

In summary, we have shown that that the high-field instantons in the Fe8 problem are continuous, and thus qualititatively distinct from the discontinuous instantons induced by the fourth order anisotropy in Eq. (4).

## III Acknowledgments

This research is supported by the National Science Foundation via Grant No. DMR-0202165.