数理解析研究所講究録
第 1837 巻 2013 年 21-28

21

Relationship between quantum walks and differential
equationsTakuya Machida

Abstract The limit theorems of discrete- and continuous-time quantum walks
on the line have been intensively studied. We show a relation among limit
distributions of quantum walks, Heun differential equations and Gauss differential equations. Indeed, we derive the second-order Fucksian differential
equations which limit density functions of quantum walks satisfy. Moreover,using both differential equations, we discuss a relationship between discreteand continuous-time quantum walks. Taking suitable limit, we can transforma Heun equation obtained from the limit density function of the discrete-timequantum walk to a Gauss equation given by that of the continuous-time quantum walk. This work is collaboration with Norio Konno and Tohru Wakasa.

1 Introduction

The discrete-time quantum walk ( $QW$ ), which is a quantum counterpart ofthe classical random walk, has been extensively investigated since Ambainis
et al. [2] studied a detail of the walk. The continuous-time $QW$ was proposedby Farhi and Gutmann [5], and has been analyzed on not only regular graphs
but also complex networks (e.g. [8, 19, 25]). further development in the theoryof the $QW$ during recent 10 years showed us several novel properties on both
QWs. The behavior of the $QW$ is quite different from that of the random
walk and is expected to be connected with various phenomena in quantum
mechanics. relation between the $QW$ and quantum computer has been also
discussed (e.g. [1, 20, 22]). The quantum search algorithm designed by the $QW$
is one of the important applications. The Grover search algorithm can be
$A$

$A$

Acknowledgements The author is grateful to Norio Konno and Tohru Wakasa for usefulcomment and also to the Meiji University Global $COE$ Program “Formation and Development of Mathematical Sciences Based on Modeling and Analysis” for the support.

22
considered as a discrete-time $QW$ on the complete graph and it produces
speed-up at the square-root rate for the corresponding classical search. There
are some reviews of the $QW$ [10, 11, 15,24].
One of the purposes in the study of the $QW$ is to derive the limit distribution and the asymptotic behavior as time tends to infinity. The limit
distribution has been obtained for various kinds of QWs. In the present paper,
we concentrate on the $QW$ in the one-dimensional space. Observing previous
results, one can mention that each limit distribution usually has a compact
support and admits a singularity at the boundary of the support. This is aninteresting property of the limit distribution, because the $QW$ does not possess any singularity in space. To the fact, we now address a question: How tounderstand the singularity of the $QW$ ? Motivated by this question, we investigate the limit distribution of the $QW$ from a viewpoint of the differential
equation.
We begin with finding a differential equation for the limit distribution.
For example, consider discrete- and continuous-time symmetric simple random
walks on the line. The central limit theorem for the walk, that is,denotes the walker’s posi, is well-known, wherexis the probability that the walker is at position
tion at time andat time . For the limit density function $f(x)=e^{-x^{2}/2}/\sqrt{2\pi}$ , an equation$d^{2}f(x)/dx^{2}+xdf(x)/dx+f(x)=0$ is derived. This equation comes from the, and in partheory of the diffusion equation
ticular, it is also obtained by the self-similarity of the fundamental solution$u(x, t)=(1/\sqrt{t})f(x/\sqrt{t})$ .
Let us consider both discrete-time and continuous-time QWs on the line.
The classical random walk corresponds to the diffusion process, while for the$QW$ the corresponding process is not known. Thus, to find out the process
would remain as one of important problems. Taking an account of the singularity in the limit distribution, we treat a class of Fucksian linear differential
equations of the second order. For discrete-time (resp. continuous-time) QWs,
we are led to a Heun’s differential equation ( $HE$ ) (resp. a hypergeometric differential equation by Gauss (the Gauss equation, $GE$ ) . The $GE$ is one of
typical Fucksian equations and represents the Fucksian equations with exactly
three regular singular points. On the other hand, the $HE$ was proposed in 1888
by Heun [7] and admits four regular singular points.
Moreover, a concept of confluence between the $HE$ and the $GE$ helps us tounderstand a relationship between discrete,-and continuous-time QWs clearly.
Through these results, authors believe that the $HE$ and the $GE$ play an important role in understanding the QWs.
The present paper is organized as follows. In Sect. 2, we explain both the
one-dimensional discrete-time $QW$ and the $HE$ . After introducing the limit
distribution obtained by Konno [12, 14], we discuss a relation between thediscrete-time $QW$ and the $HE$ . In Sect. 3, we concentrate on the continuoustime $QW$ , and show that the $GE$ relates with the limit density function of
the walk. Section 4 is devoted to a connection between the $HE$ and the $GE$$\lim_{tarrow\infty}\mathbb{P}(Y_{t}/\sqrt{t}\leq$$)$$= \int_{-\infty}^{x}e^{-y^{2}/2}/\sqrt{2\pi}dy$

$t$

$x$

$Y_{t}$$\mathbb{P}(Y_{t}=x)$$t$$\partial u(x, t)/\partial t=\frac{1}{2}\partial^{2}u(x, t)/\partial x^{2}$

$)$

23
in order to understand a relationship between discrete- and continuous-time
QWs given by Strauch [23].

2 $A$ relation between the discrete-time $QW$ and the $HE$
In this section, we discuss a relation between the discrete-time $QW$ in one
dimension and the $HE$ . At first we define the $QW$ on the line. Let$\{0, \pm 1, \pm 2, \ldots\})$ be infinite components vectors which denote the position of
the walker. Here, x-th component ofis 1 and the other is . Let
be the amplitude of the walker at position at time $t\in\{0,1,2, \ldots\}$ , whereis the set of complex numbers. The amplitude of the walk at time is expressedby(1).
$|x\rangle(x\in \mathbb{Z}=$$0$$|x\rangle$$|\psi_{t}(x)\rangle\in \mathbb{C}^{2}$$\mathbb{C}$

$x$

$t$

$| \Psi_{t}\rangle=\sum_{x\in \mathbb{Z}}|x\rangle\otimes|\psi_{t}(x)\rangle$

The time evolution of the walk can be defined by the following unitary matrix:$U=\{\begin{array}{l}bacd\end{array}\}$where$a,$ $b,$ $c,$$d\in \mathbb{C}$(2),. Moreover, we introduce two matrices:(3)$P=\{\begin{array}{l}ba00\end{array}\}, Q=\{\begin{array}{l}00dc\end{array}\}$Note that $P+Q=U$ . Then the evolution is determined by$|\psi_{t+1}(x)\rangle=P|\psi_{t}(x+1)\rangle+Q|\psi_{t}(x-1)\rangle$

The probability that the discrete-time quantum walker
at time, is defined by$t,$.

$X_{t}^{(d)}$(4)

is at position$x$$\mathbb{P}(X_{t}^{(d)}=x)$$\mathbb{P}(X_{t}^{(d)}=x)=\langle\psi_{t}(x)|\psi_{t}(x)\rangle$

wheredenotes the conjugate transposed vector of
paper, we take the initial state as$\langle\psi_{t}(x)|$(5),$|\psi_{t}(x)\rangle$. In the present(6)$|\psi_{0}(x)\rangle=\{\begin{array}{l}\tau[1/\sqrt{2}, i/\sqrt{2}](x=0) ,\tau[0,0] (x\neq 0) ,\end{array}$where is the transposed operator. Equation (6) is well-known as the initialstate that gives the symmetric probability distribution about the origin [15].
For the walk, some limit theorems and asymptotic behaviors have beenobtained. In particular, we focus on the density function of probability distribution as $tarrow\infty$ . The limit distribution of the $QW$ was given by Konno [12,14]. That is, for $abcd\neq 0$ , we have$T$$\lim_{tarrow\infty}\mathbb{P}(\frac{X_{t}^{(d)}}{t}\leq x)=\int_{-\infty}^{x}f^{(d)}(y)I_{(-|a|,|a|)}(y)dy$

,

(7)

24
where
$f^{(d)}(x)= \frac{\sqrt{1-|a|^{2}}}{\pi(1-x^{2})\sqrt{|a|^{2}-x^{2}}}$(8),

lot of limit distribuand $I_{A}(x)=1$ if $x\in A,$ $I_{A}(x)=0$ if $x\not\in A.$
tions of discrete-time QWs are often described by using this function $f^{(d)}(x)$(e.g. [3,9,16-18,21]). Figure 1 depicts the comparison between the probability distribution at time 500 and the limit density function for the walk with
$a=b=c=-d=1/\sqrt{2}$ , which is called the Hadamard walk.
$A$

1

$0$

$-|u|$

$x$

$x$

(a)

(b)

$|u|$

1

Fig. 1 Comparison between the probability distribution and the limit density function of
the discrete-time $QW$ with $a=b=c=-d=1/\sqrt{2}$ . Figure (a) is the probability distribution
at time $t=500$ . Figure (b) is the limit density function of the walk.

From now, we discuss a relation between the limit density function $f^{(d)}(x)$and the $HE$ . The canonical form of the $HE$ is given by,$\frac{d^{2}u}{dz^{2}}+(\frac{\gamma}{z}+\frac{\delta}{z-1}+\frac{\epsilon}{z-\theta})\frac{du}{dz}+\frac{\alpha\beta z-q}{z(z-1)(z-\theta)}u=0$(9). The fivewhere
is one of the singular points and$\alpha+\beta+1=\gamma+\delta+\epsilon$ andrelationbytheparameters
are linked
the parameter is called the accessory parameter. The $HE$ has four regular. Particularly the $HE$ with $\gamma=\delta=\epsilon=1/2$ issingularities at $z=0,1,$
called Lam\’e’s equation and it have been analyzed in detail. In some special
cases, the $HE$ becomes the $GE(e.g. \theta=1, q=\alpha\beta case)$ .
We find that $f^{(d)}(x)$ satisfies the following differential equation:$\theta\in \mathbb{C}$$\alpha,$$\alpha,$$\beta,$$\gamma,$$\delta,$$\beta,$$\gamma,$$\delta,$$\epsilon,$$q\in \mathbb{C}$$\epsilon$$q$$\theta,$$\infty$$(1-x^{2})(|a|^{2}-x^{2}) \frac{d^{2}}{dx^{2}}f^{(d)}(x)-x(4|a|^{2}+3-7x^{2})\frac{d}{dx}f^{(d)}(x)$$+(9x^{2}-2|a|^{2}-1)f^{(d)}(x)=0$ .

(10)

By a change of an independent variable $x^{2}=z$ , we obtain one of our main
results:

25
Theorem 1$\frac{d^{2}}{dz^{2}}u^{(d)}(z)+(\frac{\frac{1}{2}}{z}+\frac{2}{z-1}+\frac{\frac{3}{2}}{z-|a|^{2}})\frac{d}{dz}u^{(d)}(z)$$+ \frac{\frac{9}{4}z-\frac{2|a|^{2}+1}{4}}{z(z-1)(z-|a|^{2})}u^{(d)}(z)=0$

,

(11)

where
$u^{(d)}(z)= \frac{\sqrt{1-|a|^{2}}}{\pi(1-z)\sqrt{|a|^{2}-z}}$

(12)

.

We should remark that Eq. (11) is equivalent to the $HE$ with$\alpha=\beta=\frac{3}{2}, \gamma=\frac{1}{2}, \delta=2, \epsilon=\frac{3}{2}, q=\frac{2|a|^{2}+1}{4}, \theta=|a|^{2}$(13)

3 $A$ relation between the continuous-time $QW$ and the $GE$

In this section we will show a relationship between the continuous-time $QW$
on and the $GE$ :$\mathbb{Z}$(14)$z(z-1) \frac{d^{2}u}{dz^{2}}+\{(\alpha+\beta+1)z-\gamma\}\frac{du}{dz}+\alpha\beta u=0$

where$\alpha,$$\beta,$$\gamma\in \mathbb{C}$are parameters. Equation (14) is a second-order Fucksian

equation with three regular singularities at $z=0,1,$
We give a definition of the continuous-time $QW$ on the line. At first, weconsider the amplitude
at time $t(>0)$ insteadat positionoffor the discrete-time $QW$ . The evolution of the amplitude isdefined by$\infty.$$\psi_{t}(x)\in \mathbb{C}$$x\in \mathbb{Z}$$|\psi_{t}(x)\rangle\in \mathbb{C}^{2}$$i \frac{d\psi_{t}(x)}{dt}=-\nu\{\psi_{t}(x-1)-2\psi_{t}(x)+\psi_{t}(x+1)\}$

(15)

,

where $\nu>0$ . The probability that the walker is at position at time isdenoted by $\mathbb{P}(X_{t}^{(c)}=x)=|\psi_{t}(x)|^{2}$ , whereis the continuous-time quantum walker’s position at time . We take an initial state as $\psi_{0}(0)=1$ and$\psi_{0}(x)=0(x\neq 0)$ . Konno [13] and Gottlieb [6] got the limit theorem for thecontinuous-time $QW$ as follows:
$x$

$t$

$X_{t}^{(c)}$$t$$\lim_{tarrow\infty}\mathbb{P}(\frac{X_{t}^{(c)}}{t}\leq x)=\int_{-\infty}^{x}f^{(c)}(y)I_{(-2\nu,2\nu)}(y)dy$

,

(16)

where
$f^{(c)}(x)= \frac{1}{\pi\sqrt{(2\nu)^{2}-x^{2}}}$

.

(17)

In Fig. 2, we show the comparison between the probability distribution at time
500 and the limit density function for the walk with $\nu=1/2\sqrt{2}.$

26

$x$

$x$

(b)

(a)

Fig. 2 Comparison between the probability distribution and the limit density function of
the continuous-time $QW$ with $\nu=1/2\sqrt{2}$ . Figure (a) is the probability distribution at time
$t=500$ . Figure (b) is the limit density function of the walk.

We see that the function $f^{(c)}(x)$ satisfies the following differential equation:$(4 \nu^{2}-x^{2})\frac{d^{2}}{dx^{2}}f^{(c)}(x)-3x\frac{d}{dx}f^{(c)}(x)-f^{(c)}(x)=0$

.

(18)

By the change of an independent variable $x^{2}/4\nu^{2}=z$ , we have a continuoustime counterpart of Theorem 1:

Theorem 2,$z(z-1) \frac{d^{2}}{dz^{2}}u^{(c)}(z)+(2z-\frac{1}{2})\frac{d}{dz}u^{(c)}(z)+\frac{1}{4}u^{(c)}(z)=0$

(19)

where
$u^{(c)}(z)= \frac{1}{2\nu\pi\sqrt{1-z}}$

.

(20)

Note that Eq. (19) is the $GE$ with $\alpha=\beta=\gamma=1/2.$

4 $A$ relation between discrete-time and continuous-time QWs in
the theory of the differential equation
In this section, we discuss a relation between discrete- and continuous-time
QWs on the second-order differential equations which were obtained in previous sections. Strauch [23] found a relation between both walks by transforming
Eq. (4) to Eq. (15) in a suitable limit. ’Alessandro [4] focused on both QWs
on general graphs and derived the dynamics of continuous-time walks as alimit of discrete-time dynamics.
Considering a confluent type for the $HE$ which the function $u^{(d)}(z)$ satisfies,
we can also obtain the $GE$ which the function $u^{(c)}(z)$ satisfies. For a scaling$D$27
parameter , substituting $z=t/\tau$ in Eq. (11), we have$\tau$$4t(|a|^{2} \tau-t)(1-\frac{t}{\tau})\frac{d^{2}}{dt^{2}}v(t)+2\{\frac{8t^{2}}{\tau}-(5|a|^{2}+4)t+|a|^{2}\tau\}\frac{d}{dt}v(t)$$+( \frac{9t}{\mathcal{T}}-2|a|^{2}-1)v(t)=0$

with $v(t)=u^{(d)}(t/\tau)$ . As
obtain a confluent $HE$ :$\tauarrow\infty,$$|a|arrow 0$

under the condition.

$t(t-1) \frac{d^{2}v}{dt^{2}}+(2t-\frac{1}{2})\frac{dv}{dt}+\frac{1}{4}v=0$,$|a|^{2}\tauarrow 1$

(21)

, we

(22)

Equation (22) is equivalent to the $GE$ which was obtained from the continuoustime $QW$ (see Eq. (19)). This result corresponds to the result in Strauch [23].
We can confirm his result in a relation between the $HE$ and the $GE.$

References
1. Ambainis, A.: Quantum walks and their algolismic applications. International Journalof Quantum Imformation 1, 507-518 (2003)
2. Ambainis, A., Bach, E., Nayak, A., Vishwanath, A., Watrous, J.: One-dimensional
quantum walks. Proceedings of the thirty-third annual ACM symposium on Theory ofcomputing, 37-49 (2001)
3. Chisaki, K., Hamada, M., Konno, N., Segawa, E.: Limit theorems for discrete-timequantum walks on trees. Interdisciplinary Information Sciences 15, 423-429 (2009)
4. D’Alessandro, D.: Connection between continuous and discrete time quantum walks on-dimensional lattices; extensions to general graphs. arXiv:0902.3496, (2009)
5. Farhi, E., Gatmann, S.: Quantum computation and decision trees. Phys. Rev. A 58,
915 (199S)
6. Gottlieb, A.D.: Convergence of continuous-time quantum walks on the line. Phys. Rev.
E72, 047102 (2005)
7. Heun, K.: Zur theorie der riemann’schen functionen zweiter ordnung mit vier verzweigungspunkten. Mathematische Annalen 33, 161-179 (1888)
8. Ide, Y., Konno, N.: Continuous-time quantum walks on the threshold network model.
Mathematical Structures in Computer Science 20, 1079-1090 (2010)
9. Inui, N., Konno, N., Segawa, E.: One-dimensional three-state quantum walk. Phys.
Rev. E72, 056112 (2005)
10. Kempe, J.: Quantum random walks– an introductory overview. Contemporary Physics
44, 307-327 (2003)
11. Kendon, V.: Decoherence in quantum walks –a review. Mathematical Structures in
Computer Science 17, 1169-1220 (2007)
12. Konno, N.: Quantum random walks in one dimension. Quantum Information Processing
1, 345-354 (2002)
13. Konno, N.: Limit theorem for continuous-time quantum walk on the line. Phys. Rev.
E72, 026113 (2005)
14. Konno, N.: A new type of limit theorems for the one-dimensional quantum random
walk. Journal of the Mathematical Society of Japan 57, 1179-1195 (2005)
15. Konno, N.: Quantum Walks. Volume 1954 of Lecture Notes in Mathematics. Springer$d$

Verlag, (Heidelberg) (2008) 309-452
16. Konno, N., Machida, T.: Limit theorems for quantum walks with memory. Quantum
Information and Computation 10, 1004-1017 (2010)

28
17. Machida, T., Konno, N.: Limit theorem for a time-dependent coined quantum walk on
the line. F. Peper et al. (Eds.): IWNC 2009, Proceedings in Information and Communications Technology 2, 226-235 (2010)
18. Machida, T.: Limit theorems for a localization model of 2-state quantum walks. International Journal of Quantum Information 9, 863-874 (2011)
19. M\"ulken, O., Pernice, V., Blumen, A.: Quantum transport on small-world networks:
continuous-time quantum walk approach. Phys. Rev. E76, 051125 (2007)
20. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press (2000)
21. Segawa, E., Konno, N.: Limit theorems for quantum walks driven by many coins.
International Journal of Quantum Information 6, 1231-1243 (2008)
22. Shenvi, N., Kempe, J., Whaley, K.B.: Quantum random-walk search algorithm. Phys.
Rev. A 67, 052307 (2003)
23. Strauch, F.W.: Connecting the discrete- and continuous-time quantum walks. Phys.
Rev. A 74, 030301 (2006)
24. Venegas-Andreca, S.E.: Quantum Walks for Computer Scientists. Morgan & Claypool
Publishers (2008)
X.P., Liu, F.: Continuous-time quantum walks on Erd\’os-R\’enyi networks. Physics
Xu,
25.
Letters A 372, 6727-6732 (2008)$A$

T.M.: Meiji Institute for Advanced Study of Mathematical Sciences, Meiji
University, Tama, Kawasaki 214-8571, Japan, $E-$-mail: bunchin@meiji.ac.jp