Abstract
This study investigates unitary equivalent classes of one-dimensional quantum walks. We prove that one-dimensional quantum walks are unitary equivalent to quantum walks of Ambainis type and that translation-invariant one-dimensional quantum walks are Szegedy walks. We also present a necessary and sufficient condition for a one-dimensional quantum walk to be a Szegedy walk.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
1 Introduction
This study investigates unitary equivalent classes of one-dimensional quantum walks. A quantum walk is defined by a pair \((U, \{\mathcal {H}_v\}_{v \in V})\), where V is a countable set, \(\{\mathcal {H}_v\}_{v \in V}\) is a family of separable Hilbert spaces, and U is a unitary operator on \(\mathcal {H}= \bigoplus _{v \in V} \mathcal {H}_v\) [17]. For a given quantum walk \((U, \{\mathcal {H}_v\}_{v \in V})\), we can define a digraph \(G = (V, D)\) [7, 8, 17]. In this paper, we consider primarily one-dimensional quantum walks, which have been the subject of many studies [1–6, 10–14, 16–18, 20].
It is important to clarify when we think of two quantum walks as being the same. We consider unitary equivalence of quantum walks in the sense of [17]. If two quantum walks are unitary equivalent, then their digraphs and dimensions of their Hilbert spaces are the same. Furthermore, the probability distributions of the quantum walks are also the same. Consequently, we can think of unitary equivalent quantum walks as being the same.
Unitary equivalent classes of simple quantum walks have been shown to be parameterized by a single parameter [5]. We extend this result and show that every translation-invariant one-dimensional quantum walk is unitary equivalent to a simple quantum walk. Moreover, we prove that every one-dimensional quantum walk is unitary equivalent to one of Ambainis type.
The Szegedy walk, whose original form was introduced in [19], is one of the well-investigated quantum walks (see also [9, 15–17]). We prove that every translation-invariant one-dimensional quantum walk is a Szegedy walk and present a necessary and sufficient condition for a one-dimensional quantum walk to be a Szegedy walk.
Relation between Szegedy walks and staggered quantum walks was considered in [15]. The evolution operator of a staggered quantum walk is the product of two (or more) self-adjoint unitary operators. On the other hand, the evolution operator of a quantum walk considered in this paper is just a unitary operator. Therefore, the approach used in this paper is different from that used in [15].
The remainder of this paper is organized as follows. We introduce some notations for quantum walks in Sect. 2. In Sect. 3, we describe the unitary equivalence of quantum walks. In Sect. 4, we reveal the form of standard quantum walks. In Sect. 5, we prove that every one-dimensional quantum walk is unitary equivalent to one of Ambainis type. In Sect. 6, we clarify when a one-dimensional quantum walk becomes a Szegedy walk and show that every translation-invariant one-dimensional quantum walk is a Szegedy walk.
2 Preliminaries
Let us recall the definition of quantum walks in the sense of [16, 17].
Definition 1
Let V be a countable set, \(\{\mathcal {H}_v \}_{v \in V}\) a family of separable Hilbert spaces, and U a unitary on \(\mathcal {H}= \bigoplus _{v\in V} \mathcal {H}_v\). A quantum walk is a pair \((U, \{ \mathcal {H}_v \}_{v \in V})\), and we write \((U, \{ \mathcal {H}_v \}_{v \in V}) \in \mathcal {F}_{QW}\).
A (pure) quantum state is represented by a unit vector in a Hilbert space. For \(\lambda \in {\mathbb R}\), quantum states \(\xi \) and \(\hbox {e}^{\mathrm{i}\lambda } \xi \) in \(\mathcal {H}\) are identified. Hence, quantum walks \((U, \{ \mathcal {H}_v \}_{v \in V})\) and \((\hbox {e}^{\mathrm{i}\lambda } U, \{ \mathcal {H}_v \}_{v \in V})\) are also identified.
Let \((U, \{ \mathcal {H}_v \}_{v \in V})\) be a quantum walk. \(P_v \in B(\mathcal {H})\) is a projection onto \(\mathcal {H}_v\), and \(U_{uv} \in B(\mathcal {H})\) is an operator defined by \(U_{uv} = P_u UP_v\) for all \(u, v \in V\). An operator \(U_{uv}\) is also considered as an operator in \(B(\mathcal {H}_v, \mathcal {H}_u)\), and we use the same notation if there is no confusion.
Given a quantum walk \((U, \{ \mathcal {H}_v \}_{v \in V}) \in \mathcal {F}_{QW}\), we can construct a digraph \(G = (V, D)\). For vertices \(u,v \in V\), the number of directed edges from v to u is denoted by \(\mathrm{card}(u,v)\); i.e.,
where o(e) and t(e) are the origin and the terminus of the directed edge e, respectively, and card indicates the cardinal number of a set.
Definition 2
For a quantum walk \((U, \{ \mathcal {H}_v \}_{v \in V}) \in \mathcal {F}_{ QW }\), define the number of directed edges from v to u by
Then, a digraph (V, D) is called a digraph of the quantum walk \((U, \{ \mathcal {H}_v \}_{v \in V})\).
Next, we define a translation-invariant quantum walk. Translation-invariant one-dimensional quantum walks are well known. Here, we extend the notion of translation-invariant quantum walk to arbitrary digraphs.
Definition 3
A bijection \(\gamma \) on V is called an automorphism on a digraph (V, D) if
for all \(u, v \in V\). A quantum walk \((U, \{ \mathcal {H}_v \}_{v \in V})\) is called translation invariant for \(\gamma \) if
for all \(u, v \in V\).
A digraph \(G = (V,D)\) is called symmetric if \(\mathrm{card}(u,v) = \mathrm{card}(v,u)\) for any \(u,v \in V\). A digraph \(G =(V, D)\) is called locally finite if \(\mathrm{card}\{e \in D : o(e) = v\}\) and \(\mathrm{card}\{ e\in D : t(e) = v\}\) are finite for any \(v \in V\).
Now, we introduce three classes of quantum walks.
Definition 4
A quantum walk \((U, \{ \mathcal {H}_v \}_{v \in V}) \in \mathcal {F}_{QW}\) is called standard if the digraph is locally finite and symmetric, and satisfies
for all \(v \in V\).
Note that a symmetric digraph satisfies
Definition 5
A quantum walk is called one-dimensional if \(\dim \mathcal {H}_n = 2\), and the digraph of the quantum walk satisfies \(V= {\mathbb Z}\) and
with \(\mathrm{card} (n,n+1) =\mathrm{card} (n+1,n) =1\) for all \(n \in {\mathbb Z}\), i.e., the digraph has no multiple edges.
We can canonically define an automorphism \(\gamma \) on the digraph of a one-dimensional quantum walk, i.e., \(\gamma (n) = n+1 \) for \(n \in {\mathbb Z}\).
Definition 6
[16, 17, 19] A standard quantum walk \((U, \{ \mathcal {H}_v \}_{v \in V}) \) is called a Szegedy walk if there exist a self-adjoint unitary operator S on \(\mathcal {H}\), a real number \(\lambda \in {\mathbb R}\), and unit vectors \(\phi _v \in \mathcal {H}_v\) such that \(\hbox {e}^{\mathrm{i}\lambda }SU\) has the form
where \(C_v = 2 | \phi _v \rangle \langle \phi _v | - I_{\mathcal {H}_v}\) on \(\mathcal {H}_v\). Here, the unitary operators S and C are called shift and coin operators, respectively.
Since a self-adjoint unitary operator S satisfies \(S^2 =I\), a Szegedy walk is represented as
In the case of one-dimensional quantum walks, the operator \(C_v\) is a traceless self-adjoint unitary operator.
Finally, we recall the probability distribution of a quantum walk.
Definition 7
Let \((U, \{ \mathcal {H}_v \}_{v \in V}) \in \mathcal {F}_{ QW }\), and let \(\Psi _0\) be an initial state in \(\mathcal {H}\). The probability \(\mu _t^{\Psi _0} ( v)\) of finding the quantum walker at time \(t \in {\mathbb Z}_+\) and at vertex v is defined by
3 Unitary equivalence of quantum walks
In this section, we consider the unitary equivalence of quantum walks.
Definition 8
\((U_1 , \{ \mathcal {H}_{v_1}^{(1)} \}_{v_1 \in V_1}) \in \mathcal {F}_{ QW }\) and \((U_2 , \{ \mathcal {H}_{v_2}^{(2)} \}_{v_2 \in V_2}) \in \mathcal {F}_{ QW }\) are unitary equivalent, written \((U_1 , \{ \mathcal {H}_{v_1}^{(1)} \}_{v_1 \in V_1}) \simeq (U_2 , \{ \mathcal {H}_{v_2}^{(2)} \}_{v_2 \in V_2})\), if there exist a unitary W from \(\bigoplus _{v_1\in V_1} \mathcal {H}_{v_1}\) to \(\bigoplus _{v_2\in V_2} \mathcal {H}_{v_2}\) and a bijection \(\phi \) from \(V_1\) to \(V_2\) such that
We would like to regard unitary equivalent quantum walks as being the same. The next proposition says that unitary equivalent quantum walks have the same digraphs.
Proposition 1
Let \((U_1 , \{ \mathcal {H}_{v_1}^{(1)} \}_{v_1 \in V_1})\) and \((U_2 , \{\mathcal {H}_{v_2}^{(2)} \}_{v_2 \in V_2})\) be quantum walks, and let \(G_1 = (V_1, D_1)\) and \(G_2 = (V_2, D_2)\) be their digraphs. If quantum walks \((U_1 , \{ \mathcal {H}_{v_1}^{(1)} \}_{v_1 \in V_1})\) and \((U_2 , \{ \mathcal {H}_{v_2}^{(2)} \}_{v_2 \in V_2})\) are unitary equivalent by a unitary W, the digraphs \(G_1 = (V_1, D_1)\) and \(G_2 = (V_2, D_2)\) are isomorphic; that is, there exists a bijection \(\phi \) from \(V_1\) to \(V_2\) such that
Proof
From the definition of unitary equivalence, there exists a bijection \(\phi \) from \(V_1\) to \(V_2\). A unitary W maps \(\mathcal {H}_{v_1}\) to \(\mathcal {H}_{\phi (v_1)}\), with the result that \(W P_{v_1} W^* = P_{\phi (v_1)}\). Since \(\mathrm{card}(u,v) = \mathrm{rank} P_u U_1 P_v\) for \(u,v \in V_1\),
Hence, we obtain the proposition. \(\square \)
When \((U_1 , \{ \mathcal {H}_{v_1}^{(1)} \}_{v_1 \in V_1}) \in \mathcal {F}_{QW}\) and \((U_2 , \{ \mathcal {H}_{v_2}^{(2)} \}_{v_2 \in V_2}) \in \mathcal {F}_{QW}\) are unitary equivalent, we can identify \(V_2\) with \(V_1\) using the bijection \(\phi \), and write \(V = V_1\). Similarly, \(D_1\) and \(D_2\), and \(\mathcal {H}^{(1)}_{v}\) and \(\mathcal {H}^{(2)}_{\phi (v)}\) can be identified, and we write \(D= D_1\) and \(\mathcal {H}_v = \mathcal {H}_{v}^{(1)}\). Here, the unitary W can be decomposed as
where \(W_v = P_v W P_v\).
The following corollary is an immediate consequence of Proposition 1.
Corollary 1
Let quantum walks \((U_1, \{ \mathcal {H}_v \}_{v\in V})\) and \((U_2, \{ \mathcal {H}_v \}_{v\in V})\) be unitary equivalent. If \((U_1, \{ \mathcal {H}_v \}_{v\in V})\) is standard or one-dimensional, then so is \((U_2, \{ \mathcal {H}_v \}_{v\in V})\).
Unitary equivalence also preserves the properties of a Szegedy walk.
Proposition 2
Let quantum walks \((U_1, \{ \mathcal {H}_v \}_{v\in V})\) and \((U_2, \{ \mathcal {H}_v \}_{v\in V})\) be unitary equivalent by a unitary W. If \((U_1, \{ \mathcal {H}_v \}_{v\in V})\) is a Szegedy walk, then so is \((U_2, \{ \mathcal {H}_v \}_{v\in V})\).
Proof
By the assumption, there exist a self-adjoint unitary S on \(\mathcal {H}\), a real number \(\lambda \in {\mathbb R}\), and unit vectors \(\phi _v \in \mathcal {H}_v\) such that \(\hbox {e}^{\mathrm{i}\lambda } SU_1\) has the form
where \(C_v = 2 |\phi _v\rangle \langle \phi _v|-I_{\mathcal {H}_v}\). Then, \( WSW ^*\) is also a self-adjoint unitary on \(\mathcal {H}\). Moreover,
from which it follows that \((U_2, \{ \mathcal {H}_v \}_{v\in V})\) is a Szegedy walk. \(\square \)
In general, a quantum walk that is unitary equivalent to a translation-invariant quantum walk is not translation invariant. However, if we add a condition, then translation invariance is also preserved.
Proposition 3
Let \((U, \{ \mathcal {H}_n \}_{n\in {\mathbb Z}})\) be a translation-invariant one-dimensional quantum walk such that \(\mathcal {H}_n =\mathcal {H}_{n+1}\) for all \(n \in {\mathbb Z}\), and let W be a unitary on \(\mathcal {H}\) that has the form
where \(W_n\) is a unitary on \(\mathcal {H}_n\), and \(W_n = W_{n+1}\) for all \(n \in {\mathbb Z}\). The quantum walk \(( WUW ^*, \{ \mathcal {H}_n \}_{n\in {\mathbb Z}})\) is a translation-invariant one-dimensional quantum walk.
Proof
It is sufficient to prove that \( WUW ^*\) is translation invariant; i.e., \(P_n WUW ^* P_m = P_{\gamma (n)} WUW ^* P_{\gamma (m)}\). Since U is translation invariant,
Hence, \( WUW ^*\) is translation invariant. \(\square \)
Finally, we consider the probability distribution of a quantum walk. This does not change under unitary equivalence.
Proposition 4
Let quantum walks \((U_1, \{ \mathcal {H}_v \}_{v\in V})\) and \((U_2, \{ \mathcal {H}_v \}_{v\in V})\) be unitary equivalent by a unitary W, let \(\Phi _0\) and \(W\Phi _0\) in \(\mathcal {H}\) be an initial state of \((U_1, \{ \mathcal {H}_v \}_{v\in V}) \) and \((U_2, \{ \mathcal {H}_v \}_{v\in V})\), respectively, and let \(\mu _t^{(1), \Phi _0}\) and \(\mu _t^{(2), W\Phi _0}\) be the probability distributions of the quantum walks \((U_1, \{ \mathcal {H}_v \}_{v\in V}) \) and \((U_2, \{ \mathcal {H}_v \}_{v\in V}) \), respectively. Then,
for all \(t \in {\mathbb Z}_+\) and \(v \in V\).
Proof
By the definition,
Therefore, we obtain the proposition. \(\square \)
One of the primary topics of study in connection with quantum walks is the probability distributions of quantum walks, by virtue of which we can think of unitary equivalent quantum walks as being the same. When we consider other properties of quantum walks, additional properties, such as Proposition 3, must be considered.
4 Standard quantum walk
This study investigates one-dimensional quantum walks and Szegedy walks. Since both kinds of quantum walk are standard, we clarify the form of a standard quantum walk.
Theorem 1
Let \((U, \{ \mathcal {H}_v \}_{v \in V}) \in \mathcal {F}_{QW}\) be a standard quantum walk. There exist orthonormal bases \(\{\xi _{e}\}_{e \in D}\) and \(\{\zeta _{e}\}_{e\in D}\) of \(\mathcal {H}\) with \(\xi _{e} \in \mathcal {H}_{t(e)}\) and \(\zeta _{e} \in \mathcal {H}_{o(e)}\), such that
Moreover, \(U_{uv}\) has the form
for any \(u, v \in V\).
Proof
Since \(\mathrm{rank}U_{uv} = \mathrm{card} \{ e \in V : t(e) = u, o(e) = v\}\), we can set \(\{\xi _e : t(e) = u, o(e) =v, e\in D \} \subset \mathcal {H}_u = \mathcal {H}_{t(e)}\) as an orthonormal basis of \(\mathrm{ran} U_{uv}\) for all \(u,v \in V\), where \(\mathrm{ran} U_{uv}\) is the range of \(U_{uv}\). Then, \(\{\xi _e : o(e) =v, e\in D \}\) is an orthonormal system of \(\mathcal {H}\). An operator \(UP_v\) is a partial isometry with an initial projection \(P_v\). The range of this operator is contained in \(\bigoplus _{u\in V} \mathrm{ran} U_{uv} = \mathrm{span}\{ \xi _{e} : o(e) =v , e \in D \}\), that is,
From the definition of a standard quantum walk, \( \dim \mathcal {H}_v = \mathrm{card} \{ e \in D : o(e) = v\}\). Since the rank of the range projection of \(U P_v\) is equal to the rank of the initial projection \(P_v, \mathrm{rank} U P_v = \mathrm{card} \{ e \in D : o(e) = v\}\). Considering the dimensions of the subspaces in (1),
Moreover, the range projection \( UP _v U^*\) leaves \(\mathrm{span}\{ \xi _{e} : o(e) =v , e \in D \}\) unchanged. Therefore, \(U P_v U^* \xi _e = \xi _e\) for all \(e \in D\) with \(o(e) =v\), and this implies that \(P_v U^* \xi _e = U^* \xi _e\), with the result that \(U^* \xi _e \in \mathcal {H}_v =\mathcal {H}_{o(e)}\).
Let \(\zeta _{e} = U^* \xi _{e}\). Since \(\{ \xi _{e} : o(e) = v , e\in D \}\) is an orthonormal system, \(\{\zeta _{e} : o(e) =v , e\in D \}\) is an orthonormal basis of \(\mathcal {H}_v\). Hence, \(\{ \zeta _{e} : e \in D\}\) is an orthonormal basis of \(\mathcal {H}\). Since U is unitary and \(U\zeta _{e} = \xi _{e}, \{\xi _{e} : e \in D \}\) is also an orthonormal basis of \(\mathcal {H}\), and
By the definition of \(U_{uv}\), the equation
also holds. \(\square \)
Corollary 2
For a standard quantum walk \((U, \{ \mathcal {H}_v \}_{v \in V}) \in \mathcal {F}_{QW}\), there exist a self-adjoint unitary operator S on \(\mathcal {H}\) and a unitary operator \(T_v\) on \( \mathcal {H}_v (v \in V)\) such that \(U = ST\), where \(T = \bigoplus _{v \in V} T_v\).
Proof
Since the digraph of a standard quantum walk is symmetric, there exists a bijection on D, denoted by \(e \mapsto \bar{e}\), for which \(t(e) = o(\bar{e}), o(e) = t(\bar{e})\), and \(\bar{\bar{e}} =e\).
By Theorem 1, U can be written as
Define S by \(S\xi _{e} = \xi _{\bar{e}}. S\) is a self-adjoint unitary; hence, \(S^2=I\). Then,
The operator
satisfies the assertion. \(\square \)
Now, to clarify the explicit form of a shift operator S of a Szegedy walk, we present the next lemma.
Lemma 1
Let \((U, \{\mathcal {H}_v\}_{v\in V})\) be a Szegedy walk with a shift operator S and a coin operator C, such that \(U = \hbox {e}^{\mathrm{i}\lambda } SC\) for some \(\lambda \in {\mathbb R}\). Then,
for any \(u, v \in V\).
Proof
By Theorem 1, we can assume that there exist orthonormal bases \(\{\xi _{e}\}_{e \in D}\) and \(\{\zeta _{e}\}_{e\in D}\) of \(\mathcal {H}\) with \(\xi _{e} \in \mathcal {H}_{t(e)}\) and \(\zeta _{e} \in \mathcal {H}_{o(e)}\), such that
Then, \(\mathrm{ran} U_{uv} = \mathrm{span} \{ \xi _e: t(e) = u, o(e) =v, e\in D \}\). Since the coin operator C is written as a direct sum of \(C_v\),
for all \(e \in D\) with \(t(e)=u\) and \(o(e) = v\). This implies that \(S(\mathrm{ran} U_{uv}) \subset \mathcal {H}_v\). Furthermore, by the form of \(U, \mathcal {H}_v\) is decomposed as
Here,
Since \(S( \mathrm{ran} U_{vw}) \subset \mathcal {H}_w\) and \(\mathrm{ran} U_{uv} \subset \mathcal {H}_u, \mathrm{ran} U_{uv} \subset S(\mathrm{ran} U_{vu})\). Considering the inversion formula,
for all \(u,v \in V\). \(\square \)
Using this lemma, we have the next theorem.
Theorem 2
Let \((U, \{\mathcal {H}_v\}_{v\in V})\) be a Szegedy walk with a shift operator S and a coin operator C, such that \(U = \hbox {e}^{\mathrm{i}\lambda } SC\) for some \(\lambda \in {\mathbb R}\). There exist orthonormal bases \(\{\xi _e \}_{e \in D}\) and \(\{\zeta _e \}_{e \in D}\) of \(\mathcal {H}\) with \(\xi _e \in \mathcal {H}_{t(e)}\) and \(\zeta _e \in \mathcal {H}_{o(e)}\) such that
Proof
By Theorem 1, we can assume that there exist orthonormal bases \(\{\xi _{e}\}_{e \in D}\) and \(\{\zeta _{e}\}_{e\in D}\) of \(\mathcal {H}\) with \(\xi _{e} \in \mathcal {H}_{t(e)}\) and \(\zeta _{e} \in \mathcal {H}_{o(e)}\) such that
By Lemma 1, \(S(\mathrm{ran} U_{uv}) = \mathrm{ran} U_{vu}\). Moreover, in the proof of Theorem 1, the choice of an orthonormal basis of \(\mathrm{ran} U_{uv}\) is arbitrary. Therefore, for an orthonormal basis \(\{\xi _e : t(e)=u, o(e) =v , e\in D \}\) of \(\mathrm{ran}U_{uv}\), we can redefine \(\xi _{\bar{e}} = S \xi _e\). Then, \(\{ \xi _{\bar{e}} : t(e)=u, o(e) =v , e\in D \}\) is an orthonormal basis of \(\mathrm{ran}U_{vu}\). Consequently, we can obtain orthonormal bases \(\{\xi _e \}_{e \in D}\) and \(\{\zeta _e \}_{e \in D}\) of \(\mathcal {H}\) with \(\xi _e \in \mathcal {H}_{t(e)}\) and \(\zeta _e \in \mathcal {H}_{o(e)}\) such that
This completes the proof. \(\square \)
5 One-dimensional quantum walk
In this section, we consider a one-dimensional quantum walk \((U, \{ \mathcal {H}_n \}_{n\in {\mathbb Z}})\). Without loss of generality, we can assume that \(\mathcal {H}_n = {\mathbb C}^2\) for all \(n \in {\mathbb Z}\). Here, \(D = \{ (n, n+1) , (n+1,n) : n \in {\mathbb Z}\}\). By Theorem 1, there exist orthonormal bases \(\{ \xi _{n,n+1} ,\xi _{n+1,n} \}_{n \in {\mathbb Z}}\) and \(\{ \zeta _{n,n+1}, \zeta _{n+1,n} \}_{n \in {\mathbb Z}}\) of \(\mathcal {H}\) with \(\xi _{n,n+1},\zeta _{n+1,n} \in \mathcal {H}_n\) and \(\xi _{n+1,n} , \zeta _{n,n+1} \in \mathcal {H}_{n+1}\) such that
There is a substantial literature on one-dimensional quantum walks, which fall into four principal types. The first type is represented as follows. Let \(\{e_1^n, e_2^n\}\) be a canonical orthonormal basis of \(\mathcal {H}_n = {\mathbb C}^2\). We consider \(e_i^n\) as \(|n\rangle |i\rangle \). We take \(\xi _{n-1,n} = e_1^{n-1}, \xi _{n+1,n} = e_2^{n+1}\), and \(\zeta _{n-1, n} = \bar{a}_n e_1^n + \bar{b}_n e_2^n, \zeta _{n+1, n} = \bar{c}_n e_1^n + \bar{d}_n e_2^n\). Then,
A quantum walk of this type is said to be of Ambainis type [2, 3]. A set of all quantum walks of this type is denoted by \(\mathcal {C}_1\). Note that
is unitary.
The second type is represented by taking \(\xi _{n-1, n} = {a}_{n} e_1^{n-1} + c_n e_2^{n-1}, \xi _{n+1, n} = {b}_n e_1^{n+1} + {d}_n e_2^{n+1}\), and \(\zeta _{n-1,n} = e_1^{n}, \zeta _{n+1,n} = e_2^{n}\), such that
A quantum walk of this type is said to be of Gudder type [6]. A set of all quantum walks of this type is denoted by \(\mathcal {C}_2\).
Similarly, the third type is represented by taking \(\xi _{n-1,n} = e_2^{n-1}, \xi _{n+1,n} = e_1^{n+1}\), and \(\zeta _{n-1, n} = \bar{c}_n e_1^n + \bar{d}_n e_2^n, \zeta _{n+1, n} = \bar{a}_n e_1^n + \bar{b}_n e_2^n\), such that
A set of all quantum walks of this type is denoted by \(\mathcal {C}_3\). The fourth type is represented by taking \(\xi _{n-1, n} = {b}_{n} e_1^{n-1} + d_n e_2^{n-1}, \xi _{n+1, n} = {a}_n e_1^{n+1} + {c}_n e_2^{n+1}\), and \(\zeta _{n-1,n} = e_2^{n}, \zeta _{n+1,n} = e_1^{n}\), such that
A set of all quantum walks of this type is denoted by \(\mathcal {C}_4\).
Summarizing, we have four types of one-dimensional quantum walks:
These four types of one-dimensional quantum walks are also represented as follows:
Theorem 3
Let \((U, \{ \mathcal {H}_n \}_{n \in {\mathbb Z}})\) be a one-dimensional quantum walk. For each \(k =1,2,3,4\), there exists a one-dimensional quantum walk in \(\mathcal {C}_k\) that is unitary equivalent to \((U, \{ \mathcal {H}_n \}_{n \in {\mathbb Z}})\).
Proof
By Theorem 1, U can be written as
where \(\{ \xi _{n,n+1} ,\xi _{n+1,n} \}_{n \in {\mathbb Z}}\) and \(\{ \zeta _{n,n+1}, \zeta _{n+1,n} \}_{n \in {\mathbb Z}}\) are orthonormal bases of \(\mathcal {H}\) with \(\xi _{n,n+1},\zeta _{n+1,n} \in \mathcal {H}_n\) and \(\xi _{n+1,n} , \zeta _{n,n+1} \in \mathcal {H}_{n+1}\).
First, we prove that \((U, \{ \mathcal {H}_n \}_{n \in {\mathbb Z}})\) is unitary equivalent to a quantum walk in \(\mathcal {C}_1\). Let
for all \(n \in {\mathbb Z}\). It is easily seen that \(W_n\) is a unitary on \(\mathcal {H}_n\), with the result that \(W = \bigoplus _{n\in {\mathbb Z}} W_n\) is a unitary on \(\mathcal {H}\) that satisfies \(W\mathcal {H}_n = \mathcal {H}_n\). Moreover, from a direct calculation,
Since \(W= \bigoplus _{n\in {\mathbb Z}} W_n\) is unitary, \(\{W\zeta _{n-1,n} , W\zeta _{n+1,n}\}\) is an orthonormal basis of \(\mathcal {H}_n\). Hence, \((WUW^*, \{\mathcal {H}_n\}_{n\in {\mathbb Z}})\) is in \(\mathcal {C}_1\), and we obtain that \((U, \{ \mathcal {H}_n \}_{n \in {\mathbb Z}})\) is unitary equivalent to a quantum walk in \(\mathcal {C}_1\).
Second, we prove that \((U, \{ \mathcal {H}_n \}_{n \in {\mathbb Z}})\) is unitary equivalent to a quantum walk in \(\mathcal {C}_2\). Let
for all \(n \in {\mathbb Z}\). It is easily seen that \(W_n\) is a unitary on \(\mathcal {H}_n\), with the result that \(W = \bigoplus _{n\in {\mathbb Z}} W_n\) is a unitary on \(\mathcal {H}\). Moreover, from a direct calculation, we have
Since \(W= \bigoplus _{n\in {\mathbb Z}} W_n\) is unitary, \(\{W\xi _{n,n-1} , W\xi _{n,n+1}\}\) is an orthonormal basis of \(\mathcal {H}_n\). Hence, \((WUW^*, \{\mathcal {H}_n\}_{n\in {\mathbb Z}})\) is in \(\mathcal {C}_2\), and we obtain that \((U, \{ \mathcal {H}_n \}_{n \in {\mathbb Z}})\) is unitary equivalent to a quantum walk in \(\mathcal {C}_2\).
The proofs of the remaining parts are similar to these. \(\square \)
As a corollary of the theorem, we have the following.
Corollary 3
Let \((U, \{ \mathcal {H}_n \}_{n \in {\mathbb Z}})\) be a translation-invariant one-dimensional quantum walk. For each \(k =1,2,3,4\), there exists a translation-invariant one-dimensional quantum walk in \(\mathcal {C}_k\) that is unitary equivalent to \((U, \{ \mathcal {H}_n \}_{n \in {\mathbb Z}})\).
Proof
By Theorem 1, U can be written as
where \(\{ \xi _{n,n+1} ,\xi _{n+1,n} \}_{n \in {\mathbb Z}}\) and \(\{ \zeta _{n,n+1}, \zeta _{n+1,n} \}_{n \in {\mathbb Z}}\) are orthonormal bases of \(\mathcal {H}\) with \(\xi _{n,n+1},\zeta _{n+1,n} \in \mathcal {H}_n\) and \(\xi _{n+1,n} , \zeta _{n,n+1} \in \mathcal {H}_{n+1}\). Moreover, by translation invariance, we can assume that
for all \(n \in {\mathbb Z}\). Therefore, in the proof of Theorem 3, \(W_n = W_{n+1}\) for all \(n \in {\mathbb Z}\). Then, the assertion of the corollary follows from Proposition 3. \(\square \)
6 One-dimensional Szegedy walk
In this section, we consider a necessary and sufficient condition for a one-dimensional quantum walk to be a Szegedy walk. Let \((U, \{\mathcal {H}_n \}_{n\in {\mathbb Z}})\) be a one-dimensional quantum walk. Considering the unitary equivalence, we can assume \(\mathcal {H}_n = {\mathbb C}^2\) for all \(n \in {\mathbb Z}\) without loss of generality. By Theorem 3, we can assume that U is represented as
where \(\{\zeta _{n-1,n} , \zeta _{n+1,n}\}\) is an orthonormal basis of \(\mathcal {H}_n\). Here,
where the matrix
is unitary for all \(n \in {\mathbb Z}\).
If this is a Szegedy walk, there exists a shift operator S such that \(\hbox {e}^{\mathrm{i}\lambda } SU\) is a direct sum of traceless self-adjoint unitary operators for some \(\lambda \in {\mathbb R}\). By Lemma 1, \(S(\mathrm{ran}U_{n,n+1}) = \mathrm{ran}U_{n+1, n}\). Moreover, \(\mathrm{ran}U_{n+1,n} = {\mathbb C} e_2^{n+1}\) and \(\mathrm{ran}U_{n, n+1} = {\mathbb C} e_1^{n}\). Therefore, \(S e_1^n =\hbox {e}^{\mathrm{i}\theta _n} e_2^{n+1}\) for some \(\theta _n \in {\mathbb R}\). Consequently, S has the form
Then, SU is described as
Let \(c_n = \hbox {e}^{\mathrm{i}\mu _n} r_n\) and \(b_n = \hbox {e}^{\mathrm{i}\nu _n} r_n\) with \(r_n \ge 0\) and \(\mu _n, \nu _n \in {\mathbb R}\). Then,
When \(r_n \ne 0\), the \(2\times 2\) matrices on the right-hand side are traceless self-adjoint unitary if and only if
Indeed, assume that the \(2\times 2\) matrices on the right-hand side of (3) are traceless self-adjoint unitary. Then, the diagonal entries are real, and the sum of them is zero. Therefore,
and
These equations imply (4). Conversely, assume (4). Then, the matrices in (3) are traceless, and their diagonal entries are real. Since SU is unitary by the definitions of S and U, the matrices in (3) are also unitary. It is easy to see that a \(2 \times 2\) traceless unitary matrix with real and nonzero diagonal entries is self-adjoint.
In the case \(r_n = 0, |a_n| = |d_n| =1\), because SU is unitary. Let \(a_n = \hbox {e}^{\mathrm{i}\sigma _n}\) and \(d_n = \hbox {e}^{\mathrm{i}\tau _n}\) for some \(\sigma _n, \tau _n \in {\mathbb R}\). Then, (3) is represented as
Therefore, the \(2 \times 2\) matrices on the right-hand side are traceless self-adjoint unitary if and only if
Hence, \(\theta _n\) and \(\lambda \) satisfy conditions (4) and (5).
Conversely, if there exist \(\theta _n\) and \(\lambda \) satisfying these conditions, the quantum walk \((U, \{\mathcal {H}_n \}_{n \in {\mathbb Z}})\) is a Szegedy walk. Indeed, define a shift operator S by (2). Then, it is easily seen that \(\hbox {e}^{\mathrm{i}\lambda } SU\) is a direct sum of traceless self-adjoint unitary operators.
Therefore, \((U, \{\mathcal {H}_n \}_{n \in {\mathbb Z}})\) is a Szegedy walk if and only if the above simultaneous equations for \(\lambda \) and \(\theta _n\) have a solution.
Now, we have the next theorem.
Theorem 4
Let \((U, \{\mathcal {H}_n \}_{n \in {\mathbb Z}})\) be a one-dimensional quantum walk given by
where \(r_n , s_n \ge 0\) and \(\mu _n, \nu _n, \sigma _n , \tau _n \in {\mathbb R}\), and let \(\hbox {e}^{ \mathrm{i}\delta _n} (\delta _n \in {\mathbb R})\) be the determinant of
\((U, \{\mathcal {H}_n \}_{n \in {\mathbb Z}})\) is a Szegedy walk if and only if the simultaneous equations
for all \(n \in {\mathbb Z}\) and
with respect to \( \lambda \) and \( \{ \theta _n \}_{n\in {\mathbb Z}}\) have a solution.
Proof
The determinant of \(U_n\) is calculated as
Since \(s_n^2+r_n^2 =1\) and \(|\hbox {e}^{\mathrm{i}\delta _n}| =1\),
modulo \(2\pi \). Hence, equation (5) is calculated as
On the other hand, the first equation in (4) is equivalent to
with the result that
Therefore, the second equation in (4) is calculated as
Equation (8) is equivalent to the first equation in (4). Consequently, the simultaneous equations (4) and (5) have a solution if and only if the simultaneous equations (7) and (8) have a solution. \(\square \)
Another necessary and sufficient condition for a one-dimensional quantum walk to be a Szegedy walk is easier to check in some cases.
Corollary 4
Let \(\{n_k \}_{k \in \Lambda } \subset {\mathbb Z}\) be numbers indexed by \(\Lambda \subset {\mathbb Z}\) that satisfy \(r_{n_k} \ne 0\) with \(n_k < n_{k+1}\). Suppose that \(\Lambda \ne \emptyset \) and \(0 \in \Lambda \). A one-dimensional quantum walk \((U, \{\mathcal {H}_n \}_{n \in {\mathbb Z}})\) given by (6) is a Szegedy walk if and only if there exists \(\eta \in {\mathbb R}\) such that
for all \(k \in \Lambda \) with \(k-1 \in \Lambda \).
Proof
First, we assume that the simultaneous equations (7) and (8) have a solution \(\{\lambda , \theta _n\}\). By (7)
Since \(\theta _{n_k}\) and \(\theta _{n_{k-1}}\) satisfy (8),
with the result that
On the other hand, assume that there exists \(\eta \in {\mathbb R}\) such that
for all \(k \in \Lambda \) with \(k-1 \in \Lambda \). Set \(\lambda = -\eta /2, \theta _{n_0} = \mu _{n_0} + \lambda \), and
inductively. Then, \(\lambda \) and \(\theta _n\) satisfy (7). Moreover, if \(\theta _{n_{k-1}}\) with \(n_{k-1}\ge n_0\) satisfies (8), then \(\theta _{n_k}\) also satisfies (8). Indeed, by (9) and (10),
Similarly, if \(\theta _{n_{k}}\) with \(n_{k} \le n_0\) satisfies (8), then \(\theta _{n_{k-1}}\) also satisfies (8). Indeed, by (9) and (10),
This completes the proof. \(\square \)
As a special case of Corollary 4, we have the next corollary.
Corollary 5
A one-dimensional quantum walk \((U, \{\mathcal {H}_n \}_{n \in {\mathbb Z}})\) given by (6) with \(r_n \ne 0\) for all \(n \in {\mathbb Z}\) is a Szegedy walk if and only if there exists \(\eta \in {\mathbb R}\) such that
When \(r_n =0\) for all \(n\in {\mathbb Z}\), a one-dimensional quantum walk is a Szegedy walk.
Corollary 6
A one-dimensional quantum walk \((U, \{\mathcal {H}_n \}_{n \in {\mathbb Z}})\) given by (6) with \(r_n = 0\) for all \(n \in {\mathbb Z}\) is a Szegedy walk.
Proof
Set \(\lambda = 0, \theta _0 =0\), and
inductively. This is a solution of simultaneous equations (7). \(\square \)
Using these corollaries, we prove that every translation-invariant one-dimensional quantum walk is a Szegedy walk.
Corollary 7
A translation-invariant one-dimensional quantum walk is a Szegedy walk.
Proof
If \(r_n =0\) for all \(n \in {\mathbb Z}\), then it is a Szegedy walk by Corollary 6. If \(r_n \ne 0\) for all \(n \in {\mathbb Z}\), then \(\mu _{n-1} + \nu _n\) is a constant, because the quantum walk is translation invariant. Therefore, it is a Szegedy walk by Corollary 5. \(\square \)
Now, we consider some known models of one-dimensional quantum walks.
Corollary 8
A one-dimensional quantum walk \((U, \{\mathcal {H}_n \}_{n \in {\mathbb Z}})\) with 2 coins [4, 10], i.e.,
where \(r_+, r_- >0\), is a Szegedy walk if and only if
Proof
By Corollary 5, \((U, \{\mathcal {H}_n \}_{n \in {\mathbb Z}})\) is a Szegedy walk if and only if there exists \(\eta \in {\mathbb R}\) such that
This condition is equivalent to
\(\square \)
Using Corollary 5, we have following two corollaries.
Corollary 9
The following quantum walk, considered in [12],
is a Szegedy walk.
Corollary 10
The following quantum walk, considered in [13, 14],
is a Szegedy walk if and only if there exists \(\eta \in {\mathbb R}\) such that
Using Theorem 4, we can prove that a quantum walk of the Shikano–Katsura model [18] is a Szegedy walk.
Corollary 11
A quantum walk of the Shikano–Katsura model, i.e.,
is a Szegedy walk for any \(\alpha \in {\mathbb R}\).
Proof
By the definition of \(U, \delta _n\) is 0, and \(\mu _n\) is 0 or \(\pi \) for all \(n \in {\mathbb Z}\). Set \(\lambda =0, \theta _n=0\) for all \(n \in {\mathbb Z}\). This is a solution of (7) and (8). \(\square \)
References
Aharanov, L., Davidovidh, N., Zagury, N.: Quantum random walks. Phys. Rev. A 48, 1687–1690 (1993)
Ambainis, A.: Quantum walks and algorithmic applications. Int. J. Quantum Inf. 1, 507–518 (2003)
Ambainis, A., Bach, E., Nayak, A., Vishwanath, A., Watrous, J.: One-dimensional quantum walks. In: Proceedings of 33th ACM Symposium of the Theory of Computing, pp. 37–49 (2001)
Endo, T., Konno, N., Obuse, H.: Relation between two-phase quantum walks and the topological invariant. arXiv:1511.04230
Goyal, S.K., Konrad, T., Diósi, L.: Unitary equivalence of quantum walks. Phys. Lett. A 379, 100–104 (2015)
Gudder, S.P.: Quantum Probability. Academic Press, New York (1988)
Higuchi, Y., Konno, N., Sato, I., Segawa, E.: Quantum graph walks I: mapping to quantum walks. Yokohama Math. J. 59, 33–55 (2013)
Higuchi, Y., Konno, N., Sato, I., Segawa, E.: Quantum graph walks II: quantum walks on graph coverings. Yokohama Math. J. 59, 57–90 (2013)
Higuchi, Y., Konno, N., Sato, I., Segawa, E.: Spectral and asymptotic properties of Grover walks on crystal lattices. J. Funct. Anal. 267, 4197–4235 (2014)
Kitagawa, T., Rudner, M.S., Berg, E., Demler, E.: Exploring topological phases with quantum walks. Phys. Rev. A 82, 033429 (2010)
Konno, N.: Quantum random walks in one dimensional. Quantum Inf. Process. 1, 345–354 (2002)
Konno, N.: One-dimensional discrete-time quantum walks on random environment. Quantum Inf. Process. 8, 387–399 (2009)
Konno, N.: Localization of an inhomogeneous discrete-time quantum walk on the line. Quantum Inf. Process. 9, 405–418 (2010)
Konno, N., Łuczak, T., Segawa, E.: Limit measures of inhomogeneous discrete-time quantum walks in one dimensional. Quantum Inf. Process. 12, 33–53 (2013)
Portugal, R., Santos, R.A., Fernandes, T.D., Gonçalves, D.N.: The staggered quantum walk model. Quantum Inf. Process. 15, 85–101 (2016)
Segawa, E., Suzuki, A.: Spectral mapping theorem of an abstract quantum walk. arXiv:1506.06457
Segawa, E., Suzuki, A.: Generator of an abstract quantum walk. Quantum Stud. Math. Found. (2016). doi:10.1007/s40509-016-0070-1
Shikano, Y., Katsura, H.: Localization and fractality in inhomogeneous quantum walks with self-duality. Phys. Rev. E 82, 031122 (2010)
Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: Proceedings of 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 32–41 (2004)
Venegas-Andraca, S.E.: Quantum walks: a comprehensive review. Quantum Inf. Process. 11, 1015–1106 (2012)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Ohno, H. Unitary equivalent classes of one-dimensional quantum walks. Quantum Inf Process 15, 3599–3617 (2016). https://doi.org/10.1007/s11128-016-1361-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11128-016-1361-5