Quantum stochastic walks: A generalization of classical random walks and quantum walks

We introduce the quantum stochastic walk (QSW), which determines the evolution of a generalized quantum-mechanical walk on a graph that obeys a quantum stochastic equation of motion. Using an axiomatic approach, we specify the rules for all possible quantum, classical, and quantum-stochastic transitions from a vertex as defined by its connectivity. We show how the family of possible QSWs encompasses both the classical random walk (CRW) and the quantum walk (QW) as special cases but also includes more general probability distributions. As an example, we study the QSW on a line and the glued tree of depth three to observe the behavior of the QW-to-CRW transition.

Figure 1

The QSW is a quantum stochastic process defined by a set of Axioms that describe the connectivity of an underlying graph. The family of possible QSWs encompasses the CRW and the QW as limiting cases. QSWs can be used to generate walks that continuously interpolate between QW and CRW and, therefore, can be employed to analyze algorithmic classical-to-quantum transitions. The family of QSWs also describes more general quantum stochastic processes with a behavior that cannot be recovered by the QW and CRW approaches.

Figure 2

The distance between the classical and purely dephased QW on the line is plotted as a function of the dephasing strength $\omega$ at fixed time $t=5$ ($\omega$ and $t$ in atomic units). The Euclidean distance metric between two probability mass functions, $p^{(1)}\hspace{0.5em}{p}^{(2)}$, is defined by $d(p^{(1)}\hspace{0.5em}{p}^{(2)})=\sqrt{{\sum }_i(p_i^{(1)}-p_i^{(2)}){}^2}$, and the abscissa parameter, $\omega$, is defined in Eq. (5) with the set $\{L_k\}=\{|k\rangle \langle k|\}$ as the pure dephasing operators. Notice that pure dephasing does not provide a mapping to the CRW.

Figure 3

Probability distributions of a walker starting at position $0$ of an infinite line defined by $M$ are shown at time $t=5$ (atomic units). The heavy line (red) represents the QW, the thin line (black) represents the CRW, and the dotted line (blue) represents a choice of a QSW due to a single operator $L={\sum }_{\kappa ,{\kappa }^{\prime }}{M}_{\kappa }^{{\kappa }^{\prime }}|\kappa \rangle \langle {\kappa }^{\prime }|$ whose distribution cannot be obtained from the classical or quantum walks. (a) The transition of the QW to the CRW is shown. The diagonal elements of the density matrix (Population) are plotted as a function of the vertex of the walker (Position) and a coupling parameter $\omega$. When $\omega =0$ the evolution is due only to the Hamiltonian, and when $\omega =1$ the Hamiltonian dynamics are not present with the environmental dynamics responsible for dynamics. (b) The transition of the QW to the QSW is shown.

Figure 4

Transport probability through a glued tree of depth three as a function of time (atomic units) and classical-quantum mixing parameter $\omega$. In both figures, the line with $\omega =1$ corresponds to the CRW, and the line with $\omega =0$ corresponds to the QW. The lines with $\omega =(0.16,0.12,0.08,0.04)$ correspond to mixed quantum-classical walks that have performance worse than the CRW, the lines with $\omega =(0.96,0.88,0.72,0.56)$ are the mixed classical-quantum walks that perform better than the CRW, and the $\omega =0.4$ line is the worst-performing mixed walk. (a) The probability of being at the exit site as a function of time is shown for various mixing parameters of the classical and quantum walks. (b) The time average of the probability of being at the exit site. For QWs, no stationary distribution exists due to unitary evolution; however, the time average of the probability distribution of a QW converges [1].

Figure 5

Plot of the time-averaged population for transport through the $G_3$ tree at three fixed times, $t=\{5,10,25\}$, as a function of the decoherence strength $\omega \in [0,1]$ (atomic units). When $\omega =1$, the classical walk is obtained, and when $\omega =0$, the unitary walk is recovered. Notice that the probability is not a strictly decreasing function of the decoherence.

Figure 6

Examples of glued trees of depth one, two, and three. The glued tree of depth $n$ consist of two binary trees of depth $n$ connected at the leaves.