数理解析研究所講究録 1422 巻 2005 年 1-11

1

Relation between coined quantum walks andquantum cellular automata

横浜国立大学・応用数学

濱田 昌寿 (Masatoshi Hamada),
今野紀雄 (Norio Konno),
瀬川悦生 (Etsuo Segawa)

Department of Applied Mathematics,
Yokohama National University

1

Introduction

Very recently Patel et al. [1] constructed a quantum walk (QW) on a line
without using a coin toss instruction, and analyzed the asymptotic behaviorof the walk on the line and its escape probability with an absorbing wall. In
fact the QW investigated by them can be considered as a class of quantum
cellular automata on the line (see [2, 3, 4], for examples), so we call their
non-coined QW a quantum cellular automaton (QCA) in this paper. On theother hand, a usual QW with a coin toss instruction was introduced andintensively studied by Ambainis et al. [5], (see Refs. [6, 7, 8] for reviews of). Here we call the QW a coined $QW$. At a first glance, the QCA looksthe. However, we show that there exists a one-todifferent from the coined
one correspondence between them in a more general setting. The purpose of
the present paper is to clarify this connection. Once the connection is wellunderstood, the result by Patel et al. [1] is straightforwardly obtained.
The rest of this paper is organized as follows. Section 2 is devoted tothe definition of the QCA. In Section 3, the definitions of A-type and B-type
QWs are presented. In Section 4 (resp. 5), we describe a connection between. Section 6 gives a relation between
QCAs and A-type (resp. -type). Finally, we discuss the case given by Patel
QCAs and two-step coined
et al. [1].
$\mathrm{Q}\mathrm{W}$$\mathrm{Q}\mathrm{W}$$\mathrm{B}$$\mathrm{Q}\mathrm{W}\mathrm{s}$$\mathrm{Q}\mathrm{W}\mathrm{s}$2Definition of QCA

2) denote the set of (resp, non-negative) integers and’
(resp.
Let
indicate the collection of complex numbers. We define the dynamics of a onedimensional QCA including the model investigated by Patel et al. [1]. (Asfor recent reviews on QCAs, see Aoun and Tarifi [9], Schumacher and Werner[10].) Let
be the amplitude of the QCA at timeand at$=1$ and$=0$ if, that is,starting fromlocation$k\neq m$ . Moreover, let$\mathrm{Z}$$\mathrm{C}$$\mathrm{Z}_{+}$$\eta_{k}^{(m)}(n)(\in \mathrm{C})$$n\in \mathrm{Z}_{+}$$\eta_{m}^{(m)}(0)$$m\in \mathrm{Z}$$k\in \mathrm{Z}$$\eta_{k}^{(m)}(0)$$x_{k}^{(m:\pm)}(n)=|\alpha\eta_{k}^{(m)}(n)+\beta\eta_{k}^{(m\pm 1)}(n)|^{2}$and$x^{(m:\pm)}(n)=(x_{k}^{(m:\pm)}(n) :where ,

k\in \mathrm{Z})$with. As we will show later, theisequivalent to a probability distribution of a coined QW at time , where apaircorresponds to an initial qubit state of the. The evolution of
the QCA on the line is given by$\alpha$$|\alpha|^{2}+|\beta|^{2}=1$$\beta\in \mathrm{C}$$x_{k}^{(m:\pm)}(n)$$n$$(\alpha, \beta)$$\mathrm{Q}\mathrm{W}$$\eta^{(m)}(n+1)=\overline{U}\eta^{(m)}(n)$where$\overline{U}$is the unitary matrix.

$\overline{U}=$-3 -2 -1

$+2$

$+3$

$000da0bc$$c$$d\in \mathrm{C}$and$\eta^{(m)}(n)$$000adc0b$$0da000\mathrm{c}b$$0c\mathrm{a}db000$$ad000b00$, . . .)

indicates the transposed operator. Let $||u||=$. The unitarity of ensures that if $||\eta^{(m)}(0)||=1$ , then $||\eta^{(m)}(n)||=$$n\in \mathrm{Z}_{+}$$\sum_{k=-\infty}^{\infty}|u_{k}|^{2}$, here$a0cb\mathrm{O}000$

is the configuration$\eta^{(m)}(n)={}^{t}(\ldots, \eta_{-1}^{(m)}(n)\dot{\prime}\eta_{0}^{(m)}(n),$ $\eta_{+1}^{(m)}(n)$for any$+4$$.\cdot.\cdot.\cdots\ovalbox{\tt\small REJECT}$$0000d0ab$with , , ,
$b$

$+1$

$..\cdot.\cdot.+4+3+2+1-2-1-30\ovalbox{\tt\small REJECT}.\cdot.\cdot.\cdot.\cdot.\cdot..\cdot.\cdot.\cdot.\cdot.\cdot..\cdot.\cdot..\cdot..\cdot$$00000abc$

$a$

0

$t$

$\overline{U}$3. Furthermore, if $||x^{(m:\pm)}(0)||=1$ , then $||x^{(m:\pm)}(n)||=1$ for
1 for any n. A little algebra reveals that is unitary if and only if
any n$\in \mathrm{Z}_{+}$$\overline{U}$$\in \mathrm{Z}_{+}$$|a|^{2}+|b|^{2}+|c|^{2}+|d|^{2}=1$$a\overline{d}+\overline{a}d+b\overline{c}+\overline{b}c=0$$a\overline{c}+b\overline{d}=0$$a\overline{b}+\overline{a}b=0$

(1)
(2)
(3)
(4)
(5)

,

,

,
,

$c\overline{d}+\overline{c}d=0$where is a complex conjugate of $z\in$ C. Here we consider , , , satisfying”
Eqs. (1) (5). Trivial cases are “ $|a|=1$ , $b=c=d=0”$ , $|b|=1$ , $a=c=$
For other$d=0”$ , $‘ t|c|=1$ , $a=b=d=0”$ , and “ $|d|=1$ , $a=b=c=0$
cases, we have the following five types:, $bc\neq 0$ , $a=d=0$ .
Type, $ab\neq 0$ , $c=d=0$ .
,Type, $cd\neq 0$ , $a=b=0$ .
Type III: $|c|^{2}+|d|^{2}=1$ ,$a$$\overline{z}$

$b$

$c$

$d$

-

”

$\mathrm{I}:|b|^{2}+|c|^{2}=1_{\mathrm{J}}b\overline{c}+\overline{b}c=0$$\mathrm{I}\mathrm{I}:|a|^{2}+|b|^{2}=1$$a\overline{b}+\overline{a}b=0$$c\overline{d}+\overline{c}d=0$

Type
Type

, $ad\neq 0,$ $b=c=0$ .
satisfying Eqs. (1) (5) and $abcd\neq 0$ .

$\mathrm{I}\mathrm{V}:|a|^{2}+|d|^{2}=1,$$\mathrm{V}:a_{1}b$

, ,
$c$

$d$

Let
seen that for any$a\overline{d}+\overline{a}d=0$-$\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}[x^{(m:\pm)}(n)]=\{k\in \mathrm{Z} :x_{k}^{(m:\pm)}(n)>0\}$. Then, it is easily

in Type , andin Type . So both Types I and II are also
, we introduce a coined
trivial cases. To investigate non-trivial Types III
QW in the next section.
We see that a direct computation implies that $(a, b, c, d)$ satisfying Eqs.
(1) (5) has the following form:$n\in \mathrm{Z}_{+}$,$\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}[x^{(0:\pm)}(n)]\subseteq\{-2, -1,0, 1\}$$\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}[x^{(0:\pm)}(n)]\subseteq\{-1,0_{7}1,2\}$$\mathrm{I}$$\mathrm{I}\mathrm{I}$-$\mathrm{V}$-(a, b,-i$\mathrm{C}_{\}}d)=e^{i\delta}(\cos\theta\cos\phi,$$\cos\theta\sin\phi, \sin\theta\sin\phi, \mathrm{i}\sin\theta\cos\phi)$(6)$\in[0,2\pi)$ . From now on, we assume that $(a, b, c, d)$ has thewhere ,
above form. Remark that the case studied by Patel et at is $\delta=\pi/2$ and$-1/2)$ , which belongs to$=\pi/4$ , that is, $(a, b, c, d)=$Type V.
$\theta$$\phi,$$\delta$$\mathrm{i}/2,$$\theta=\phi$3$\mathrm{i}/2,$$\mathrm{i}/2,$

Definition of coined QW

The time evolution of one-dimensional both A-type and -type coined QWs
is given by the following unitary matrix:$\mathrm{B}$U$=(\begin{array}{l}a’c’\end{array}$

,

$db’$

$)$

4
where

$a’$

, , ,
,
$b’$

$c’$

$d’\in \mathrm{C}$. So we have $|a’|^{2}+|b’|^{2}=|c’|^{2}+|d’|^{2}=1$ ,where Is $=\det U=a’d’-b’c’$ with$={}^{t}(0,1)$ . For an A-type coined$={}^{t}(1,0)$ andLetperforms the evolution:$0$,$c’=-\triangle\overline{b’}$$a’\overline{c’}+b’\overline{d’}=$$|\triangle|=1$$d’=\triangle\overline{a’}_{2}$$|R\rangle$$|L\rangle$$|L\rangle$$arrow$$U|L)=a’|L\rangle+c’|R\rangle$$|R\rangle$$arrow$$U|R\rangle=b’|L)+d’|R\rangle$$\mathrm{Q}\mathrm{W}$.

, each coin,at each time step for which that coin is active, where and can be respectively thought of as the head and tail 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 coin shows , the particle
moves one unit to the left, when it shows , it moves one unit to the right.
Then a -type coined QW is also defined in a similar way as we will statelater. Thus the coined QW can be considered as a quantum version of a classical random walk with an additional degree of freedom called the chirality
which takes values left and right.
The amplitude of the location of the particle is defined by a 2-vector
at each location at any time . The probability that the particle is at
location is given by the square of the modulus of the vector at . For the-type coined QW $(j=A, B)$ , letdenote the amplitude at time
at location where
$R$

$L$

$L$

$R$

$\mathrm{B}$$\in \mathrm{C}^{2}$

$n$

$k$

$\mathrm{k}$$|\Psi_{j,k}(n))$

$j$

$n$

$k$

$|\Psi_{j,k}(n)\rangle=(\psi_{j,k}^{R}(n)\psi_{j,k}^{L}(n))$

with the chirality being left (upper component) or right (lower component).
For each $=A$ and , the dynamics offor the -type coined
QW starting from the origin with an initial qubit state, (where,), is presented as the following transformation:
and
$J|$

$B$

$j$

$|\Psi_{j,k}(n)\rangle$$\varphi={}^{t}(\alpha, \beta)$$\alpha$$\beta\in \mathrm{C}$$|\alpha|^{2}+|\beta|^{2}=1$$|\Psi_{j,k}(n+1)\rangle=P_{j}|\Psi_{j,k+1}(n)\rangle+Q_{j}|\Psi_{j,k-1}(n)\rangle$

where$Q_{A}=(\begin{array}{ll}0 0c d’\end{array})$$P_{A}=(\begin{array}{ll}a’ b’0 0\end{array})$$)$

and$P_{B}=(\begin{array}{ll}a’ 0c’ \mathrm{O}\end{array})$,$Q_{B}=(\begin{array}{ll}0 b’0 d’\end{array})$

(7)

...

5

It is noted that $U=P_{j}+Q_{j}(j=A, B)$ . The unitarity of ensures that theamplitude always defines a probability distribution for the location. From
Eq. (7), we see that a unitary matrix of the system is described as
$U$

.

.

.

$Q_{j}OOOO..\cdot.\cdot$$Q_{j}P_{j}OOO..\cdot.\cdot$$Q_{j}P_{j}OOO..\cdot.\cdot$.

.

$\ovalbox{\tt\small REJECT}$$\ovalbox{\tt\small REJECT}$$Q_{j}P_{j}OOO..\cdot.\cdot$$P_{j}OOOO..\cdot.\cdot$

with$\mathit{0}=(\begin{array}{ll}0 00 0\end{array})$

for $j=A$ and . Remark that the A-type (resp. -type) coined QW iscalled an A-type (resp. a -type) quantum random walk in our previous
paper [11].
$B$$\mathrm{B}$$\mathrm{G}$4Connection between QCA and A-type coined
QW

To begin with, we investigate a relation between the QCA and thecoined QW. To do so, the unitary matrix of the QCA-3 -2 -1$\overline{U}=$$.\cdot....+3+2+1-2-3+4-10\ovalbox{\tt\small REJECT}.\cdot.\cdot.\cdot...\cdot...\cdot.\cdot.\cdot..\cdot...\cdot..\cdot.\cdot$

0

$+1$

$+2$

$+3$

$+4$

da0Ob ab0c a0cdb da0cOb 0adbc d0abc 0acb 0dab$\cdot.\cdot...\cdot.\cdot.\ovalbox{\tt\small REJECT}$$\mathrm{A}$-tyPe

$\epsilon$

is rewritten as$\mathrm{r}_{\vee}$-1$\overline{U}=$

0

$+1$

$+2$

$Q_{A}P_{A}T_{A}O.\cdot.\cdot.\cdot$$Q_{A}T_{A}OO.\cdot.\cdot.\cdot$$...\cdot.\cdot.\cdot.\cdot.\cdot.\cdot..\cdot.\cdot.\cdot\ovalbox{\tt\small REJECT}$$.\cdot.\cdot.\cdot+2+1-10(’.\cdot.\cdot.$$P_{A}T_{A}OO.\cdot.\cdot.\cdot$$Q_{A}T_{A}P_{A}O...\cdot.\cdot$

where$P_{A}=(\begin{array}{ll}d c0 0\end{array})$,$T_{A}=(\begin{array}{ll}b aa b\end{array})$,$Q_{A}=(\begin{array}{ll}0 0c d\end{array})$

We consider a pair $(2k-1,2k)$ in the QCA as a site in the A-type coined
QW for any $k\in$ Z. Moreover we observe that $2k-1$ (resp. $2k$ ) site in
the QCA corresponds to right (resp. left) chirality at a site . in the A-type. We call the QCA a generalized -type coined $QW$. Whencoinedis not zero matrix, the particle has non-zero amplitudes for maintaining its
position during each time step. More precisely,
$k$

$k$

$A$

$\mathrm{Q}\mathrm{W}$$T_{A}$$|\Psi_{A,k}(n)\rangle=(\psi_{A,k}^{L}(n)\psi_{A,k}^{R}(n))$

and$|\Psi_{A,k}(n+1)\rangle=Q_{A}|\Psi_{A,k+1}(n)\rangle+T_{A}|\Psi_{A,k}(n)\rangle+P_{A}|\Psi_{A,k-1}(n)\rangle$

Prom the above observation, we see that “TypeQCA
generalized””-type coined, where $\zeta X-Y$ means that there is a one-to-one
correspondence between $X$ and ; that is,$\mathrm{V}$$\neq-\neq$($\mathrm{A}$$\mathrm{Q}\mathrm{W}$$Y$$\psi_{A,k}^{R}(n)=\beta\eta_{2k-1}^{(-1)}(n)+\alpha\eta_{2k-1}^{(0)}(n)$$x_{2k-1}^{(0.-)}.(n)=|\psi_{A,k}^{R}(n)|^{2}$,,$\psi_{A_{7}k}^{L}(n)=\beta\eta_{2k}^{(-1)}(n)+\alpha\eta_{2k}^{(0)}(n)$$x_{2k}^{(0.-)}.(n)=|\psi_{A,k}^{L}(n)|^{2}$

Here we recall Type III: $|c|^{2}+|d|^{2}=1$ ,, $cd\neq 0$ , $a=b=0$ . In
this case,becomes zero matrix. So we see that Type III is nothing but
an A-type QW by interchanging, and the roles of left and rightandchiralities with $c=b’=c’$ , $d=a’=d’$ . That is, “Type III QCA
A-type.
coinedWe should remark that asincreases (see Eq. (6)), the relative weightofincreases and the particle has greater probability of maintaining its
position. This property also holds in a generalized -type case introduced in$c\overline{d}+\overline{c}d=0$$T_{A}$$P_{A}$$Q_{A}$$arrow-arrow$$\mathrm{Q}\mathrm{W}"$$\tan\phi$$T_{A}$$\mathrm{B}$the next section

7

Connection between QCA and -type coined

5$\mathrm{B}$QW
As in the case of the A-type coined, we study a relation between the
QCA and the -type coined; that is, “TypeQCA – generalized-type coined. To do this, the unitary matrix of the QCA-2 -1
0 $+1$ $+2$ $+3$ $+4$$\mathrm{Q}\mathrm{W}$$\mathrm{B}$$\mathrm{B}$$\mathrm{V}$$\mathrm{Q}\mathrm{W}$$\mathrm{Q}\mathrm{W}"$$+5\ldots$$.\cdot.\cdot.\cdot.\cdot.\cdot..\cdot.\cdot.\cdot.\cdot.\vee...\cdot.\cdot.\cdot.\cdot.\cdot$$\overline{U}=$$000000cb$$000\mathrm{O}adcb$$..\cdot.\cdot.+5+4+3+2+1-2-10\ovalbox{\tt\small REJECT}$$00da00bc$$00ad00cb$$ad000bc0$$0ad000bc$$000000bc$$.\cdot.\cdot.\cdot.\cdot..\cdot.\cdot.\cdot.\cdot.\cdot..\cdot.\cdot.\cdot.\cdot.\cdot\ovalbox{\tt\small REJECT}$$0000dabc$

is rewritten as-1$\overline{U}=$

0

$+1$

$+2$

$Q_{B}T_{B}P_{B}O.\cdot.\cdot.\cdot$$T_{B}P_{B}OO^{\cdot}..\cdot.$$..\cdot..\cdot+2+1-10\ldots(\begin{array}{l}.\cdot\ldots T_{B}\ldots Q_{B}\ldots O\ldots O\ldots\end{array}$$\cdot.\cdot.\cdot..\cdot.\cdot.\cdot.\cdot..\cdot.\cdot..\ovalbox{\tt\small REJECT}$$Q_{B}T_{B}P_{B}O.\cdot.\cdot.\cdot$

.

where
$P_{B}=(\begin{array}{ll}d 0a 0\end{array})$,$T_{B}=(\begin{array}{ll}b cc b\end{array})$,$Q_{B}=(\begin{array}{ll}0 a0 d\end{array})$

We consider a pair $(2k, 2k+1)$ in the QCA as a site in the -type coined
QW for any $k\in$ Z. Moreover we observe that $2k$ (resp. $2k+1$ ) site in
the QCA corresponds to left (resp. right) chirality at site in the B-type. We call the QCA a generalized -type coined $QW$. Whencoinedis not zero matrix, the particle has non-zero amplitudes for maintaining its, it is shown
position during each time step. As in the case of the A-type
generalized -type coined QW , that is,that “Type QCA$k$$\mathrm{B}$

$k$

$B$

$\mathrm{Q}\mathrm{W}$$T_{B}$$\mathrm{Q}\mathrm{W}$$\mathrm{V}$$\mapsto$$\mathrm{B}$$\psi_{B,k}^{L}(n)=\alpha\eta_{2k}^{(0)}(n)+\beta\eta_{2k}^{(1)}(n)$$x_{2k}^{(0.+)}.(n)=|\psi_{B,k}^{L}(n)|^{2}$,,$\psi_{B,k}^{R}(n)=\alpha\eta_{2k+1}^{(0)}(n)+\beta\eta_{2k+1}^{(1)}(n)$$x_{2k+1}^{(0.+)}.(n)=|\psi_{B_{1}k}^{R}(n)|^{2}$

8, $ad\neq 0$ , $b=c=0$ . In,
We think of Typeis zero matrix. So Type IV becomes a -type coined QW withthis case,.
-type coined$d=a’=d’$ , $a=b’=c’$ ; that is, “Type IV QCA, which was called
Meyer [2, 3, 4] has investigated the -type coined
a quantum lattice gas automaton. His case (for example, Eq. (24) in his
in Eq. (6).
, andpaper [2] can be obtained by $6arrow 3\pi/2$ ,$a\overline{d}+\overline{a}d=0$$\mathrm{I}\mathrm{V}:|a|^{2}+|d|^{2}=1$$\mathrm{B}$$T_{B}$$\mapsto \mathrm{B}$$\mathrm{B}$6$\mathrm{Q}\mathrm{W}\mathrm{s}$$\thetaarrow\pi/2+\theta$$\phiarrow\rho$$)$$\mathrm{Q}\mathrm{W}"$

Connection between Type V QCA and twostep coined QW

In the previous two sections, we have clarified the following relations: “Type’”,-type coined, Type IV QCA
A-type coined
III QCA
generalized A-type coined QW $-\neq$ generalized
moreover “Type QCA. This section gives a relation between Type QCA and-type coined
two-step coined. The meaning of the “two-step” is that we identify the
one-step transition of Type QCA with the two-step transition of two-step.
coined”is given. Next
two-step A-type coinedFirst Type QCA”
two-step -type coinedis also presented. CombinType QCA
ing them all, we finally obtain the following relations:two-step A-type
QCA $<-$, generalized A-type coined QW“Type”
coinedQCA – generalized -type coined QW
two-step B-type“Type’coinedNow we present “generalized A-type coined QW – two-step A-type”
in the following way. A direct computation implies that a gencoined
eralized A-type coined QW with$\mapsto$$\mathrm{Q}\mathrm{W}^{7}$$\mapsto$$\mathrm{V}$$\mathrm{B}$$\Leftarrow--arrow \mathrm{B}$$\mathrm{Q}\mathrm{W}$$\mathrm{V}$$\mathrm{Q}\mathrm{W}"$$\mathrm{Q}\mathrm{W}$$\mathrm{V}$$\mathrm{Q}\mathrm{W}$$\mapsto$$\mathrm{V}$$\mapsto$$\mathrm{V}$$\mathrm{Q}\mathrm{W}$$\mathrm{B}$$\mathrm{Q}\mathrm{W}$$arrowarrow$$\mathrm{V}$$\mathrm{Q}\mathrm{W}$$\mapsto$$\mathrm{B}$$\mathrm{V}$$\mathrm{Q}\mathrm{W}^{?}$$\mathrm{Q}\mathrm{W}$$P_{A}=(\begin{array}{ll}d c0 0\end{array})$$T_{A}=(\begin{array}{ll}b aa b\end{array})$$)$,$Q_{A}=(\begin{array}{ll}0 0c d\end{array})$

is equivalent to a two-step A-type coined QW with
$P_{A}(1)=(\begin{array}{llll}i\mathrm{c}\mathrm{o}\mathrm{s}\phi e^{i\theta_{2}} \mathrm{s}\mathrm{i}\mathrm{n}\phi e^{i\theta_{2}}0 0 \end{array})$,$P_{A}(2)=e^{i\delta}$$(\begin{array}{lll}\mathrm{s}\mathrm{i}\mathrm{n}\theta e^{-\mathrm{i}\theta_{2}} -i\mathrm{c}\mathrm{o}\mathrm{s}\theta e^{i\theta_{1}}0 \mathrm{O} \end{array})$

and$Q_{A}(1)=(\begin{array}{lllll}0 0 \mathrm{s}\mathrm{i}\mathrm{n}\phi e^{i\theta_{1}} i\mathrm{c}\mathrm{o}\mathrm{s} \phi e^{i\theta_{1}}\end{array})$

for any$\theta_{1_{7}}\theta_{2}\in[0,2\pi)$$P_{A}=P_{A}(2)P_{A}(1)$,,$Q_{A}(2)=\mathrm{e}^{i\delta}$$(\begin{array}{lll}0 \mathrm{O}-i\mathrm{c}\mathrm{o}\mathrm{s}\theta e^{-i\theta_{2}} \mathrm{s}\mathrm{i}\mathrm{n}\theta e^{-i\theta_{1}}\end{array})$

where$Q_{A}=Q_{A}(2)Q_{A}(1)$,$T_{A}=P_{A}(2)Q_{A}(1)+Q_{A}(^{c_{\}}}.)P_{A}(1)$9Note that $(a, b, c, d)$ has the form given in Eq. (6) and $U(n)\equiv P_{A}(n)+Q_{A}(n)$is unitary for $n=1,2$ .
In a similar fashion, we show that “generalized -type coined QW; that is, a generalized -type coined QW with
two-step -type coined$\zeta$$arrowarrow$$\mathrm{B}$$\mathrm{B}$$\mathrm{Q}\mathrm{W}"$$\mathrm{B}$$P_{B}=(\begin{array}{ll}d 0a 0\end{array})$,$T_{B}=(\begin{array}{ll}b cc b\end{array})$,$Q_{B}=(\begin{array}{ll}0 a0 d\end{array})$corresponds to a two-step -type coined QW with$\mathrm{B}$$P_{B}(1)=(\begin{array}{lll}i\mathrm{c}\mathrm{o}\mathrm{s}\phi e^{i\theta_{2}} 0\mathrm{s}\mathrm{i}\mathrm{n}\phi e^{i\theta_{\mathrm{l}}} 0\end{array})$,$P_{B}(2)=e^{i\delta}$$(\begin{array}{lll}\mathrm{s}\mathrm{i}\mathrm{n}\theta e^{-i\theta_{2}} 0-i\mathrm{c}\mathrm{o}\mathrm{s}\theta e^{-i\theta_{2}} 0\end{array})$

and$Q_{B}(1)=(\begin{array}{ll}0 \mathrm{s}\mathrm{i}\mathrm{n}\phi e^{i\theta_{2}}0 i\mathrm{c}\mathrm{o}\mathrm{s}\phi e^{\mathrm{i}\theta_{1}}\end{array})$

for any$\theta_{1}$,$\theta_{2}\in[0,2\pi)$$P_{B}=P_{B}(2)P_{B}(1)$,, $Q_{B}(2)=e^{i\delta}$$(\begin{array}{lll}0 -i\mathrm{c}\mathrm{o}\mathrm{s}\theta e^{i\theta_{1}}0 \mathrm{s}\mathrm{i}\mathrm{n}\theta e^{-\mathrm{z}\theta_{1}}\end{array})$where$Q_{B}=Q_{B}(2)Q_{B}(1)$,$T_{B}=P_{B}(2)Q_{B}(1)+Q_{B}(2)P_{B}(1)$Remark that $P_{B}(n)$ $+Q_{B}(n)=P_{A}(n)+Q_{A}(n)$ for $n=1,2$ .
al. [1]. In their
From now on we discuss the case given by Patelasandblocks ofnotation, we take general 2$ei$$\mathrm{x}$$2$$U_{e}=(\begin{array}{ll}\mathrm{c}\mathrm{o}\mathrm{s}\phi_{1} i\mathrm{s}\mathrm{i}\mathrm{n}\phi_{1}i\mathrm{s}\mathrm{i}\mathrm{n}\phi_{1} \mathrm{c}\mathrm{o}\mathrm{s}\phi_{1}\end{array})$

Their special case is dx$=$,

Oz $=\pi/4$ ,$U_{o}=(\begin{array}{ll}\mathrm{c}\mathrm{o}\mathrm{s}\phi_{2} i\mathrm{s}\mathrm{i}\mathrm{n}\phi_{2}i\mathrm{s}\mathrm{i}\mathrm{n}\phi_{2} \mathrm{c}\mathrm{o}\mathrm{s}\phi_{2}\end{array})$$\mathrm{i}.\mathrm{e}.$$U_{e}=U_{o}= \frac{1}{\sqrt{2}}$By using$U_{e}$

and$U_{o}$$\mathrm{i}\sin\phi_{1}\cos_{0}\phi_{1}000$$.\cdot....+2+1-1-2+30\ovalbox{\tt\small REJECT}....\cdot.\cdot.\cdot.......\cdot..\cdot...\cdot$,(8)$(\begin{array}{ll}\mathrm{l} ii 1\end{array})$, the following matrices are defined:-2$\overline{U}_{e}=$$U_{o}$$U_{e}$-1$\mathrm{i}\sin\phi_{1}\mathrm{c}\mathrm{o}_{0}\mathrm{s}_{0}\phi_{1}00$0$\mathrm{i}\sin\phi_{1}\cos_{0}\phi_{1}000$

$+1$

$+2$

$+3$

$i\sin\phi_{1}\cos\phi_{1}0000$$\mathrm{i}\sin\phi_{1}\cos\phi_{1}0000$$\mathrm{i}\sin\phi_{1}\cos\phi_{1}0000$$...\cdot...\cdot....\cdot..\cdot..\cdot..\cdot.\ovalbox{\tt\small REJECT}$

10
and

-1

-2

0

$+2$

$+1$

$+3$

$.\cdot.\cdot.\cdot.\cdot..\cdot.\cdot.\cdot\sim.\cdot.\cdot.\cdot..\cdot.\cdot$$.\cdot.\cdot.\cdot.\cdot..\cdot.\cdot.\cdot.\cdot..\cdot.\cdot.\cdot.\cdot.\ovalbox{\tt\small REJECT}$$\overline{U}_{o}=$$\mathrm{c}\mathrm{o}_{0}\mathrm{s}\phi_{2}0000$$\mathrm{i}\sin\phi_{2}\mathrm{c}\mathrm{o}_{0}\mathrm{s}\phi_{2}000$$i\sin\phi_{2}\mathrm{c}\mathrm{o}_{0}\mathrm{s}\phi_{2}000$$\mathrm{i}\sin\phi_{2}\cos_{0}\phi_{2}000$$\mathrm{i}\sin\phi_{2}\cos_{0}\phi_{2}000$$.\cdot.\cdot.\cdot+3+2+1-2-10\ovalbox{\tt\small REJECT}$

Noting that$\overline{U}=\overline{U}_{e}\overline{U}_{o}$$\cos\phi_{2}00000$, we have(a, b, c,$d)=(\mathrm{i}\cos\phi_{1}\sin\phi_{2}, \cos\phi_{1}\cos\phi_{2},$i$\sin\phi_{1}\cos\phi_{2}, -\sin\phi_{1}\sin\phi_{2})$(9)Therefore, by choosing, $\phi=\pi/2-\phi_{2}$ , and $\delta=\pi/2$ in Eq. (6), we
obtain Eq. (9).
Furthermore, we see that if $\theta+\phi=\pi/2,3\pi/2$ ,, and $=2\theta_{1}+\pi/2$ ,$=\pi/4$ ,then $U(1)$ $=U(2)$ . To get the case of Patel et al., we take, and $6=\pi/2$ , so$\theta=\phi_{1}$$\theta_{1}=\theta_{2}$$\delta$$\theta=\phi$$\theta_{1}=$$\theta_{2}=0$$U(1)$ $=U(2)= \frac{1}{\sqrt{2}}$(10)$(\begin{array}{ll}i 11 i\end{array})$

Remark that $U_{e}=U_{o}$ is not equal to $U(1)=U(2)$ in their case (see Eqs.
(8) and (10) . To obtain their asymptotic result, we define their walk attime with the initial qubit stateby. Note that if, then the distribution is symmetric at any time,satisfies(see Theorem 4 in [12]). Then, our limit theorem [11, 12, 13] implies that$)$$\varphi={}^{t}(1/\sqrt{2},1/\sqrt{2})$$n$$\varphi={}^{t}(\alpha, \beta)$$X_{n}^{\varphi}$$\alpha\overline{\beta}=\overline{\alpha}\beta$$P(a \leq X_{r\iota}^{\varphi}/n\leq b)arrow\int_{a}^{b}\frac{4}{\pi(4-x^{2})\sqrt{4-2x^{2}}}dx$$(narrow\infty)$

for $-\sqrt{2}\leq a<b\leq\sqrt{2}$ . It should be noted that their case can be considered
as a two-step coined QW with $U(1)=U(2)$ , so we make a change of variables; $xarrow x/2$ in our original papers [11, 12, 13]. The above limit density
function corresponds to Eq. (34) at time $t=1$ in their paper [1]. Thus,
their asymptotic result can be easily derived from the connection between
the QCA and the two-step coined QW that is given in this section. Moreover,
it would be shown that a similar convergence theorem holds for any generalmodel with $U(1)=U(2)$ as in the above case.
Finally we should remark that in more general setting, Severini [14] hasstudied combinatorial properties of the digraphs of unitary matrices to clarify
the following question: On which digraphs can QWs be defined ?

11References[1] A. Patel, K. S. Raghunathan and P. Rungta, Quantum random walks do notneed coin toss, (2004), quant-ph/0405128.
[2] D. A. Meyer, From quantum cellular automata to quantum lattice gases, J.
Statist Phys. 85: 551-574 (1996), quant-ph/9604003.

[3] D. A. Meyer, Qunatum mechanics of lattice gas automata: one particle planewaves and potentials, Phys. Rev. E55: 5261-5269 (1997), quant-ph/9611005.
[4] D. A. Meyer, Qunatum mechanics of lattice gas automata: boundary conditions and other inhomogeneties, J. Phys. A: Math. Gen. 31: 2321-2340(1998), quant-ph/9712052.

[5] A. Ambainis, E. Bach, A. Nayak, A. Vishwanath and J. Watrous, Onedimensional quantum walks. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, (2001), 37-49.
[6] J. Kempe, Quantum random walks an introductory overview, Contemporary
Physics 44: 307-327 (2003), quant-ph/0303081.
-[7] B. Tregenna, W. Flanagan, W. Maile, and V. Kendon, Controlling discrete
quantum walks: coins and initial states, New Journal of Physics 5: 83.1-83.19(2003), quant-ph/0304204.
[8] A. Ambainis, Qunatum walks and their algorithmic applications, International Journal of Quanturn Info rmation 1: 507-518 (2003), quant-ph/0403120.
[9] B. Aoun and M. Tarifi, Introduction to quantum cellular automata, quant$\mathrm{p}\mathrm{h}/0401123$.

[10] B. Schumacher and JL F. Werner, Reversible quantum cellular automata,quant-ph/0405174.

[11] N. Konno, Limit theorems and absorption problems for quantum random
walks in one dimension, Quantum Information and Computation 2: 578-595(2002), quant-ph/0210011.
[12] N. Konno, Quantum random walks in one dimension, Quantum Information
Processing 1: 345-354 (2002), quant-ph/0206053,[13] N. Konno, A new type of limit theorems for the one-dimensional quantum
random walk, quant-ph/0206103.
[14] S. Severini, On the digraph of a unitary matrix, SIAM J. Matrix Anal . Appl.
.
25: 295-300 (2003), math.
$\mathrm{C}\mathrm{O}/0205187$