Directional quantum random walk induced by coherence

Abstract

Quantum walk (QW), which is considered as the quantum counterpart of the classical random walk (CRW), is actually the quantum extension of CRW from the single-coin interpretation. The sequential unitary evolution engenders correlation between different steps in QW and leads to a non-binomial position distribution. In this paper, we propose an alternative quantum extension of CRW from the ensemble interpretation, named quantum random walk (QRW), where the walker has many unrelated coins, modeled as two-level systems, initially prepared in the same state. We calculate the walker’s position distribution in QRW for different initial coin states with the coin operator chosen as Hadamard matrix. In one-dimensional case, the walker’s position is the asymmetric binomial distribution. We further demonstrate that in QRW, coherence leads the walker to perform directional movement. For an initially decoherenced coin state, the walker’s position distribution is exactly the same as that of CRW. Moreover, we study QRW in 2D lattice, where the coherence plays a more diversified role in the walker’s position distribution.

Graphical abstract

Keywords

quantum walk / random walk / ensemble interpretation / directional walking / coherence

1 Introduction

In the classical random walk (CRW), the walker is usually assumed to have one single coin. At each step, he flips the coin and decides the moving direction according to the flipping result [1]. The coin is either heads or tails after flipping, and then the walker moves right or left accordingly in one-dimensional case. This is the single-coin interpretation for CRW. Since the flipping process of CRW eliminates the correlation between the coin and the walker, no correlation exists between different steps. In other words, the coins can be considered as independent coins for different steps. This indicates that we can understand CRW with the ensemble interpretation, where the walker possesses many independent coins, and flips each coin at each step.

It is conventionally understood that the quantum counterpart of CRW is the quantum walk (QW) [2-5] (named as quantum random walk in early studies), the concept of which was first proposed by Aharonov [2]. Different from CRW, the walker’s position distribution of QW is found to be non-binomial [5-8]. QW has been extensively studied to utilize its advantage in quantum computation [9-11], quantum simulation [12, 13], or to give a prototype to understand the quantum phase transition and the topological phases [14-16]. Various types of QW have been invented in the theoretical studies, e.g., multiple-coin QW [17], QW in higher dimensions [18], and QW with a step-dependent coin [19, 20]. Recently, QW has been realized in experiment with different physical systems, such as trapped atoms or ions [21-24], optical systems [19, 25-27], and superconducting qubit [28]. Previous studies provide the transition from QW to CRW in different fashions, with decoherence [8, 29-32] and random phase approaches [33], with aperiodic QW [34], or with multiple-coin QW [17]. In this paper, we find that QW is one possible quantum extension of CRW from the single-coin interpretation. In the current version of QW, the state of the walker and the coin is described by the quantum state in the corresponding Hilbert space while the flipping process is considered as a unitary transform on the coin [5, 7]. The unitary transform engenders strong correlation between different steps. While in CRW, the flipping process eliminates the correlation between the walker and the coin, and every step is independent.

Inspired by the ensemble interpretation of CRW, we re-define quantum random walk (QRW) in this paper, where random means each step is uncorrelated. QRW can be regarded as an alternative quantum extension of CRW from the ensemble interpretation, while QW is the quantum extension of CRW from the single-coin interpretation. In QRW, the walker possesses many quantum coins, modeled as two-level systems prepared in the same initial state. The mathematical form of QRW is similar to the particular multiple-coin QW defined in Ref. [17], where the walker flips each coin at each step with a unitary coin operator, and moves according to the corresponding flipping result at each step. Similar to QW [5], the coin operator is chosen as Hadamard matrix. The walker’s position distribution in QRW/CRW is binomial due to the zero correlation between different steps, and that in QW is non-binomial due to the strong correlation. Especially, we study the walker’s position distribution in QRW with different coin’s initial states. For an initially decoherenced coin state, the walker’s position distribution recovers the result of CRW. For an initial coin state with coherence, the walker’s position is shown to follow the asymmetric binomial distribution, where the orientation of the walker is determined by the real part of the non-diagonal term of the initial coin state.

This paper is organized as follows. In Section 2, we revisit CRW in the language of the density matrix and give the two interpretation for CRW, the single-coin interpretation and the ensemble interpretation. In Section 3, we propose QRW as the quantum extension of CRW from the ensemble interpretation, and discuss the walker’s position distribution in 1D case. In Section 4, we analyze the correlation between different steps in CRW, QW, and QRW. We thus clarify that it is the difference in such correlation that makes the walker follows different position distribution in those walk models. In Section 5, we extend the framework of the new QRW to 2D lattice. Finally, the conclusion is given in Section 6.

2 Revisit classical random walk with density matrix approach

2.1 Single-coin interpretation

As a preparation, we first revisit CRW in the language of the density matrix. In the beginning, the position of the walker is set to the origin of the coordinates {|0\rangle }_w, while the coin stays at a mixed state

\begin{array}{}\text{(1)}& {\rho }_c=p_1^{(0)}{|1\rangle }_c\langle 1|+p_{-1}^{(0)}{|-1\rangle }_c\langle -1|\mathrm{,}\end{array}

where {|1\rangle }_c and {|-1\rangle }_c represent the heads and tails of the coin respectively, with the corresponding probability as p_1^{(0)} and p_{-1}^{(0)}=1-p_1^{(0)}. The non-diagonal term of the above density matrix is zero since the coin is completely classical without any coherence in CRW. Such that, the total initial state of the walker and the coin is

\begin{array}{}\text{(2)}& \rho (0)={|0\rangle }_w\langle 0|\otimes {\rho }_c\mathrm{.}\end{array}

At each step, the walker flips the coin and moves according to the flipping result

\begin{array}{}\text{(3)}& \rho (l+1)=\mathcal{T}\mathcal{C}\left[\rho (l)\right]\mathrm{,}\end{array}

where \rho (l) is the total density matrix of the walker and coin after the l-th step. Since the density matrix is always diagonal in CRW, we can write \rho (l) as

\begin{array}{}\text{(4)}& \rho (l)={\displaystyle \sum _{x=-\infty }^{\infty }}{\displaystyle \sum _{u=\pm 1}}{p}_{x\mathrm{,}u}(l){|x\rangle }_w\langle x|\otimes {|u\rangle }_c\langle u|\mathrm{,}\end{array}

where p_{x\mathrm{,}u}(l) is the probability that the walker arrives at x and the coin is at {|u\rangle }_c state after the l-th step. The flipping process \mathcal{C} only operates on the coin, and transforms the density matrix to \tilde{\rho }(l)=\mathcal{C}\left[\rho (l)\right] as

\begin{array}{}\text{(5)}& \tilde{\rho }(l)={\displaystyle \sum _{x=-\infty }^{\infty }}{\displaystyle \sum _{u=\pm 1}}{\tilde{p}}_{x\mathrm{,}u}(l){|x\rangle }_w\langle x|\otimes {|u\rangle }_c\langle u|\mathrm{,}\end{array}

with the new distribution {\tilde{p}}_{x\mathrm{,}u}(l)={\displaystyle {\sum }_{v=\pm 1}}{p}_{x\mathrm{,}v}(l)p(u|v). Here, p\left(u\right|v) denotes the conditional probability for flipping the coin from {|v\rangle }_c state to {|u\rangle }_c state with v\mathrm{,}u=\pm 1. For CRW, the state of the coin before and after flipping should be independent, which requires the conditional probability satisfies p(u|1)=p(u|-1). After flipping, the new distribution becomes

\begin{array}{}\text{(6)}& {\tilde{p}}_{x\mathrm{,}u}(l)=p_x(l)p_u\mathrm{,}\end{array}

where p_x(l)=p_{x\mathrm{,1}}(l)+p_{x\mathrm{,}-1}(l) gives the position distribution, and p_u=p(u|1)=p(u|-1) gives the coin distribution. It is clearly seen in Eq. (6) that the flipping process eliminates the correlation between the walker and the coin. Therefore, the total density matrix after flipping becomes a product state composed of the walker and the coin as

\begin{array}{}\text{(7)}& \tilde{\rho }(l)=\left[{\text{Tr}}_c\rho (l)\right]\otimes {\tilde{\rho }}_c\mathrm{,}\end{array}

where the flipped coin state {\tilde{\rho }}_c follows

\begin{array}{}\text{(8)}& {\tilde{\rho }}_c=p_1{|1\rangle }_c\langle 1|+p_{-1}{|-1\rangle }_c\langle -1|\mathrm{,}\end{array}

which is the same after flipping at different steps. For CRW without bias, all the conditional probabilities are equal to 1/2 and the flipped coin state becomes the fully mixed state {\tilde{\rho }}_c=1/2\left({|1\rangle }_c\langle 1|+{|-1\rangle }_c\langle -1|\right).

After flipping, the walker moves according to the flipped coin state {\tilde{\rho }}_c through the transition process \mathcal{T}\left[\tilde{\rho }(l)\right]=T\tilde{\rho }(l)T^{†} with the transition operator

\begin{array}{}\text{(9)}& T={\displaystyle \sum _{x=-\infty }^{\infty }}{\displaystyle \sum _{u=\pm 1}}{|x+u\rangle }_w\langle x|\otimes {|u\rangle }_c\langle u|\mathrm{,}\end{array}

which means the walker moves right (left) when the coin stays at {|1\rangle }_c ({|-1\rangle }_c). Thus, after the (l+1)-th step, the total density matrix \rho (l+1)=\mathcal{T}\left[\tilde{\rho }(l)\right] is explicitly obtained as

\begin{array}{}\text{(10)}& \rho (l+1)={\displaystyle \sum _{x=-\infty }^{\infty }}{\displaystyle \sum _{u=\pm 1}}{\tilde{p}}_{x-u\mathrm{,}u}(l){|x\rangle }_w\langle x|\otimes {|u\rangle }_c\langle u|\mathrm{.}\end{array}

Together with Eq. (4), we obtain the recursion relation

\begin{array}{}\text{(11)}& p_{x\mathrm{,}u}(l+1)={\tilde{p}}_{x-u\mathrm{,}u}(l)\mathrm{,}u=\pm 1.\end{array}

\begin{array}{}\text{(12)}& \rho (n)={\displaystyle \sum _{j=0}^n}{|2j-n\rangle }_w\langle 2j-n|\otimes p_1^j{p}_{-1}^{n-j}\left[\left(\begin{array}{c}n-1\\ j-1\end{array}\right){|1\rangle }_c\langle 1|+\left(\begin{array}{c}n-1\\ j\end{array}\right){|-1\rangle }_c\langle -1|\right]\mathrm{,}\end{array}

By tracing over the coin’s degree of freedom in \rho (n), we obtain the probability for the walker arriving at the position 2j-n after n steps as

\begin{array}{}\text{(13)}& P_{2j-n}(n)=\left(\begin{array}{c}n\\ j\end{array}\right)p_1^j{p}_{-1}^{n-j}\mathrm{.}\end{array}

This probability distribution, known as the binomial distribution, describes the walker’s position distribution in the CRW. The expectation and variance of the walker’s position [1] are given by

\begin{array}{}\text{(14)}& \langle x\rangle =n(p_1-p_{-1})\mathrm{,}\end{array}

and

\begin{array}{}\text{(15)}& \langle \text{Δ}{x}^2\rangle =\langle x^2\rangle -{\langle x\rangle }^2=4n{p}_1{p}_{-1}\mathrm{,}\end{array}

respectively. When p_1=p_{-1}=1/2, the binomial distribution of Eq. (13) is symmetric. In this case, the expected position of the walker after n steps is just the origin of the coordinates, which can be easily checked from Eq. (14). Otherwise, for p_1\ne p_{-1}, the position distribution is asymmetric, the walker will thus perform directional walking, i.e., \langle x\rangle \ne 0, and the CRW is directional.

2.2 Ensemble interpretation with many coins

In the above discussion, the flipping process \mathcal{C} eliminates the correlation between the coin and the walker at every step, and the flipped coin state {\tilde{\rho }}_c does not depend on the previous state \rho (k). The coin can be considered as independent coins for different steps. This is the ensemble interpretation for CRW. In the following discussion, we will obtain the same result of the position distribution based on the ensemble interpretation. Suppose the walker possesses many coins, the number of which is equal to the total step number n the walker will move. The total Hilbert space is the product of the walker’s space and the space for each coin

\begin{array}{}\text{(16)}& {\mathcal{H}}_{\text{T}}={\mathcal{H}}_w\otimes \underset{l=1}{\overset{n}{{\displaystyle \otimes }}}{\mathcal{H}}_{l\mathrm{,}c}\mathrm{.}\end{array}

At the beginning, all the coins satisfy the same distribution {\rho }_c by Eq. (1). Now, the initial density matrix of the walker and all coins reads

\begin{array}{}\text{(17)}& \rho (0)={|0\rangle }_w\langle 0|\otimes \underset{l=1}{\overset{n}{{\displaystyle \otimes }}}{\rho }_{l\mathrm{,}c}\mathrm{,}\end{array}

where l distinguishes different coins. At the l-th step, the walker flips the l-th coin and moves according to the flipping result, namely,

\begin{array}{}\text{(18)}& \rho (l)={\mathcal{T}}_l{\mathcal{C}}_l\left[\rho (l-1)\right]\mathrm{.}\end{array}

The flipping process {\mathcal{C}}_l transforms the l-th coin’s state from {\rho }_{l\mathrm{,}c} to {\tilde{\rho }}_{l\mathrm{,}c}, where {\tilde{\rho }}_{l\mathrm{,}c} follows the same form as Eq. (8). And the transition process

\begin{array}{}\text{(19)}& {\mathcal{T}}_l\left(\rho \right)=T_l\rho T_l^{†}\end{array}

is realized with the transition operator

\begin{array}{}\text{(20)}& T_l={\displaystyle \sum _{x=-\infty }^{\infty }}{\displaystyle \sum _{u=\pm 1}}{|x+u\rangle }_w\langle x|\otimes {|u\rangle }_l\langle u|\otimes \underset{j\ne l}{\overset{n}{{\displaystyle \otimes }}}{I}_j\mathrm{.}\end{array}

Here, I_j is the 2×2 identity matrix for the j-th coin. So that, the total density matrix after n step is \rho \left(n\right)={\displaystyle {\prod }_{l=1}^n}\left({\mathcal{T}}_l{\mathcal{C}}_l\right)\left[\rho (0)\right], which can be explicitly written as

\begin{array}{}\text{(21)}& \rho (n)={\displaystyle \sum _{\left\{u_l\right\}}}|{\displaystyle \sum _l}{u}_l{\rangle }_w\langle {\displaystyle \sum _l}{u}_l|\otimes \underset{l=1}{\overset{n}{{\displaystyle \otimes }}}\left(p_{u_l}{|u_l\rangle }_l\langle u_l|\right)\mathrm{.}\end{array}

In the summation, u_l=\pm 1 gives the direction for each step. By tracing over the space of all the coins, the probability for the walker arriving at the position x after n steps is obtained as

\begin{array}{}\text{(22)}& P_x(n)={\displaystyle \sum _{\left\{u_l\right\}:{\displaystyle {\sum }_l{u}_l=x}}}{\displaystyle \prod _{l=1}^n}{p}_{u_l}\mathrm{.}\end{array}

The limitation on the path {\displaystyle {\sum }_{l=1}^n}{u}_l=x requires (x+n)/2 right steps and (x-n)/2 left steps along n steps, and (x\pm n)/2 needs to be a positive integer otherwise the probability is zero. Then the probability at the position x is obtained explicitly as

\begin{array}{}\text{(23)}& P_x(n)=\{\begin{array}{ll}\left(\begin{array}{c}n\\ \frac{n+x}{2}\end{array}\right)p_1^{\frac{n+x}{2}}{p}_{-1}^{\frac{n-x}{2}}\mathrm{,}\hfill & n+x\text{is}\text{even}\mathrm{,}\hfill \\ \mathrm{0,}\hfill & n+x\text{is}\text{odd}\mathrm{.}\hfill \end{array}\end{array}

It is clearly seen from Eq. (23) that the walker’s position distribution is exactly the same as that of Eq. (12) in the one-coin case by setting j=(n+x)/2. Therefore, the equivalence between the one-coin interpretation and many-coin interpretation (ensemble interpretation) for CRW is proved. In further investigation below, we will extend the ensemble interpretation to quantum random walk to study the effect of the initial coherence of the coin.

3 Quantum random walk

In this section, we will discuss the QRW in one-dimensional space from the perspective of the ensemble interpretation of Section 2.2. For QRW, the total initial density matrix of the system is also described by Eq. (17), where the initial state of the l-th coin is now assumed to be

\begin{array}{}\text{(24)}& {\rho }_{l,c}=\left(\begin{array}{cc}{p}_1^{(0)}& \eta \\ {\eta }^{\ast }& p_{-1}^{(0)}\end{array}\right),\end{array}

where the non-diagonal term η characterizes the coherence in the coin state. We consider a unitary flipping process {\mathcal{C}}_l at the l-th step acting on the l-th coin

\begin{array}{}\text{(25)}& {\mathcal{C}}_l\left({\rho }_{l\mathrm{,}c}\right)=C_l{\rho }_{l\mathrm{,}c}{C}_l^{†}\equiv {\tilde{\rho }}_{l\mathrm{,}c}\mathrm{,}\end{array}

where {\tilde{\rho }}_{l\mathrm{,}c} is called the flipped state of the coin. The coin operator only acts on the l-th coin

\begin{array}{}\text{(26)}& C_l=I_w\otimes \underset{j\ne l}{\overset{n}{{\displaystyle \otimes }}}{I}_j\otimes {\tilde{C}}_l\mathrm{,}\end{array}

where {\tilde{C}}_l is a U(2) matrix for the l-th coin, and I_w is the identity matrix in the walker’s Hilbert space. For a general SU(2) matrix

\begin{array}{}\text{(27)}& {\tilde{C}}_l=\left(\begin{array}{cc}a& b\\ -b^{*}& a^{*}\end{array}\right)\mathrm{,}\end{array}

it follows from Eqs. (25) and (26) that the coin state after flipping becomes

\begin{array}{}\text{(28)}& {\tilde{\rho }}_{l\mathrm{,}c}={\displaystyle \sum _{u_l\mathrm{,}{v}_l}}{\rho }_{u_l{v}_l}{|u_l\rangle }_l\langle v_l|\mathrm{,}\end{array}

where u_l\mathrm{,}{v}_l=\pm 1 and

\begin{array}{}\text{(29)}& \begin{array}{l}{\rho }_{\mathrm{1,1}}=p_1^{(0)}{\left|a\right|}^2+{\eta }^{*}{a}^{*}b+\eta a{b}^{*}+p_{-1}^{(0)}{\left|b\right|}^2\mathrm{,}\\ {\rho }_{\mathrm{1,}-1}=a\left(a\eta +b{p}_{-1}^{(0)}\right)-b\left(a{p}_1^{(0)}+b{\eta }^{*}\right)\mathrm{,}\\ {\rho }_{-\mathrm{1,1}}=a^{*}\left(a^{*}{\eta }^{*}+b^{*}{p}_2^{(0)}\right)-b^{*}\left(a^{*}{p}_1^{(0)}+b^{*}\eta \right)\mathrm{,}\\ {\rho }_{-\mathrm{1,}-1}=p_{-1}^{(0)}{\left|a\right|}^2-{\eta }^{*}{a}^{*}b-\eta a{b}^{*}+p_1^{(0)}{\left|b\right|}^2\mathrm{.}\end{array}\end{array}

According to Eq. (18), the total density matrix after n-th step is

\begin{array}{}\text{(30)}& \rho (n)=\left({\displaystyle \prod _{l=1}^n}{T}_l{C}_l\right)\rho (0){\left({\displaystyle \prod _{l=1}^n}{T}_l{C}_l\right)}^{†}\mathrm{.}\end{array}

Since \left[C_l\mathrm{,}{T}_{l^{\prime }}\right]=0 commutes for different steps l\ne l^{\prime }, we first act all the coin operators on the initial state of the coins

\begin{array}{}\text{(31)}& {\displaystyle \prod _{l=1}^n}{C}_l{\rho }_{l\mathrm{,}c}{C}_l^{†}={\displaystyle \prod _{l=1}^n}{\tilde{\rho }}_{l\mathrm{,}c}\mathrm{.}\end{array}

Then, Eq. (30) is rewritten as

\begin{array}{}\text{(32)}& \rho (n)=\left({\displaystyle \prod _{l=1}^n}{T}_l\right)\left({|0\rangle }_w\langle 0|\otimes \underset{l^{\text{'}}=1}{\overset{n}{{\displaystyle \otimes }}}{\tilde{\rho }}_{l^{\text{'}}\mathrm{,}c}\right){\left({\displaystyle \prod _{l=1}^n}{T}_l\right)}^{†}\mathrm{.}\end{array}

Substituting Eq. (20) into Eq. (32), we obtain

\begin{array}{}\text{(33)}& \rho (n)={\displaystyle \sum _{\left\{u_l\mathrm{,}{v}_l\right\}}}|{\displaystyle \sum _{l=1}^n}{u}_l{\rangle }_w\langle {\displaystyle \sum _{l=1}^n}{v}_l|\otimes \underset{l=1}{\overset{n}{{\displaystyle \otimes }}}{\rho }_{u_l{v}_l}{|u_l\rangle }_l\langle v_l|\mathrm{.}\end{array}

The position distribution of the walker is determined by the diagonal elements of the density matrix of the flipped coin {\tilde{\rho }}_{l\mathrm{,}c}. The probability at the position x after n steps P_x(n)={\text{Tr}}_c\langle x|\rho (n){|x\rangle }_w is obtained from Eq. (33) by tracing over the freedom of the coins as

\begin{array}{}\text{(34)}& P_x(n)=\left(\begin{array}{c}n\\ \frac{n+x}{2}\end{array}\right){\rho }_{\mathrm{1,1}}^{\frac{n+x}{2}}{\rho }_{-\mathrm{1,}-1}^{\frac{n-x}{2}}\mathrm{,}\end{array}

where the corresponding transition probabilities {\rho }_{\mathrm{1,1}} and {\rho }_{-\mathrm{1,}-1} are given in Eq. (29). The walker’s position distribution by Eq. (34) for QRW is a binomial distribution with the probabilities {\rho }_{\mathrm{1,1}}\mathrm{,}{\rho }_{-\mathrm{1,}-1}, the same as the distribution of a directional CRW. In QRW, the walker flips different coins at different steps, hence each step is independent. While in QW, the position distribution is shown to be non-binomial distribution, which strongly depends on the initial coin state [5]. The non-binomial distribution comes from the strong correlation between different steps, which will be specifically discussed in Section 4. To briefly show the similarities and differences between CRW, QW and QRW, we illustrate their typical characteristics in Table 1.

In order to understand the origin of the bias in QRW, we need to figure out what determines the transition probabilities {\rho }_{\mathrm{1,1}} and {\rho }_{-\mathrm{1,}-1}. For the coin operator chosen as the Hadamard matrix

\begin{array}{}\text{(35)}& {\tilde{C}}_l=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)\mathrm{,}\end{array}

the transition probabilities follow as {\rho }_{\mathrm{1,1}}=1/2+\text{Re}\eta, and {\rho }_{-\mathrm{1,}-1}=1/2-\text{Re}\eta. Therefore, after n steps, the position distribution of the walker is given by Eq. (34) as

\begin{array}{}\text{(36)}& P_x(n)=\left(\begin{array}{c}n\\ \frac{n+x}{2}\end{array}\right){\left(\frac{1}{2}+\text{Re}\eta \right)}^{\frac{n+x}{2}}{\left(\frac{1}{2}-\text{Re}\eta \right)}^{\frac{n-x}{2}}\mathrm{,}\end{array}

which indicates that the bias is only determined by the real part of the non-diagonal term. When the real part of the non-diagonal term in the coin’s density matrix is zero, i.e., \text{Re}\eta =0, the result returns back to CRW without bias.

As a comparison, we demonstrate the position distribution of QRW, QW and CRW in Fig. 1. The total step number is n=100, and we only plot the probability at the even lattice since the probability at the odd lattice is zero. In Fig. 1(a), we consider an initially decoherenced coin state with p_1^{(0)}=p_{-1}^{(0)}=0.5, \eta =0. The position distribution of QRW (red curve with circles) returns to the one of CRW (black dashed line) while the position distribution of QW is non-binomial (green curve with squares). In Fig. 1(b), we choose the initial state with coherence by setting p_1^{(0)}=p_{-1}^{(0)}=\mathrm{0.5,}\eta =0.1. The positive non-diagonal term of the density matrix results in the right-hand movement for the QRW, namely, the coherence of the coin induces the asymmetry in the corresponding position distribution.

With the position distribution given by Eq. (36), we obtain the expectation and the variance of the walker’s position after n steps, according to Eqs. (14) and (15), as

\begin{array}{}\text{(37)}& \langle x\rangle =2n\text{Re}\eta \mathrm{,}\end{array}

and

\begin{array}{}\text{(38)}& \langle \text{Δ}{x}^2\rangle =n\left[1-{\left(2\text{Re}\eta \right)}^2\right]\mathrm{,}\end{array}

respectively. The above two relations of Eqs. (37) and (38) are the main results of this paper, which show that the coherence in the initial coin state results in the directional moving of the walker.

4 The correlation in quantum walk

In Sections 2 and 3, we have discussed the position distribution in CRW and QRW, and demonstrated that no correlation exists in CRW and QRW between different steps. In this section, we will show that the correlation indeed exists between different steps in QW, which is qualified through the covariance of the coin state between the initial time and final time.

In QW, the walker has only one coin, and the one-step evolution is described by Eq. (3) with the same transition process as in CRW. Different from CRW, the flipping process in QW is substituted by a unitary evolution \mathcal{C}\left(\rho \right)=C\rho C^{†} with the Hadamard matrix

\begin{array}{}\text{(39)}& C=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)\end{array}

operating on the coin state.

The density matrix of the walker and coin after n steps follows from Eq. (3) as

\begin{array}{}\text{(40)}& \rho (n)=(TC{)}^n\rho (0)(TC{)}^{†n}\mathrm{.}\end{array}

The transition operator T is defined in Eq. (9), and the initial state \rho (0) is given as Eq. (2). To describe the coin’s distribution after n steps, we perform a measurement of the Pauli operator {\sigma }_z on the coin, as {\sigma }_z{|\pm 1\rangle }_c=\pm {|\pm 1\rangle }_c. The expectation of {\sigma }_z after n steps is

\begin{array}{}\text{(41)}& \langle {\sigma }_z(n)\rangle =\text{Tr}\left[{\sigma }_z{\rho }_c(n)\right]\mathrm{,}\end{array}

where {\rho }_c(n) is the reduced density matrix of the coin after n steps.

To figure out the correlation between the initial time and final time, we perform a joint measurement of {\sigma }_z at the initial time. and after n steps, the expectation \langle {\sigma }_z(n){\sigma }_z(0)\rangle follows

\begin{array}{}\text{(42)}& \langle {\sigma }_z(n){\sigma }_z(0)\rangle ={\displaystyle \sum _{{\nu }_1\mathrm{,}{\nu }_2=\pm 1}}{\nu }_1{\nu }_2\text{Tr}\left[E_{{\nu }_2}U(n)E_{{\nu }_1}\rho (0)E_{{\nu }_1}{U}^{†}(n)E_{{\nu }_2}\right]\mathrm{,}\end{array}

where {\nu }_1({\nu }_2) gives the measurement result at the initial time (after n steps), and E_{{\nu }_{\alpha }}={|{\nu }_{\alpha }\rangle }_c\langle {\nu }_{\alpha }|\mathrm{,}\alpha =\mathrm{1,2} is the projection operator. Note that the non-diagonal term of \rho (0) vanishes in the initial measurement, i.e.,

\begin{array}{}\text{(43)}& E_{{\nu }_1}\rho (0)E_{{\nu }_1}={|0\rangle }_w\langle 0|\otimes p_{{\nu }_1}^{(0)}{|{\nu }_1\rangle }_c\langle {\nu }_1|\mathrm{.}\end{array}

Hence, we only need to consider for the diagonal initial state without coherence. The correlation in the coin is described by the covariance

\begin{array}{}\text{(44)}& \langle \text{Δ}\left[{\sigma }_z(n){\sigma }_z(0)\right]\rangle =\langle {\sigma }_z(n){\sigma }_z(0)\rangle -\langle {\sigma }_z(n)\rangle \langle {\sigma }_z(0)\rangle \mathrm{,}\end{array}

which is obtained explicitly as (detailed derivation in Appendix A)

\begin{array}{}\text{(45)}& \begin{array}{ll}\langle \text{Δ}\left[{\sigma }_z(n){\sigma }_z(0)\right]\rangle =\hfill & \left[1\text{}-\text{}\frac{\sqrt{2}}{2}\text{}+\text{}\frac{{\left(-1\right)}^n}{2\pi }{\displaystyle {\int }_{-\pi }^{\pi }}\frac{\cos \left(2{\omega }_{k}n\right)}{1+{\left(\cos k\right)}^2}\text{d}k\right]\hfill \\ \hfill & \times \left[1-{\left(p_1^{(0)}-p_{-1}^{(0)}\right)}^2\right]\mathrm{,}\hfill \end{array}\end{array}

with {\omega }_k=\arcsin \left(\sin k/\sqrt{2}\right)\mathrm{.} In the large n limit (n\to \infty), the integral in Eq. (45) diminishes due to the highly oscillated term \cos \left(2{\omega }_{k}n\right), so that the covariance approaches a constant

\begin{array}{}\text{(46)}& \underset{n\to \infty }{{\displaystyle \lim }}\langle \text{Δ}\left[{\sigma }_z(n){\sigma }_z(0)\right]\rangle =\left(1\text{}-\text{}\frac{\sqrt{2}}{2}\right)\left[1\text{}-\text{}{\left(p_1^{(0)}\text{}-\text{}{p}_{-1}^{(0)}\right)}^2\right]\mathrm{.}\end{array}

The non-zero covariance suggests that the correlation is generated through the flipping process, where the final coin state is correlated to the initial coin state.

In Fig. 2, we illustrate the covariance \langle \text{Δ}\left[{\sigma }_z(n){\sigma }_z(0)\right]\rangle of QW, QRW, and CRW, where the initial coin is chosen as the maximally mixed state with p_1^{(0)}=p_{-1}^{(0)}=0.5. It is clearly seen in Fig. 2 that the covariance of QW (green curve), given by Eq. (45), oscillates with the increasing of n, and gradually converges to a non-zero constant 1-1/\sqrt{2} (horizontal red dotted line), which is consistent with the analytical result of Eq. (46).

The non-zero covariance implies the coin state after n steps is correlated to the initial coin state, as shown in Table 1, which implies that the coin will remember its initial state for no matter how many steps the walker moves. The covariance of CRW and QRW is both zero (horizontal black dashed line). In CRW, we have \langle {\sigma }_z(n){\sigma }_z(0)\rangle =\langle {\sigma }_z(n)\rangle \langle {\sigma }_z(0)\rangle which leads the corresponding covariance to be zero, and indicates the flipping process at each step is independent. In QRW, the flipping process for different coins at different steps is independent, and thus the covariance of QRW \langle \text{Δ}\left[{\sigma }_z^n(n){\sigma }_z^1(0)\right]\rangle =\langle {\sigma }_z^n(n){\sigma }_z^1(0)\rangle -\langle {\sigma }_z^n(n)\rangle \langle {\sigma }_z^1(0)\rangle is also zero, where {\sigma }_z^1(0) measures the state for the first coin before walking, and {\sigma }_z^n(n) measures the state of the n-th coin after n steps. Therefore, we state that no correlation exists between different steps in CRW and QRW, while strong correlation exists in QW.

5 Quantum random walk in 2D lattice

With the theoretical framework of one-dimensional QRW established in Section 3, it is convenient for us to discuss QRW in two-dimensional lattice. Interestingly, unlike the 1D QRW, in the 2D case, the influence of the coherence in the coin’s initial state on the position distribution of the walker is more complicated, as demonstrated in this section.

For QRW in 2D lattice, the Hilbert space of the walker is expanded as \left\{{|r\rangle }_w|r=\left(x\mathrm{,}y\right)\mathrm{,}x\mathrm{,}y\in Z\right\}. And the Hilbert for each coin space is four dimension \left\{{|u\rangle }_1|u=R\mathrm{,}L\mathrm{,}U\mathrm{,}D\right\}, to determine the walker moves right R=(\mathrm{1,0}), left L=(-\mathrm{1,0}), up =(\mathrm{0,1}), and down D=(\mathrm{0,}-1) correspondingly. We still consider the walker initially stays at the origin of the coordinates {|(\mathrm{0,0})\rangle }_w, and has many coins prepared in the same initial state. In this situation, the initial density matrix for the walker and the coins follows

\begin{array}{}\text{(47)}& \rho (0)={|(\mathrm{0,0})\rangle }_w\langle (\mathrm{0,0})|\otimes \underset{l=1}{\overset{n}{{\displaystyle \otimes }}}{\rho }_{l\mathrm{,}c}\mathrm{,}\end{array}

where {\rho }_{l\mathrm{,}c} is the density matrix of the l-th coin, and can be represented by a general non-negative 4×4 Hermite matrix as

\begin{array}{}\text{(48)}& {\rho }_{k\mathrm{,}c}=\left(\begin{array}{cccc}{q}_1& {\eta }_{12}& {\eta }_{13}& {\eta }_{14}\\ {\eta }_{21}& q_2& {\eta }_{23}& {\eta }_{24}\\ {\eta }_{31}& {\eta }_{32}& q_3& {\eta }_{34}\\ {\eta }_{41}& {\eta }_{42}& {\eta }_{43}& q_4\end{array}\right)\mathrm{,}\end{array}

The flipping process and the transition process are the same as that described by Eq. (25) and Eq. (19). The coin operator C_l is also given by Eq. (26), where {\tilde{C}}_l can be chosen as a general U(4) matrix. We consider the Grover coin acting on the l-th coin [9, 35], i.e.,

\begin{array}{}\text{(49)}& {\tilde{C}}_l=\frac{1}{2}\left(\begin{array}{cccc}-1& 1& 1& 1\\ 1& -1& 1& 1\\ 1& 1& -1& 1\\ 1& 1& 1& -1\end{array}\right)\mathrm{.}\end{array}

Analogous to Eq. (20) in the 1D case, the position of the walker changes according to the state of the l-th coin {|u\rangle }_l with u=R\mathrm{,}L\mathrm{,}U\mathrm{,}D. So that, the transition operator for the 2D case reads

\begin{array}{}\text{(50)}& T_l={\displaystyle \sum _u}{\displaystyle \sum _r}{|r+u\rangle }_w\langle r|\otimes {|u\rangle }_l\langle u|\otimes \underset{j\ne l}{\overset{n}{{\displaystyle \otimes }}}{I}_j\mathrm{,}\end{array}

Similar to the 1D QRW, the position distribution is unique determined by the diagonal elements for the flipped coin {\tilde{\rho }}_{l\mathrm{,}c}={\mathcal{C}}_l\left({\rho }_{l\mathrm{,}c}\right), as noted by {\rho }_{uu}=\langle u|{\tilde{\rho }}_{l\mathrm{,}c}{|u\rangle }_l. The probabilities \left\{{\rho }_{uu}\right\} can be further expressed as

\begin{array}{}\text{(51)}& \left(\begin{array}{c}{\rho }_{RR}\\ {\rho }_{LL}\\ {\rho }_{UU}\\ {\rho }_{DD}\end{array}\right)=\frac{1}{4}\left(\begin{array}{cccc}1& -2& -2& -2\\ 1& -2& 2& 2\\ 1& 2& -2& 2\\ 1& 2& 2& -2\end{array}\right)\left(\begin{array}{c}1\\ {\zeta }_1\\ {\zeta }_2\\ {\zeta }_3\end{array}\right)\end{array}

with

\begin{array}{}\text{(52)}& {\zeta }_1=\text{Re}\left({\eta }_{12}\right)-\text{Re}\left({\eta }_{34}\right)\mathrm{,}\end{array}

\begin{array}{}\text{(53)}& {\zeta }_2=\text{Re}\left({\eta }_{13}\right)-\text{Re}\left({\eta }_{24}\right)\mathrm{,}\end{array}

\begin{array}{}\text{(54)}& {\zeta }_3=\text{Re}\left({\eta }_{14}\right)-\text{Re}\left({\eta }_{23}\right)\mathrm{.}\end{array}

Here, \left\{{\zeta }_i|i=\mathrm{1,2,3}\right\} is named the effective coherence, and is determined by the difference of the real part of the non-diagonal terms for the coin density matrix in Eq. (48).

In this case, the final position distribution of the walker follows (see Appendix B for detailed derivation)

\begin{array}{}\text{(55)}& P_{(x\mathrm{,}y)}(n)={\displaystyle \sum _j}{\text{ϒ}}_j\left(x\mathrm{,}y\mathrm{,}n\right){\rho }_{RR}^{\frac{j+x}{2}}{\rho }_{LL}^{\frac{j-x}{2}}{\rho }_{UU}^{\frac{n-j+y}{2}}{\rho }_{DD}^{\frac{n-j-y}{2}}\mathrm{,}\end{array}

where

\begin{array}{}\text{(56)}& {\text{ϒ}}_j\left(x\mathrm{,}y\mathrm{,}n\right)=\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}j\\ \frac{l+x}{2}\end{array}\right)\left(\begin{array}{c}n-j\\ \frac{n-l+y}{2}\end{array}\right)\mathrm{.}\end{array}

This is a quadrinomial distribution. Note that the summation here has a restriction on l, that is, l+x and n-l+y must be even. For those points (x\mathrm{,}y) not satisfied this restriction, the probability is zero. The non-negative condition for the density matrix requires that {\rho }_{uu} are all non-negative. Thus, there exists a limitation for the non-diagonal terms or the effective coherence \left\{{\zeta }_i\right\}. The allowed values for \left\{{\zeta }_i\right\} is limited in a regular tetrahedron, as illustrated in Fig. 3.

For {\zeta }_i=\mathrm{0,}i=\mathrm{1,2,3}, the position distribution of the walker for QRW in 2D lattice is symmetric with {\rho }_{uu}=\mathrm{0.25,}u=R\mathrm{,}L\mathrm{,}U\mathrm{,}D, as shown in Figs. 4(a) and (b). We also illustrate the walker’s position distribution with different \left\{{\eta }_{ij}\right\} in Fig. 4, where the various patterns show the diverse behaviors of the QRW in 2D lattice. In the simulation, the total step number is set as n=40, the diagonal terms in the coin’s initial density matrix are chosen as q_1=q_2=q_3=q_4=0.25, the non-diagonal terms {\eta }_{ij} are set as different values in the eight sub-figures.

Then we focus on the expectation and the variance of the walker’s position. Since each step is independent for the quadrinomial distribution, the expectation of the walker’s position follows from Eq. (55) as (detailed derivation in Appendix B)

\begin{array}{}\text{(57)}& \langle r\rangle =n(-{\zeta }_2-{\zeta }_3\mathrm{,}-{\zeta }_2+{\zeta }_3)\mathrm{,}\end{array}

The variances of the walker’s position along the x and y direction are

\begin{array}{}\text{(58)}& \langle \text{Δ}{x}^2\rangle =n\left[\frac{1}{2}-{\zeta }_1-{({\zeta }_2+{\zeta }_3)}^2\right]\mathrm{,}\end{array}

\begin{array}{}\text{(59)}& \langle \text{Δ}{y}^2\rangle =n\left[\frac{1}{2}+{\zeta }_1-{({\zeta }_2-{\zeta }_3)}^2\right]\mathrm{,}\end{array}

respectively. The total variance for r is

\begin{array}{}\text{(60)}& \langle \text{Δ}{r}^2\rangle =n\left(1-2{\zeta }_2^2-2{\zeta }_3^2\right)\mathrm{.}\end{array}

These relations are checked by the exact numerical results illustrated in Fig. 4. Eq. (57) shows that only {\zeta }_2 and {\zeta }_3 determine the orientation at x or y, while {\zeta }_1 does not. According to Eq. (51), p_x=p_{LL}+p_{RR}=1/2-{\zeta }_1, namely, {\zeta }_1 only determines the probability that the walker moves along x or y direction. Different from 1D case, where the non-zero η leads to the orientation of the walker, in 2D case, the effect of the coherence might cancel with each other for some suitable {\eta }_{ij} leading to zero effective coherence {\zeta }_i=0, as shown in Eqs. (52)–(54). This prediction is verified with the numerical example shown in Fig. 4(b), where the walker’s position follows symmetric distribution with non-zero {\eta }_{ij}. The above discovery reveals a fascinating feature of QRW in 2D lattice: even the coherence exists in the coin’s initial state, the walker may not perform directional walking.

For the probabilities {\rho }_{UU}={\rho }_{DD}=0 ({\rho }_{LL}={\rho }_{RR}=0), the walker moves only along the x (y) direction, in which situation the coherence satisfies {\zeta }_1=-1/\mathrm{2,}{\zeta }_2={\zeta }_3 ({\zeta }_1=1/2, {\zeta }_2=-{\zeta }_3). The orientation is then only determined by the effective coherence {\zeta }_3, and thus the QRW in 2D lattice in this case returns to the 1D QRW, as demonstrated in Fig. 4(c) [Fig. 4(d)].

6 Conclusion and discussion

In this paper, we extend classical random walk (CRW) to quantum random walk (QRW) via the ensemble interpretation, and clarify the relation between CRW, QRW, and QW (see Table 1). QRW is the quantum extension of CRW from the ensemble interpretation, while QW is the quantum extension of CRW from the single-coin interpretation.

Observed the difference of the position distribution for CRW/QRW (binomial) and QW (non-binomial), we interpret the different position distribution from the correlation aspect. In CRW, the flipping process in each step is independent, and thus no correlation exists between different steps. In QRW, the walker flips different coins at different steps. Still no correlation exists, and we retain the binomial distribution. In QW, the sequential unitary evolution engenders strong correlation between different steps. To qualify the correlation between different steps, we calculate the covariance between the initial coin state and final coin state in those walks. The result shows that the covariance is non-zero for QW while zero for CRW/QRW.

It is found that in QRW the walker performs directional walking once the coherence exists in the coin’s initial state. We further prove that, in such case, the stronger the coherence is, the more obvious the directional movement is, and the smaller the fluctuation of the walker’s position distribution is. Besides, QRW in 2D lattice is also studied, where the influence of coin state’s coherence on the walker’s position distribution is found to be more complicated (than that in the 1D case). Different from the one-dimensional case, even if there exists coherence in the coin’s initial state, the walker may not perform directional walking. This is because, under some special conditions, the influence of different non-diagonal terms in the coin’s density matrix on the position distribution of the walker may cancel each other out.

Generally, the main difference of QRW and QW can be understood by the following statement. In QRW, the quantum property refers to the initial coherence of the coin state, which results in a directional walk for the walker. While in QW, the sequential unitary operation on the single coin engenders strong correlation between different steps. This strong correlation results in the non-binomial distribution for the walker’s position.

References

[1] N. van Kampen, in: Stochastic Processes in Physics and Chemistry, 3rd Ed., North-Holland Personal Library, edited by N. V. Kampen, Elsevier, Amsterdam, 2007, p. ix

[2] Y. Aharonov, L. Davidovich, and N. Zagury, Quantum random walks, Phys. Rev. A 48(2), 1687 (1993)

[3] A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, and J. Watrous, in: Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing, ACM Press, 2001

[4] V. Kendo, Decoherence in quantum walks – a review, Math. Struct. Comput. Sci. 17(6), 1169 (2007)

[5] S. E. Venegas-Andraca, Quantum walks: A comprehensive review, Quantum Inform. Process. 11(5), 1015 (2012)

[6] G. Grimmett, S. Janson, and P. F. Scudo, Weak limits for quantum random walks, Phys. Rev. E 69(2), 026119 (2004)

[7] G. Abal, R. Siri, A. Romanelli, and R. Donangelo, Quantum walk on the line: Entanglement and nonlocal initial conditions, Phys. Rev. A 73(4), 042302 (2006)

[8] L. Ermann, J. P. Paz, and M. Saraceno, Decoherence induced by a chaotic enviroment: A quantum walker with a complex coin, Phys. Rev. A 73(1), 012302 (2006)

[9] N. Shenvi, J. Kempe, and K. B. Whaley, Quantum random-walk search algorithm, Phys. Rev. A 67(5), 052307 (2003)

[10] A. M. Childs, Universal computation by quantum walk, Phys. Rev. Lett. 102(18), 180501 (2009)

[11] N. B. Lovett, S. Cooper, M. Everitt, M. Trevers, and V. Kendon, Universal quantum computation using the discrete-time quantum walk, Phys. Rev. A 81(4), 042330 (2010)

[12] P. Witthaut, Quantum walks and quantum simulations with Bloch-oscillating spinor atoms, Rev. A 82(3), 033602 (2010)

[13] M. Mohseni, P. Rebentrost, S. Lloyd, and A. Aspuru-Guzik, Environment-assisted quantum walks in photosynthetic energy transfer, J. Chem. Phys. 129(17), 174106 (2008)

[14] T. Kitagawa, M. A. Broome, A. Fedrizzi, M. S. Rudner, E. Berg, I. Kassal, A. Aspuru-Guzik, E. Demler, and A. G. White, Observation of topologically protected bound states in photonic quantum walks, Nat. Commun. 3(1), 882 (2012)

[15] K. Wang, X. Qiu, L. Xiao, X. Zhan, Z. Bian, W. Yi, and P. Xue, Simulating dynamic quantum phase transitions in photonic quantum walks, Phys. Rev. Lett. 122(2), 020501 (2019)

[16] J. Z. Wu, W. W. Zhang, and B. C. Sanders, Topological quantum walks: Theory and experiments, Front. Phys. 14(6), 61301 (2019)

[17] T. A. Brun, H. A. Carteret, and A. Ambainis, Quantum walks driven by many coins, Phys. Rev. A 67(5), 052317 (2003)

[18] T. D. Mackay, S. D. Bartlett, L. T. Stephenson, and B. C. Sanders, Quantum walks in higher dimensions, J. Phys. Math. Gen. 35(12), 2745 (2002)

[19] A. Schreiber, K. N. Cassemiro, V. Potocek, A. Gábris, P. J. Mosley, E. Andersson, I. Jex, and C. Silberhorn, Photons walking the line: A quantum walk with adjustable coin operations, Phys. Rev. Lett. 104(5), 050502 (2010)

[20] S. Panahiyan and S. Fritzsche, Controlling quantum random walk with a step-dependent coin, New J. Phys. 20(8), 083028 (2018)

[21] M. Karski, L. Forster, J.M. Choi, A. Steffen, W. Alt, D. Meschede, and A. Widera, Quantum walk in position space with single optically trapped atoms, Science 325(5937), 174 (2009)

[22] F. Zähringer, G. Kirchmair, R. Gerritsma, E. Solano, R. Blatt, and C. F. Roos, Realization of a quantum walk with one and two trapped ions, Phys. Rev. Lett. 104(10), 100503 (2010)

[23] H. Schmitz, R. Matjeschk, C. Schneider, J. Glueckert, M. Enderlein, T. Huber, and T. Schaetz, Quantum walk of a trapped ion in phase space, Phys. Rev. Lett. 103(9), 090504 (2009)

[24] P. Xue, B. C. Sanders, and D. Leibfried, Quantum walk on a line for a trapped ion, Phys. Rev. Lett. 103(18), 183602 (2009)

[25] M. A. Broome, A. Fedrizzi, B. P. Lanyon, I. Kassal, A. Aspuru-Guzik, and A. G. White, Discrete single-photon quantum walks with tunable decoherence, Phys. Rev. Lett. 104(15), 153602 (2010)

[26] A. Peruzzo, M. Lobino, J. C. F. Matthews, N. Matsuda, A. Politi, K. Poulios, X.Q. Zhou, Y. Lahini, N. Ismail, K. Worhoff, Y. Bromberg, Y. Silberberg, M. G. Thompson, and J. L. OBrien, Quantum walks of correlated photons, Science 329(5998), 1500 (2010)

[27] H. Tang, X. F. Lin, Z. Feng, J. Y. Chen, J. Gao, K. Sun, C. Y. Wang, P. C. Lai, X.-Y. Xu, Y. Wang, L. F. Qiao, A. L. Yang, and X. M. Jin, Experimental two-dimensional quantum walk on a photonic chip, Sci. Adv. 4(5), eaat3174 (2018)

[28] Z. Yan, Y. R. Zhang, M. Gong, Y. Wu, Y. Zheng, S. Li, C. Wang, F. Liang, J. Lin, Y. Xu, C. Guo, L. Sun, C. Z. Peng, K. Xia, H. Deng, H. Rong, J. Q. You, F. Nori, H. Fan, X. Zhu, and J. W. Pan, Strongly correlated quantum walks with a 12-qubit superconducting processor, Science 364(6442), 753 (2019)

[29] T. A. Brun, H. A. Carteret, and A. Ambainis, Quantum random walks with decoherent coins, Phys. Rev. A 67(3), 032304 (2003)

[30] T. A. Brun, H. A. Carteret, and A. Ambainis, Quantum to classical transition for random walks, Phys. Rev. Lett. 91(13), 130602 (2003)

[31] K. Zhang, Limiting distribution of decoherent quantum random walks, Phys. Rev. A 77(6), 062302 (2008)

[32] J. D. Whitfield, C. A. Rodríguez-Rosario, and A. Aspuru-Guzik, Quantum stochastic walks: A generalization of classical random walks and quantum walks, Phys. Rev. A 81(2), 022323 (2010)

[33] J. Košík, V. Bužek, and M. Hillery, Quantum walks with random phase shifts, Phys. Rev. A 74(2), 022310 (2006)

[34] P. Ribeiro, P. Milman, and R. Mosseri, Aperiodic quantum random walks, Phys. Rev. Lett. 93(19), 190503 (2004)

[35] L. K. Grover, Quantum mechanics helps in searching for a needle in a haystack, Phys. Rev. Lett. 79(2), 325 (1997)

Rights & permissions

Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature 2020