Superdiffusivity of quantum walks: A Feynman sum-over-paths description

F. M. Andrade1, ∗ and M. G. E. da Luz2, †

1
Departamento de Matemática e Estatı́stica, Universidade Estadual de Ponta Grossa, 84030-900 Ponta Grossa-PR, Brazil
2
Departamento de Fı́sica, Universidade Federal do Paraná, C.P. 19044, 81531-980 Curitiba-PR, Brazil
(Dated: September 28, 2012)
Quantum walks constitute important tools in different applications, especially in quantum algo-
rithms. To a great extent their usefulness is due to unusual diffusive features, allowing much faster
spreading than their classical counterparts. Such behavior, although frequently credited to intrinsic
quantum interference, usually is not completely characterized. Using a recently developed Green’s
function approach [Phys. Rev. A 84, 042343 (2011)], here it is described – in a rather general
way – the problem dynamics in terms of a true sum over paths history a la Feynman. It allows
arXiv:1209.4953v2 [quant-ph] 27 Sep 2012

one to explicit identify interference effects and also to explain the emergence of superdiffusivity.
The present analysis has the potential to help in designing quantum walks with distinct transport
properties.

PACS numbers: 03.67.Lx, 05.40.Fb

I. INTRODUCTION [28]. However, they address the problem from a different

perspective, using combinatorial analysis to compute fi-
Quantum walks (QWs), a quantum version of classical nal states [29], but not considering intermediary steps in
random walks (CRWs) [1], is a relatively simple class terms of Feynman’s history of trajectories [30]. Hence,
of systems, yet containing almost all the essential as- interference is not made truly explicit.
pects of quantum mechanics [2, 3]. They can be used In the present work we show how quantum interference
to model a large number of phenomena [4, 5], such as: determines QWs uncommon diffusive properties. To this
energy transport in biological systems [6]; Bose-Einstein end, the exact Green’s function [31] – given as a general
condensates redistribution [7]; quantum phase transition sum of paths – is written in a closed analytical form.
in optical lattices [8]; and decoherence processes [9]. But, Then, we describe how to calculate relevant quantities in
certainly where QWs have attracted more interest is in a way identifying the trajectories superposition contri-
quantum computing [10, 11]. In fact, QWs allow the butions. To concretely illustrate the approach, we show
development of new quantum algorithms [12], which of- that the usually observed: (a) complicated oscillatory
ten display much better performance than their classical behavior of the probability distribution for visits at dif-
siblings [12, 13]. ferent sites; and (b) the process dispersion dependence on
QWs usefulness in applications is in great part due to time; are associated to the complex multiple reflections
their unusual transport properties. For instance, they and transmission patterns of the system evolved paths.
present exponentially faster hitting times [14–16] (the Finally, we mention some important technical aspects.
time necessary to visit any vertex in the system graph There are several ways to formulate QWs, all defined in
space), an important feature for searching in discrete discrete spaces (graphs) [2]. Also, time may be either a
databases [17, 18]. Such faster spreading compared to continuous [14] or a discrete variable. In the latter, the
CRWs [2] is usually attributed to interference [5, 19], a major formulations are coined [32] and scattering [33]
key ingredient in implementations [20, 21] and believed QWs. Continuous time and coined are related through
central to explain distinct behaviors [22]. However, ex- appropriate limits [34], whereas coined and scattering are
actly how these effects emerge in QWs usually is not to- unitarily equivalent in any topology and for arbitrary
tally characterized [23], posing challenges as to how one transition amplitudes [35]. Hence, we consider only scat-
could properly link the high degree of entanglement in tering quantum walks (SQWs), keeping in mind that our
QWs [24] with interference. Furthermore, since interfer- finds can be extended to such other constructions as well.
ence actually comes from a high proliferation of paths Moreover, the Green’s function method considered here
(after all, QWs are associated to the idea of CRWs [25]), [31] is valid for any graph topology. Although for our
it also bears on the problem of how decoherence [26] can purposes we address QWs on the line, avoiding extra
make the “quantum trajectories” to become classical [27]. and unnecessary mathematical complications, we men-
In trying to understand interference in QWs, a path tion that the same type of analysis would likewise work
integral-like treatment would be appropriate. Actually, in more complex networks.
a few interesting works along this line have been proposed

II. THE SUM OVER PATHS DESCRIPTION

∗ fmandrade@uepg.br We assume an undirected 1D lattice of equally spaced

† luz@fisica.ufpr.br vertices labeled in Z, Fig. 1. Pairs of neighbor vertices
 2

(+)
tj (−) j − 1 and j (j and j + 1) we have | + 1, ji and | − 1, j − 1i
rj (| + 1, j + 1i and | − 1, ji). Therefore, the full set {|σ, ji}
vertex j
(+) spans all the possible system states |ψi. The quantum
rj (−)
tj numbers σ = ±1 (hereafter for short ±) represent the
propagation direction along the lattice (or graph). The
+1, j +1, j+1
discrete dynamics is given by the one step time evolution
−1, j−1 −1, j operator U , such that the state at times m + 1 and m
are related by |ψ(m + 1)i = U |ψ(m)i. For an arbitrary
FIG. 1. QWs graph structure in 1D. At each edge there are phase z = exp[iγ], we have [31]
two basis states, e.g., |+, ji and |−, j − 1i (schematically rep-
(σ) ∗ (−σ) ∗
 
resented by arrows) for the edge between j −1 and j. In detail U † |σ, ji = z ∗ tj−σ |σ, j − σi + rj−σ | − σ, j − σi ,
the vertex dependent scattering quantum amplitudes.  
(σ) (σ)
U |σ, ji = z tj |σ, j + σi + rj | − σ, j − σi . (1)
(+) (−)
T j−n+1 T j−1
(a)
(−) (+) (−) (+) (±) (±)
R j−n R j−n+1 R j−1 R j Here [35] (with 0 ≤ rj , tj ≤ 1 and 0 ≤ φt,j , φr,j < 2π)
j−n f j−n+1 j−1 i j j+n−1 j+n (+) (−) (+) (−)
rj2 + t2j = 1, φr;j + φr;j = φt;j + φt;j ± π,
(b) (±)
tj
(±)
= tj exp[iφt;j ],
(±)
rj
(±)
= rj exp[iφr;j ], (2)
(−) (+)
R j−1 R j

j−n j−n+1 j−1 i,f j j+n−1

guarantee the evolution unitarity. The r’s and t’s can
j+n
be understood as the vertices reflection and transmission
Tj
(+) (−)
T j+n−1 quantum amplitudes (see Fig. 1).
(c)
(−) (−) (+) The problem is fully described by the Green’s function
R j−1 R (+) R j+n−1R j+n
j
approach in [31]. Consider the walk starting at the edge
j−n j−n+1 j−1 i j j+n−1 f j+n i (between the vertices j − 1 and j) with the state di-
rection σ and finally getting to the edge f (between the
FIG. 2. For G, the three possible situations for the relative vertices j ± n and j ± (n − 1), for any n = 0, 1, 2, . . .).
positions of the initial and final, i and f , edges. The three possible situations are illustrated in Fig. 2.
Then, the most general exact expression for the Green’s
function, representing the transmission probability am-
are joined by a single edge. To each edge we ascribe two plitude {σ, i} → f reads (s = −1 (+1) [in short ∓] for f
basis states. For instance, in Fig. 1 for the edge between to the right (left) of i and s = 0 for f equal to i)

 h i(1+sσ)/2 |s|  
(3+sσ)/2 (s) (−s) (−s+(1−|s|)σ)
z Rj−(1−s)/2 Tj−(s+1)/2 1 + z Rj−sn+(1−|s|)(σ−1)/2
Gf,{σ,i} =  |s|    . (3)
(−s) (s) (−) (+) (s) (−s) (−s) (s)
1 − z 2 Rj−sn Rj−s(n−1) 1 − z 2 Rj−1 Rj − |s| z 4 Rj+(s−1)/2 Rj−sn Tj−(s+1)/2 Tj−s(n−1)

(±) (±)
The composed coefficients Rj and Tj , functions of (3). There are different contexts for which we may seek
the individual amplitudes and
(±)
are obtained
rj ’s
(±)
tj ’s, the amplitude transition {σ, i} → f . Common ones are:
(i) exactly after m = M time steps; and (ii) when the
from the following recurrence relations [36] (µ− = j −
system never visits vertices further to the left and to the
(s + 1)(n − 1)/2 and µ+ = j − 1 − (s − 1)n/2 for s 6= 0)
right than, respectively, j = Jl and j = Jr (e.g., for first
(±) (∓) (±) passage time calculations). In both we just need two ex-
(±) (±) z 2 tk tk Rk±1
Rk = rk + (∓) (±)
, Rµ(±)
±
= rµ(±)
±
, (+) (+) (−)
tra relations for Eq. (4): RJr = rJr and RJl = rJl .
(−)
1 − z 2 rk Rk±1
Moreover, for (i) we have Jl = (j −1)−[(M +sn−δ1 s )/2]
(±) (±)
(±) z tk Tk±1 and Jr = j+[(M −sn+δ1 s )/2], with [x] the integer part of
Tk = , Tµ(±) = tµ(±) . (4) x and n taken consistently. Finally, for Eq.
(∓)
1 − z 2 rk Rk±1
(±) ± ±
P (3) obviously
|ψ(0)i = |σ, j + (σ − 1)/2i. For |ψ(0)i =P cσ,j |σ, ji, the
In Eq. (3) it is not specified what is the final direction correct Green’s function would be G = cσ,j Gf,{σ,i|σ,j } .
quantum number, ν, when arriving at f . In fact, it in- The above exact expression is derived from a sum
cludes both cases once ν = σ (−σ) corresponds to the over infinite many “scattering paths” [31, 37], starting
term 1 (zR) in the second (. . .) in the numerator of Eq. and ending at the edges i and f . Its advantage is that
 3

m=0 m=1 m=2

all the possible quantum walk trajectories are “com-
pacted” into a closed formula. So, distinct interference
j−1 j j−1 j j+1 j−2 j−1 j j+1 j+2
phenomena can be extract from G. Indeed, as demon-
m=3
strated in [31], this is achieved in a rather systematic
way by means of two differential operators. The proba-
j−5 j−4 j−3 j−2 j−1 j j+1 j+2 j+3 j+4 j+5
bility for {σ, i} → f in exactly m time steps is given by
1 ∂m m=4
p{σ,i}→f (m) = |Ŝm Gf,{σ,i} |2 , with Ŝm = m! ∂z m |z=0 the
Step
P Operator. To see it, we note that [31] Ŝ m Gf,{σ,i} = j−5 j−4 j−3 j−2 j−1 j j+1 j+2 j+3 j+4 j+5

s.p. P s.p. , for each P s.p. being the contribution of a tra- m=5
jectory from i to f in m steps [38]. Interference comes
into play when we take the modulus square of such ex- j−5 j−4 j−3 j−2 j−1 j j+1 j+2 j+3 j+4 j+5

pansion. Also, any specific P follows from P̂P G, for the

Path Operator (superscripts ± omitted for clarity) FIG. 3. For each m, an arrow → (←) pointing to the vertex
j ′ indicates that the basis state |+, j ′ i (|−, j ′ i) is present in
Y tmk rml  ∂ mk ∂ ml  
the expression for |ψ(m)i = U m |+, ji. The number of arrows
k l
P̂P · = ml · 
 . (5) of a given type equals the number of distinct paths leading to
mk ! ml ! ∂tmk ∂rl
k
k,l∈P rj ,tj =0,∀j the corresponding |ν, j ′ i.

In Eq. (5) the tk ’s and rl ’s are the scattering amplitudes

(appearing mk and ml times) characterizing the path as- (first step), and finally goes to j − 2 (second step), now
sociated to P [31]. heading left. Note that in terms of a quantum scattering
With this mathematical ‘machinery’, below we can (+)
process, it represents a reflection from the vertex j (rj )
make an analysis of sum over paths for QWs. (−)
and then a transmission through the vertex j − 1 (tj−1 ).
By applying Ŝm on G{ν,j ′ },{σ,j} and afterwards simply
III. RESULTS AND DISCUSSION (±) (±)
setting rj = tj = 1 ∀j, one directly finds that the
number of paths leading to {σ, j} → {ν, j ′ } after m steps
Suppose the initial state |ψ(0)i = |σ, ji, so we write is given by the binomial coefficient [39]
j ′ =j+m

m−1

m
U |ψ(0)i = |ψ(m)i = z m
X X
aν,j ′ |ν, j ′ i. (6) Nν,j ′ = m+j ′ −j . (8)
2 − δσν
j ′ =j−m ν=±
As a simple check, one can test Eq. (8) with the schemat-
Above, some a’s are zero since certain basis states are ics in Fig 3. Moreover, from the mapping between SQWs
absent, e.g., |−, j + m − 1i cannot be reached in m steps. and coined QWs in [35], the number of paths to a given
In fact, exactly 2m a’s are not null. j ′ state for the latter QW formulation is trivially derived
Next, to make contact with CRWs, we observe that by from Nν,j ′ as
leaving from the edge corresponding to {σ, j} there is a    
determined number of trajectories (eventually none) fi- X m m
Njcoined
′ = Nν,j ′ = m+j ′ −j = m−j ′ +j , (9)
nally getting to specific edges in exact m steps. Thus,
ν 2 2
the total number of paths ending up in any possible
|ν, j ′ i is 2m . Since p = |a|2 , the a’s can be given as the which agrees with the formula in Ref. [40] (with j = 0).
sum of the quantum amplitudes [38] of all paths yielding Assume any path taking, regardless the order, d(−)
{σ, j} → {ν, j ′ }. (d(+) ) steps to the left (right). It would lead the system
As an simple example, for |ψ(0)i = |+, ji the Fig. to |ν, j ′ = j + d(+) − d(−) i. Reversing this reasoning,
3 schematically illustrates the basis states expansion of consider a fixed m = d(+) +d(−) ≥ |∆j|, with ∆j = j ′ −j.
|ψ(m)i (up to m = 5). Consider m = 2, then Paths for which d(±) = (m ± ∆j)/2 are both integers will
result in j → j ′ . To obtain all such paths, we should
z −2 |ψ(2)i = z −2 U 2 |+, ji consider G for Jl = j − d(−) and Jr = j + d(+) . The
= a−,j−2 |−, j − 2i + a+,j |+, ji contribution from each path to a given coefficient in Eq.
+a−,j |−, ji + a+,j+2 |+, j + 2i. (7) (6) will involve exactly m position dependent amplitudes
(±) (±)
rj ’s and tj ’s. In this way, the actual procedure to
The presence of, say, |−, j − 2i in the expression for
|ψ(2)i, Eq. (7), is represented in the m = 2 case of calculate the a’s is to compute aν,j ′ = Ŝm G{ν,j ′ },{σ,j} , for
Fig. 3 by an arrow pointing to the vertex j − 2. More- Jl , Jr , d(±) as above.
(±) (±)
over, its number, here just a single arrow, means there is For complete arbitrary rj ’s and tj ’s and for m in
only one path getting to |−, j − 2i from |+, ji if m = 2: the hundreds, any available computer algebra system can
a trajectory which initially heading right at j (since be used to obtain the a’s as explained. Actually, vertex-
|ψ(0)i = |+, ji), reverses its direction at j, goes to j − 1 dependent quantum amplitudes can give rise to a great
 4

diversity of diffusive properties [41]. So, the present pro- 0.19 ν=+ (a)
cedure may be useful to test distinct QWs models trans-
(±) (±) 0
port features, helping to choose sets of rj ’s and tj ’s

-i φ
more appropriate in different applications (examples to -0.19

aν,j e
appear elsewhere).
0.12 ν=− (b)
However, a real surprise is for the situation when su-
perdiffusion takes place even for j independent quantum 0
amplitudes and when at each single step the QW resem-
-0.12
bles an unbiased classical walk (i.e., 50–50% probability
to go right-left) [2]. In the following, we show how in- -90 -60 -30 0 30 60 90
terference can fully explain this apparently non-intuitive j -j
100
behavior. 0.1
ν=+
(±) (±)
For rj = r(±) , tj = t(±) and from the above pre- 75 0.05
(c)
scription, we get (nsup = min{d(σ) − δσν , d(−σ) − 1}) 0
0.03 ν = −

∆
50 -50 0 50
n=nsup 0.015

d(σ)
 (−σ)
d −1
 25
X 0
aν,j ′ = fn Cn , fn = , -50 0 50
n + δσν n 0
n=−δσν 0 50 100 150 200
(σ)
m
Cn = [t(σ) ]d −n−δσν
[r(−σ) ]n+δσν
(−σ) FIG. 4. Up to a global phase, the dimensionless coefficient
×[t(−σ) ]d −n−1
[r(σ) ]n+1 . (10) aν,j ′ , Eq. (12), as function of the quantum number j ′ for
|ψ(0)i = |+, ji, m = 100, (a) ν = +, and (b) ν = −. Since m
Furthermore, using Eq. (2) is even, aν,j ′ = 0 if j ′ − j is odd. The notorious [2] amplitudes
 r 2n+δσν +1 asymmetry because the particular initial state arises only for
Cn = exp[iφ] tm (−1)n , (11) δσν = 1 (case (a)). (c) The linear dependence of the standard
t deviation ∆ on the discrete time m. In the insets |aν,j ′ |2
and the corresponding probabilities for an unbiased classical
with φ a global phase (unimportant here) which depends random walk (dashed curves) vs. j ′ − j.
(±)
on j, j ′ , σ, ν, m and φr,t . In Eq. (10), fn gives the
number of distinct paths yielding a same amplitude Cn
to the a’s. This is possible because different paths cor-
respond to a different order of scattering processes along changes and three have four (n = 1). The phases are
the lattice. Nevertheless, if the final set of scattering’s co- then, respectively, (−1)0 = 1 and (−1)1 = −1. Hence,
incides, the resulting amplitudes Cn are these two groups of paths suffer destructive interference.
P equal. The total
m−1

On the other hand, for j ′ = j + 3 there are four pos-
number of paths for aν,j ′ is Nν,j ′ = n fn = d(σ) −δσν , sible paths, all with two direction changes (n = 0) and
which agrees with Eq. (8).
thus with a same phase. The paths therefore build up a
Particularly important in Eq. (11) is the factor (−1)n ,
relatively high amplitude.
arising from the phases difference, Eq. (2), between re-
flections and transmissions in a trajectory. In fact, for The above results can also explain two typical and im-
each path the number of directions change along the way portant behaviors observed in QWs [2, 22] (see Fig. 4
is 2n + 1 + δσν . Therefore, distinct paths may contribute (a)-(c)): (i) for usual CRWs, the probabilities for the
with distinct signals (through (−1)n ) to the sum in Eq. particle location are√ Gaussian distributed, with a stan-
(10), leading to constructive or destructive interference. dard deviation of m (insets of Fig. 4 (c)). On the other
√ hand, quantum mechanically the |a|2 ’s, representing the
Lastly, in the “unbiased” case of r = t = 1/ 2, i.e.,
50%–50% reflection-transmission probability in each ver- particle distribution along the graph, are not spatially
tex (for a similar coined case see, e.g., [40]), Eq. (10) concentrated; (ii) aj ′ vs. j ′ presents stronger oscillations
reduces to for the j ′ ’s far away from the initial j, a pattern usually
without a classical analog.
aν,j ′ = exp[iφ] 2−m/2 {−2m δm d(σ) + [d(σ) ]δσν In fact, both (i) and (ii) originate from a similar mech-
×2 F1 (−d(σ) + δσν , −d(−σ) + 1; 1 + δσν ; −1)}, (12) anism. For a fixed large m, the number of trajecto-
ries Nν,j ′ leading to j ′ is large (small) if |∆j| is small
with 2 F1 the Gaussian hypergeometric function. To il- (large). In the classical case, since there are no interfer-
lustrate this formula, we consider the a’s for the final ence, the probabilities are directly proportional to Nν,j ′
states |+, j + 1i and |+, j + 3i in the case m = 5 of Fig. and the Gaussian distribution naturally emerges (recall
3 (thus δσν = 1). From Eq. (12) we get a+,j+1 = 0 and that binomial distributions, c.f. Eq. (8), converge to
|a+,j+3 |2 = 1/2. To understand why, note that from fn Gaussians). In the quantum case, the many cancella-
in Eq. (10) or by inspecting Fig. 3, we find there are tions coming from opposite signals for distinct groups of
six (four) possible paths leading to |+, j + 1i (|+, j + 3i). trajectories, Eq. (11), prevents the probabilities at |∆j|
For j ′ = j + 1, three paths have two (n = 0) direction small to be much higher than those at larger |∆j|, Fig. 4
 5

(a)-(b). Hence, a more balanced distribution among the sum over paths history – to study QWs in general. It
states j ′ ’s is obtained. By the same token, the smooth leads to some exact analytical results, which may be diffi-
(strong oscillatory) behavior for |∆j| small (large) is due cult to obtain by other means. Second, we properly quan-
to the fact that varying j ′ in such interval will propor- tify a fundamental characteristic of QWs, interference,
tionally cause a small (large) change in the number of explicit associating such phenomenon with the emergence
paths contributing to aj ′ . This results in a slow (rapid) of supperdiffusive behavior.
variation of a′j as function of j ′ .
Hence, the present framework provides a powerful tool
Thus, the observed system fast spreading, e.g., in the
to test distinct aspects of QWs evolution, and whose
unbiased case characterized by a linear dependence on
complete comprehension is certainly an important step
m forq the standard deviation (pj ′ = |a+,j ′ |2 + |a−,j ′ |2 ):
towards making QWs more reliable to distinct applica-
′ 2 ′ 2
P P
∆= j ′ (j − j) pj ′ − ( j ′ (j − j)pj ′ ) (Fig. 4 (c)); tions as in quantum computing.
is due to (i)-(ii). In their turn, (i)-(ii) are a direct conse-
quence of intricate interference effects among paths with
different phases.

ACKNOWLEDGMENTS
IV. CONCLUSION

Summarizing, our contribution here has been twofold. MGEL acknowledges a research grant from CNPq. Fi-
First, we propose a distinct approach – based on a true nancial support is also provided by Finep/CT-Infra.

[1] Y. Aharonov, L. Davidovich, and N. Zagury, Phys. Rev. [13] M. Mosca, in Quantum Algorithms, Encyclopedia of
A 48, 1687 (1993); D. A. Meyer, J. Stat. Phys. 85, 551 Complexity Systems Science, edited by R. A. Meyers
(1996); J. Watrous, J. Comp. Sys. Sci. 62, 376 (2001). (Springer, Heidelberg, 2009).
[2] J. Kempe, Contemp. Phys. 44, 307 (2003). [14] E. Farhi and S. Gutmann, Phys. Rev. A 58, 915 (1998).
[3] J. B. Wang and B. L. Douglas, in Frontiers of Fundamen- [15] A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann,
tal and Computational Physics, AIP Conference Proceed- and D. A. Spielman, in STOC’03: Proceedings of the
ings vol. 1246, edited by J. G. Hartnett and P. C. Abbott, 35th Annual ACM Symposium on Theory of Computing
(American Institute of Physics, College Park, 2010) pp. (ACM, New York, 2003), pp. 59–68; J. Kempe, Probab.
195-198. Theory Relat. Fields 133, 215 (2005).
[4] M. Karski, L. Forster, J. M. Choi, A. Steffen, W. Alt, D. [16] A. Kempf and R. Portugal, Phys. Rev. A 79, 052317
Meschede, and A. Widera, Science 325, 174 (2009). (2009).
[5] M. A. Broome, A. Fedrizzi, B. P. Lanyon, I. Kassal, A. [17] N. Shenvi, J. Kempe, and K. B. Whaley, Phys. Rev. A
Aspuru-Guzik, and A. G. White, Phys. Rev. Lett. 104, 67, 052307 (2003); A. Gabris, T. Kiss, and I. Jex, ibid.
153602 (2010). 76, 062315 (2007); D. Reitzner, M. Hillery, E. Feldman,
[6] M. Mohseni, P. Rebentrost, S. Loyd, and A. Aspuru- and V. Buzek, ibid. 79, 012323 (2009).
Guzik, J. Chem. Phys. 129, 174106 (2008); P. Reben- [18] T. Avatar, Phys. Rev. A 78, 012310 (2008); M. Hillery,
trost, M. Mohseni, I. Kassal, S. Loyd, and Aspuru-Guzik, D. Reitzner, and V. Buzek, ibid. 81, 062324 (2010); J.
New J. Phys. 11, 033003 (2009). Lee, H.-W. Lee, and M. Hillery, ibid. 83, 022318 (2011).
[7] C. M. Chandrashekar, Phys. Rev. A 83, 022320 (2011). [19] A. Wojcik, T. Luczak, P. Kurzynski, A. Grudka, and M.
[8] C. M. Chandrashekar and R. Laflamme, Phys. Rev. A Bednarska, Phys. Rev. Lett. 93, 180601 (2004); T. Oka,
78, 022314 (2008). N. Konno, R. Arita, and H. Aoki, ibid. 94, 100602 (2005).
[9] C. Ampadu, Commum. Theor. Phys. 57, 41 (2012). [20] D. Bouwmeester, I. Marzoli, G. P. Karman, W. Schleich,
[10] D. Aharonov, A. Ambainis, J. Kempe, and U. Vazirani, in and J. P. Woerdman, Phys. Rev. A 61, 013410 (1999); P.
STOC’01: Proceedings of the 33nd Annual ACM Sympo- L. Knight, E. Roldan, and J. E. Sipe, ibid. 68, 020301(R)
sium on Theory of Computing (ACM, New York, 2001), (2003).
pp. 37–49; A. Ambainis, E. Bach, A. Nayak, A. Vish- [21] P. P. Rohde, A. Schreiber, M. Stefanak, I. Jex, and C.
wanath, and J. Watrous, in STOC’01: Proceedings of the Silberhorn, New J. Phys. 13, 013001 (2011).
33nd Annual ACM Symposium on Theory of Computing [22] V. M. Kendon, Philos. Trans. Roy. Soc. A 364, 1849
(ACM, New York, 2001), pp. 50–59. (2006).
[11] A. M. Childs, Phys. Rev. Lett. 102, 180501 (2009); N. [23] O. Muelken and A. Blumen, Phys. Rep. 502, 37 (2001).
B. Lovett, S. Cooper, M. Everitt, M. Trevers, and V. [24] Y. Ide, N. Konno, T. Machida, and E. Segawa, Quant.
Kendon, Phys. Rev. A 81, 042330 (2010). Inf. Comput. 11, 855 (2011).
[12] A. Ambainis, in SOFSEM 2008: Theory and Practice [25] T. D. Mackay, S. D. Bartlett, L. T. Stephenson, and B. C.
of Computer Science, edited by V. Geffert, J. Karhu- Sanders, J. Phys. A 35, 2745 (2002); N. Konno, Fluct.
maki, A. Bertoni, B. Preneel, P. Navrat, and M. Bielikova Noise Lett. 5, 529 (2005); J. Kosik, V. Buzek, and M.
(Springer, Berlin, 2008), pp. 1–4. Hillery, Phys. Rev. A 74, 022310 (2006).
[26] V. Kendon, Math. Struc. Comput. Sci. 17, 1169 (2007)
 6

[27] R. A. Brun, H. A. Carteret, A. Ambainis, Phys. Rev. [35] F. M. Andrade and M. G. E. da Luz, Phys. Rev. A 80,
Lett. 91, 130602 (2003). 052301 (2009).
[28] A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, and [36] A. G. Schmidt, B. K. Cheng, and M. G. E. da Luz, Phys.
J. Watrous, in STOC’01: Proceedings of the thirty-third Rev. A 66, 062712 (2002).
annual ACM symposium on Theory of computing (ACM, [37] M. G. E. da Luz, B. K. Cheng, E. J. Heller, J. Phys. A
New York, 2001) p. 37; W.-S. Yang, C. Liu, and K. 31, 2975 (1998).
Zhang, J. Phys. A 40, 8487 (2007); Y. Ide, N. Konno, [38] Ps.p. = Ws.p. exp[iSs.p. ], with S = mγ the path ac-
T. Machida, and E. Segawa, Quant. Inf. Comput. 11, tion and W the product of the corresponding coefficients
761 (2011). gained by scattering
off at the vertices along the way [31].
[29] H. A. Carteret, B. Richmond, and N. M. Temme, J. Phys. [39] For k an integer, nk is given by Maarten J. Kronenburg
A 38, 8641 (2005); N. Konno, Quant. Inf. Comput. 9, 405 in arXiv:1105.3689v1 as: (i) for n any nonnegative in-
(2010). teger, n!/(k!(n − k)!) if 0 ≤ k ≤ n and zero
otherwise;
[30] R. P. Feynman and A. R. Hibbs, Quantum Mechanics (ii) for n any negative integer, (−1)k −n+k−1k
if k ≥ 0,
and Path Integrals (McGraw-Hill, New York, 1965). (−1)n−k −k−1


n−k
if k ≤ n, and zero otherwise.
[31] F. M. Andrade and M. G. E. da Luz, Phys. Rev. A 84, [40] T. A. Brun, H. A Carteret, A. Ambainis, Phys. Rev. A
042343 (2011). 67, 052317 (2003).
[32] B. Tregenna, W. Flanagan, R. Maile, and V. Kendon, [41] P. Ribeiro, P. Milman, and R. Mosseri, Phys. Rev. Lett.
New J. Phys. 5, 83 (2003). 93, 190503 (2004); A. Romanelli, R. Siri, V. Micen-
[33] M. Hillery, J. Bergou, and E. Feldman, Phys. Rev. A 68, macher, Phys. Rev. E 76, 037202 (2007); A. Schreiber,
032314 (2003); E. Feldman and M. Hillery, J. Phys. A K. N. Cassemiro, V. Potocek, A. Gabris, I. Jex, and Ch.
40, 11343 (2007). Silberhorn, Phys. Rev. Lett. 106, 180403 (2011).
[34] F. W. Strauch, Phys. Rev. A 74, 030301(R) (2006); A.
M. Childs, Commun. Math. Phys. 294, 581 (2010).