Introduction

Quantum walks (QWs) are the quantum-mechanical counterpart of classical random walks (RWs) [1,2,3,4,5]. If the walker evolves in discrete temporal steps, we talk about discrete-time QWs, while in continuous-time quantum walks (CTQWs) time is a real parameter [6, 7]. In this work, we focus on continuous-time quantum walks. Quantum walks on graphs are used to describe the transport of energy or information across a given structure in several physical, chemical and biological systems [8,9,10,11]. They also proved to be powerful tools for building quantum algorithms [12, 13] and provide a universal model of quantum computation [14,15,16].

Experimental implementations of quantum walks unavoidably involve the interaction with an external environment, and a question arises on whether, and to which extent, the open quantum system dynamics of a quantum walker is detrimental to its quantum features. In turn, the thorough characterization of decoherence effects in CTQWs is a key ingredient for their use in quantum technology and, in particular, to envisage strategies that may mitigate or cancel out noise. Several studies investigated how noise stemming from the interaction between the system and the environment affects the dynamics of quantum walks [17,18,19,20,21,22,23,24]. Different effects may emerge, such as localization, transition towards a classically distributed walker [20, 21, 23], but also an improvement in excitation transport efficiency [18, 19, 22, 24]. However, if a QW loses all of its quantum features and becomes a classical RW, then any potential quantum advantage related to the quantum process is lost as well.

In this paper, we study if decoherence can turn a continuous-time quantum walk over a graph into the corresponding classical random walk. We refer to this phenomenon as classicalization. In order to make our analysis quantitative, we use a fidelity-based measure of non-classicality, referred to as quantum-classical distance, that quantifies the differences between the dynamics of a quantum and a classical walker on a given graph [25]. Recently, this quantity has been also used as a tool to design optimal quantum walks [26]. We use this distance to assess if and to which extent decoherence makes the quantum evolution more similar to its classical counterpart, at least asymptotically, with respect to the ideal noiseless case.

In the following, we study three different models of decoherence. First, we investigate intrinsic decoherence [27], i.e. decoherence in the Hamiltonian basis, then we shift our focus to two different mechanisms of decoherence in the position basis. In particular, we consider dephasing induced by the Haken–Strobl master equation [28] and then we analyse the interplay of unitary and irreversible dynamics using the quantum stochastic walk framework [29]. We show that intrinsic decoherence is not able to completely classicalize the walker: residual quantumness is preserved, and the quantum walker dynamics departs from the corresponding classical one. We give the analytic expressions for the asymptotic value of the quantum-classical distance over the complete, cycle and star graphs. On the other hand, the two models of decoherence in the position basis completely suppress the quantum features of the coherent process, nullifying the quantum-classical distance.

As we will see in detail, some general properties of the quantum-classical distance do not depend on the decoherence model: it reaches an asymptotic value which does not depend on the decoherence rate and its qualitative behaviour is not dependent on the size of the graph, nor the considered topology. On the other hand, we show that the rate of convergence of the quantum-classical distance to its asymptotic value is influenced by the noise parameter with a non-universal behaviour. For intrinsic decoherence and for the quantum stochastic walk model, we observe that a larger value of the decoherence parameter leads to a faster convergence, whereas for the Haken–Strobl master equation we see an inversion, such that after a threshold value of the noise rate the quantum-classical distance decays slower.

The paper is organized as follows. In Sect. 2, we establish notation and briefly review classical and quantum walks, the master equation approach for noisy quantum walks, and the quantum-classical distance. In Sect. 3, we investigate the effects of intrinsic decoherence on CTWQs, while Sect. 4 is devoted to the study of decoherence in the position basis. In Sect. 5 we draw conclusions and provide some concluding remarks.

Preliminary concepts

Let us consider a finite, simple, undirected, connected graph G(V,E), where V is the set of vertices, also called nodes, and E the set of edges. The cardinality of V sets the dimension of the graph, i.e. the number of nodes \(N=\vert V\vert \). A graph is uniquely identified by its Laplacian matrix \(L=D-A\), where A is the adjacency matrix and D is a diagonal degree matrix [30]. In particular, \(A_{jk}=1\) if vertices j and k are connected (with \(j\ne k\)), and zero otherwise, and \(D_{jj}=d_j\) is the vertex degree of the node, i.e. the number of edges connecting the j-th node to the others. L is a positive semi-definite matrix and completely determines the classical evolution of a walker on a graph. The dynamics of a classical walker initially localized on node j may be described by the diagonal density matrix

$$\begin{aligned} {\mathcal {E}}_C [\rho _j](t)=\sum _{k=1}^{N} p_{kj}(t) \vert k\rangle \!\langle k\vert . \end{aligned}$$

(1)

where \(p_{kj}(t)=\langle k\vert e^{-\nu L t} \vert j\rangle \) is the classical transition probability from node j to node k, \(\nu \) is the transition rate, \(\lbrace \vert k\rangle \rbrace _{k=1}^N\) is the complete orthonormal basis which describes localized states of the walker on the N nodes of the graph and \(\rho _j = \vert j\rangle \!\langle j\vert \) is the initial state. The map \({\mathcal {E}}_C\) describes a continuous-time random walk (CTRW) on the graph G. On the other hand, the purely coherent quantum evolution of a CTQW is obtained by promoting the Laplacian to the system's Hamiltonian \(H =\nu L\) [7] (though this is not the only possible choice for a CTQW generator [5, 31]). Without loss of generality we can set the transition rate to \(\nu = 1\) and \(\hbar =1\). The unitary evolution of the quantum walk is thus given by \(\left| \psi (t)\right\rangle =e^{-iHt}\left| j\right\rangle \), where \(\left| j\right\rangle \) denotes the initial localized state.

Noisy quantum walks

If the walker interacts with an external environment, its evolution is no longer unitary and can be described, within the Markovian approximation, by a master equation in the Lindblad form, i.e.

$$\begin{aligned} \frac{\mathrm{d}\rho (t)}{\mathrm{d}t}&=-i\left[ L,\rho (t) \right] +\sum _{k}\gamma _k {\mathcal {D}}\left[ O_k \right] \rho (t)\,. \end{aligned}$$

(2)

Here \({\mathcal {D}}\) is the Linblad superoperator, defined as \({\mathcal {D}}\left[ A\right] \rho = A\rho A^{\dagger }-\frac{1}{2}\lbrace A^{\dagger }A,\rho \rbrace \) with the brackets \(\{A,B\}=AB+BA\) denoting the usual anticommutator, \( O_k \) are the Lindblad operators and \(\gamma _k \ge 0\). The main goal of this work is to investigate if, and to which extent, the presence of environmental noise makes the quantum evolution of a walker on a graph more similar to its classical counterpart [that is described by Eq. (1)], compared to the ideal noiseless scenario. In particular, we consider three models of noisy quantum walks whose dynamics is induced by three master equations that describe dephasing in some basis of choice.

At first, we focus on decoherence in the energy basis, corresponding to the following master equation

$$\begin{aligned} \frac{\mathrm{d}\rho (t)}{\mathrm{d}t}&= -i\left[ L,\rho (t) \right] -\frac{\gamma }{2} \big [L,[L,\rho (t)]\big ] \, , \end{aligned}$$

(3)

which describes intrinsic decoherence of a quantum system. It has been derived [27] by assuming that at short timescales a quantum system evolves as a stochastic sequence of random unitary operators. The parameter \(\gamma \ge 0\) is referred to as the decoherence rate, and L is the graph Laplacian. From an operational point of view, intrinsic decoherence corresponds to a randomized quadratic perturbation [32].

We then consider two different models of decoherence in the site (position) basis. The first one corresponds to the Haken–Strobl master equation [28], which reads

$$\begin{aligned} \frac{\mathrm{d}\rho (t)}{\mathrm{d}t} =&-i\left[ L,\rho (t)\right] +\gamma \,\sum _k{\mathcal {D}}[P_k]\rho (t) \, , \end{aligned}$$

(4)

where \(\gamma \ge 0\) is the decoherence rate and \(P_k = |{k}\rangle \langle {k}|\) are the site-projector operators. It can be shown [28] that the Haken–Strobl master equation corresponds to a system with a tight-binding Hamiltonian affected by stochastic noise describing thermal Gaussian fluctuations of the on-site energies. The decoherence parameter \(\gamma \) is related to the variance of the thermal fluctuations. The Haken–Strobl master equation finds applications in the description of a single excitation transport, e.g. in an N-site chain subject to dephasing induced by the interaction with a fluctuating environment [33].

A second model of decoherence in the site basis is provided by the quantum stochastic walk (QSW) approach [29]. The QSW formalism axiomatically generalizes a classical random process to a quantum stochastic process, where the topology of the underlying graph imposes constraints on the dynamical evolution of the walker. It is described by the following master equation [34]

$$\begin{aligned} \frac{\mathrm{d}\rho (t)}{\mathrm{d}t} = -(1-p)\,i\,[L,\rho (t)]+p\sum _{kj} {\mathcal {D}}[P_{kj}]\rho (t) \,. \end{aligned}$$

(5)

Here \(p\in [0,1]\) quantifies the interplay between unitary (\(p=0\)) and irreversible (\(p=1\)) dynamics and the \(P_{kj}=L_{kj}|{k}\rangle \langle {j}|\) are the jump operators, with \(L_{kj}=\left\langle k\right| L\left| j\right\rangle \). This model generalizes both the QW and the RW on the graph by continuously interpolating between the two dynamics with a single real mixing parameter p. This model has been employed to investigate the role of environmental noise in assisting the transport of energy or information across a network, such as a light-harvesting complex in a photosynthetic process [19, 22, 24, 34].

The quantum-classical distance

In order to compare the dynamics of different quantum walks models, and to quantify the differences between quantum and classical evolutions, we use a recently introduced dynamical distance based on fidelity [25]. Given two dynamical maps, describing a classical \({\mathcal {E}}_C[\rho _{cl}]\) and a quantum \({\mathcal {E}}_Q[\rho _{cl}]\) evolution, the QC-distance \(D_{\text {QC}}(t)\) between them is defined as [25]:

$$\begin{aligned} D_{\text {QC}}(t) \doteq 1-\underset{\rho _{cl}}{\text {min}}\, {\mathcal {F}}\left( {\mathcal {E}}_C[\rho _{cl}](t),{\mathcal {E}}_{Q}[\rho _{cl}](t)\right) \,, \end{aligned}$$

(6)

where \(\rho _{cl}\) is an initial classical state of the walker, i.e. a statistical operator diagonal in the node basis, and \({\mathcal {F}}({\mathcal {E}}_C[\rho _{cl}],{\mathcal {E}}_Q[\rho _{cl}])\) is the quantum fidelity between the classically and quantum-evolved states, i.e. \({\mathcal {F}}(\rho ,\sigma )=\left[ \hbox {Tr}\sqrt{\sqrt{\rho }\sigma \sqrt{\rho }}\right] ^2\). The minimization in Eq. (6) is achieved, for every graph, by a localized state \(\rho _j\) [25]; hence, we shall focus on such initial states only. An interesting feature of this measure of non-classicality is that, for noiseless unitary quantum dynamics, it has a horizontal asymptote which depends only on the total number of nodes N, i.e. \(\lim _{t\rightarrow \infty }D_{\text {QC}}(t)=1-\frac{1}{N}\). In the next section, we use the QC-distance as a figure of merit to assess the robustness of CTQW against decoherence. In particular, we compute the QC-distance between the classically evolved state \({\mathcal {E}}_C[\rho _j](t)\) defined in Eq. (1) and the quantum state described by a CPTP-map modelling decoherence in some basis of choice.

Decoherence in the energy basis

Let us consider a quantum walker subject to the intrinsic decoherence process described by the master equation (3). The solution for an initial localized state \(\rho _j=|{j}\rangle \langle {j}|\), is given by

$$\begin{aligned} {\mathcal {E}}_{L}&[ \rho _j ](t) = \sum _{n,p} \langle \lambda _n\vert \rho _j \vert \lambda _p\rangle e^{-i(\lambda _n -\lambda _p)t-\frac{1}{2}\gamma (\lambda _n - \lambda _p)^2 t} \vert \lambda _n\rangle \!\langle \lambda _p \vert \, , \end{aligned}$$

(7)

where \(\lbrace \lambda _n \rbrace _{n=1}^N\) and \(\lbrace \vert \lambda _n \rangle \rbrace _{n=1}^N\) are, respectively, the eigenvalues and eigenvectors of L, i.e. \(L\vert \lambda _n \rangle = \lambda _n \vert \lambda _n \rangle \). Equation (7) represents decoherence in the energy basis and may also be expressed in the following form:

$$\begin{aligned} {\mathcal {E}}_L[\rho _j](t)=\int \mathrm{d}y \, g(y\vert \, 0,\sigma ) \,\,e^{-iL(t+y)} \rho _j e^{iL(t+y)}\, , \end{aligned}$$

(8)

where \(g(y\vert \,0,\sigma )\) is a Gaussian probability distribution function with standard deviation \(\sigma \) and zero mean value. The connection between the two representations is achieved by the correspondence \(\sigma ^2=\gamma t\). This map can thus be reinterpreted as a coarse graining in time of the ideal quantum evolution.

We now use Eq. (7) to compute the QC-distance \(D_{\text {QC}}(t)\) and analyse its behaviour for relevant graph topologies. In the long-time limit, the classical transition probability distribution \(p_{kj}(t)\) tends to the flat distribution, i.e. for \(t\gg 1\) we obtain

$$\begin{aligned} {\mathcal {E}}_C [\rho _{j}](t) \simeq \frac{\mathbb {I}}{N} \quad \forall \rho _{j}. \end{aligned}$$

Furthermore, in the same limit, we see from Eq. (7) that, because of the exponential damping, the only terms of the sum that survive asymptotically are those that satisfy the condition \(\lambda _n=\lambda _p\). We can write the expression for the asymptotic quantum map \({\mathcal {E}}_L[\rho _j](t_{\infty })\equiv {\mathcal {E}}_\infty [\rho _j]\) as follows

$$\begin{aligned} {\mathcal {E}}_\infty [\rho _j]=\sum _{n,p} \delta _{\lambda _n \lambda _p}\,\left\langle \lambda _n\right| \rho _j\left| \lambda _p\right\rangle |{\lambda _n}\rangle \langle {\lambda _p}| . \end{aligned}$$

(9)

The asymptotic quantum-classical distance reads

$$\begin{aligned} D_{\text {QC}}(t_{\infty })= 1-\min _{\rho _j}\,\left[ \left( \hbox {Tr}\sqrt{\frac{{\mathcal {E}}_\infty [\rho _j]}{N}} \right) ^2\right] . \end{aligned}$$

(10)

\(D_{\text {QC}}(t_{\infty })\) thus depends on the graph topology but not on the decoherence parameter \(\gamma \), which only affects the rate of convergence to its asymptotic value.

From the asymptotic expression in Eq. (9), we see that decoherence in the energy basis cannot turn the quantum evolution of CTQW into a classical random walk for any graph with a degenerate Laplacian spectrum. Indeed, the QC-distance is zero if and only if the stationary quantum state is the maximally mixed state. From the expression of \({\mathcal {E}}_\infty [\rho _j]\) it follows that, if the spectrum of L has eigenvectors corresponding to degenerate eigenvalues \(\lambda _n=\lambda _p\) with \(\left\langle \lambda _n\right| \rho _j\left| \lambda _p\right\rangle \ne 0\), then the density matrix has nonzero off-diagonal elements and the QC-distance does not vanish. Indeed, the absence of off-diagonal terms in the quantum density matrix is a necessary, but not sufficient, condition to classicalize the walker. The existence of degenerate Laplacian eigenvalues is thus a key element in the classicalization of the QW, and it is related to the symmetries of the underlying graph, as we show in Appendix A.

Let us conclude this section with few comments about the rate of convergence of the QC-distance to its asymptotic value. From the expression of the classical transition probability from node j to node k

$$\begin{aligned} p_{kj}(t)=\langle k\vert e^{ -L t} \vert j\rangle = \sum _{n} e^{-\lambda _n t} \langle k\vert \lambda _n\rangle \!\langle \lambda _n\vert j\rangle \end{aligned}$$

(11)

it follows that the convergence of the classically evolved state \({\mathcal {E}}_C[\rho _j](t)\) to the maximally mixed state is governed by the smallest nonzero eigenvalue which is known as the Fiedler value \(\lambda _F\). The leading term in Eq. (11) is \(e^{- \lambda _F t}\), and consequently, the bigger the Fiedler value, the faster the convergence of the classical distribution to the uniform one. In the quantum case instead, the rate of convergence to the stationary state is determined by the smallest nonzero value of the energy gap \((\lambda _n - \lambda _p)^2\), as can be seen from Eq. (7). The parameter \(\gamma \) determines the rate of convergence, once \((\lambda _n - \lambda _p)^2\) is fixed. For the three classes of graphs, we are going to consider in this paper, i.e. complete, cycle and star graphs, the minimum of this gap is achieved by the difference of the two smallest eigenvalues squared, namely when one is zero and the other is the Fiedler value. However, this is no longer true for a general topology.

Complete graph

The complete graph is the graph corresponding to maximal connectivity. The Laplacian matrix of a an N-node complete graph has the expression \(L=N\mathbb {I}-\mathbb {J}\), where \(\mathbb {J}\) is the unit matrix, i.e. its elements are all ones, and \(\mathbb {I}\) is the identity matrix. In Fig. 1a, we show the QC-distance of noisy (dephased) CTQWs on a complete graph with \(N=5\) nodes, for different values of the decoherence rate \(\gamma \). All the nodes of a complete graph are equivalent, and hence without loss of generality and for future convenience we set the initial state to \(\rho _N=\vert N\rangle \!\langle N\vert \).

Fig. 1
figure 1

Quantum-classical distance computed for different values of the dephasing parameter, for different graphs with \(N=5\) nodes: a complete graph, b cycle graph and c star graph. Dashed pink line indicates the asymptotic value \(D_{\text {QC}}(t_{\infty })\) in the three considered cases. The inset of figure c shows the \(D_{\text {QC}}(t;j)\) starting from the two different kind of nodes for the star graph: central (solid lines) and outer (dashed lines). t is a dimensionless time

Full size image

At the initial time \(D_{\text {QC}}(0)=0\), the distance grows with time, and eventually reaches an horizontal asymptote, not necessarily monotonically depending on the value of \(\gamma \). This asymptote does not depend on the decoherence parameter which, in turn, only affects the rate of convergence of \(D_{\text {QC}}\) to its asymptotic value. In particular, as \(\gamma \) gets bigger the distance converges more rapidly. For vanishing \(\gamma \), the QC-distance for the noiseless case is recovered. We observe that intrinsic decoherence indeed brings the quantum walk closer to the classical random walk as the decoherence rate increases. However, due to the degeneracy of the spectrum, the QW does not become fully classical and the QC-distance remains positive at all times \(t>0\). Notice that the qualitative behaviour of the QC-distance does not depend on the number of nodes N, i.e. a behaviour similar to that of Fig. 1 is observed for every N.

Let us now prove that the asymptotic value of the QC-distance does not depend on the rate \(\gamma \), but rather it is a function of N only. The Laplacian spectrum of an N-node complete graph reads \(\lambda _1=\cdots =\lambda _{N-1} = N\) and \(\lambda _N=0\). The corresponding eigenvectors are

$$\begin{aligned} \vert \lambda _k\rangle =\frac{1}{\sqrt{N}}\sum _{j=1}^N e^{i\frac{2\pi k}{N}j}\vert j\rangle . \end{aligned}$$

(12)

In order to obtain the stationary quantum-evolved state in Eq.(9), we first need to find the values of n and p for which \(\lambda _n=\lambda _p\) holds. For the complete graph, this condition is satisfied when \(n\ne N \wedge p\ne N\) or \(n = p = N\). Hence, it follows that the stationary quantum state reads

$$\begin{aligned} \rho _{\infty }{=} \frac{1}{N}\vert \lambda _N\rangle \!\langle \lambda _N \vert + \frac{1}{N} \sum _{n,p=1}^{N-1} \vert \lambda _n \rangle \!\langle \lambda _p \vert \,, \end{aligned}$$

(13)

where we used \(\langle N\vert \lambda _k \rangle =\frac{1}{\sqrt{N}}\,\, \forall k\). We can now compute the asymptotic value of the QC-distance:

$$\begin{aligned} D_{\text {QC}}(t_{\infty }) =&1-\frac{1}{N^2}\left( 1+\sqrt{N-1} \right) ^2. \end{aligned}$$

(14)

Indeed the asymptotic value does not depend on the decoherence rate \(\gamma \), but only on the number of nodes N. Notice that for \(N\rightarrow \infty \) we retrieve the asymptote of the noiseless case, i.e. \(1-\frac{1}{N}\). This suggests that, as the size of the complete graph grows, the effect of intrinsic decoherence becomes negligible.

Cycle graph

The cycle graph is a one-dimensional lattice with periodic boundary conditions, i.e. it is a regular graph with vertex degrees \(d_j=2\quad \forall j\). The Laplacian for a N-node cycle graph is a tridiagonal matrix with off-diagonal elements \(L_{j,j+1}=L_{j+1,j}=-1\) \( \forall j=1,\dots ,N-1\) and diagonal elements \(L_{jj}=2\) \(\forall j\). As for the previous case, and without loss of generality, we choose \(\rho _j=|{N}\rangle \langle {N}|\) as initial localized state of the walker.

The behaviour of \(D_{\text {QC}}(t)\) is qualitatively similar to the complete graph, see Fig. 1b, i.e. intrinsic decoherence brings the quantum evolution closer to the classical one compared to the noiseless case. However, although some quantumness is lost, the degeneracy of the Laplacian's spectrum prevents a full classicalization of the QW. Depending on the value of \(\gamma \), the QC-distance may reach its asymptotic value non-monotonically, i.e. displaying a maximum at shorter times, or monotonically. We observed that, for a fixed number of nodes, the asymptotic value of \(D_{\text {QC}}(t)\) is smaller with respect to the case of the complete graph.

To calculate the asymptotic value \(D_{\text {QC}}(t_{\infty })\), we need \({\mathcal {E}}_\infty [\rho _j]\) and, in turn, the values of n and p that fulfil the condition \(\lambda _n=\lambda _p\). The eigenvalues of the N-cycle graph Laplacian are \(\lambda _n=2\left[ 1-\cos \left( \frac{2\pi n}{N}\right) \right] \), with \(n=1,\cdots ,N\), and the corresponding eigenstates coincide with those in Eq. (12). In particular, \(\lambda _n=\lambda _p\) is satisfied when \(n=p\) or when \(n=N-p\) with \(p\ne N\). In order to explicitly evaluate \(D_{\text {QC}}(t_{\infty })\), we study the odd and the even N cases separately, since when N is even there are \(\frac{N}{2}-1\) couples of equal eigenvalues, while when N is odd there are \(\frac{N-1}{2}\) of them. With this in mind, we obtain the stationary quantum state

$$\begin{aligned} {\mathcal {E}}_\infty [\rho _j] = \frac{1}{N} \mathbb {I} + \frac{1}{N} \sum _{p=1}^{N-1}\vert \lambda _{N-p}\rangle \!\langle \lambda _{p}\vert \end{aligned}$$

(15)

where \(p\ne \frac{N}{2}\) if N is even. After diagonalizing \({\mathcal {E}}_\infty [\rho _j]\), the asymptote of the QC-distance can be easily computed. When N is even, we obtain

$$\begin{aligned} D_{\text {QC}}(t_{\infty }) = 1-\frac{1}{N^2}\left( 2+\frac{N-2}{\sqrt{2}} \right) ^2 \,, \end{aligned}$$

(16)

while for odd N we get

$$\begin{aligned} D_{\text {QC}}(t_{\infty }) = 1-\frac{1}{N^2}\left( 1+\frac{N-1}{\sqrt{2}} \right) ^2. \end{aligned}$$

(17)

In both cases, we see that as \(N \rightarrow \infty \) the asymptotic value of the QC-distance approaches \(\frac{1}{2}\), as opposed to the complete graph case, where the asymptote reaches unity in the same limit, see Fig. 2 for a comparison.

Fig. 2
figure 2

Asymptotic value of \(D_{\text {QC}}\) in the case of intrinsic decoherence, as a function of the graph size N, for the complete (black dots), cycle (blue squares) and star (red rhombus) graph. The values for the complete and star graph are identical

Full size image

Star graph

As opposed to the complete graph and the cycle graph, the nodes of a star graph are not all equivalent, but are rather grouped into two categories: the central node, which we will refer to as \(\vert 1\rangle \), and the remaining \(N-1\) external nodes. Consequently, the computation of the \(D_{\text {QC}}(t)\) involves an optimization over these two distinct classes of initial states, consistently with the definition in Eq. (6). Figure 1(c) shows the QC-distance of a quantum walker moving on a star graph. Note that the points of the plot where the function is not differentiable correspond to intersections between the QC-distance of a walker initially localized in the centre node and that of a walker whose initial state is an external node. We first study the system with initial state \(\rho _1=|{1}\rangle \langle {1}|\) and denote this distance with \(D_{\text {QC}}(t,c)\), where c stands for the central node. Numerical computation of the distance between the classical and the quantum noisy evolution shows that \(D_{\text {QC}}(t,c)\) is the same as the one obtained for the complete graph. The same happens in the noiseless case, where analytic calculations of the quantum and classical transition probabilities for the two graphs have the same expressions [35], as long as the walker is initialized in the central vertex of the star graph. Moreover, it is possible to show numerically that the QC-distance for the complete graph is equivalent to that of a larger class of N-nodes graphs, namely those obtained from an N-dimensional complete graph by removing edges that are not connected to the central node \(\vert 1\rangle \). This holds true for the noiseless scenario [36] as well as for the dynamics induced by intrinsic decoherence. If, instead, the initial state is localized on any of the external nodes, we obtain a different distance, that we call \(D_{\text {QC}}(t, e)\) (see the inset of Fig 1(c)). In particular, while at short times the maximum of the \(D_{\text {QC}}(t)\) is obtained by starting from the central node, at intermediate times it can be obtained by starting from one of the external nodes, depending on the value of the parameter \(\gamma \). At longer times, the central node always proves to be the optimal initialization for the walker. We can indeed compute the asymptotic value of \(D_{\text {QC}}(t, e)\) through Eq. (10). Given the Laplacian eigenvalues \(\lambda _1=\cdots =\lambda _{N-2} = 1\), \(\lambda _{N-1}=0\) \(\lambda _N=N\), and its respective eigenvectors [35]:

$$\begin{aligned} \vert \lambda _k\rangle = \sqrt{\frac{k}{k+1}}\vert k+2\rangle -\sqrt{\frac{1}{k(k+1)}}\sum _{j=2}^{k+1}\vert j\rangle , \end{aligned}$$

(18)

for \(k=1,\cdots ,N-2\) and

$$\begin{aligned}&\vert \lambda _{N-1}\rangle = \frac{1}{\sqrt{N}}\sum _{j=1}^N\vert j\rangle \end{aligned}$$

(19)

$$\begin{aligned}&\vert \lambda _N\rangle =\frac{1}{\sqrt{N(N-1)}}\sum _{j=1}^N\vert j\rangle -\sqrt{\frac{N}{N-1}}\vert 1\rangle , \end{aligned}$$

(20)

one obtains the following stationary state

$$\begin{aligned} {\mathcal {E}}_\infty [\rho _j] =&\frac{1}{N}\vert \lambda _{N-1}\rangle \!\langle \lambda _{N-1}\vert +\frac{1}{N(N-1)}\vert \lambda _{N}\rangle \!\langle \lambda _{N}\vert + \nonumber \\&+ \sum _{j,k=1}^{N-2}\frac{1}{\sqrt{j(j+1)}}\frac{1}{\sqrt{k(k+1)}}\vert \lambda _j\rangle \!\langle \lambda _k\vert . \end{aligned}$$

(21)

The asymptote of the QC-distance, having fixed the initial state to an external node, then reads

$$\begin{aligned} D_{\text {QC}}(t_{\infty },e)= 1-\frac{ \left( \sqrt{N(N-2)}+\sqrt{N-1}+1 \right) ^2}{N^2(N-1)} \end{aligned}$$

(22)

which is always lower than the one obtained via the central node as initial state. Hence, the asymptotic distance

$$\begin{aligned} D_{\text {QC}}(t_{\infty })&=\max \left[ D_{\text {QC}}(t_{\infty },c),D_{\text {QC}}(t_{\infty },e)\right] =D_{\text {QC}}(t_{\infty },c) \end{aligned}$$

(23)

of the star graph has the same expression of the asymptotic distance obtained for the complete graph, Eq. (14), as shown in Fig. 2. We can thus conclude that the quantumness of the QW is better preserved asymptotically if the walker is initially localized in the central node of the graph.

Decoherence in the position basis

Besides energy, the other natural basis to consider for decoherence phenomena is that of the states localized on the graph's nodes \(\{\left| k\right\rangle \}_{k=1}^N\). In the following, we analyse two different phenomenological models of decoherence in this basis.

We first consider the Haken–Strobl master equation introduced in Eq. (4) which, expressed in the node basis, can be recast into the following form:

$$\begin{aligned} \frac{\mathrm{d}\rho (t)}{\mathrm{d}t} = -i\left[ L,\rho (t)\right] - \gamma (\mathbb {J}-\mathbb {I})\circ \rho (t). \end{aligned}$$

(24)

Here \(\mathbb {J}\) is the unit matrix, i.e. a matrix whose entries are all 1, \(\mathbb {I}\) is the identity matrix, \(\rho \) is the density matrix expressed in the node basis and \(\circ \) denotes the Hadamard product of matrices (entry-wise product). Notice how the off-diagonal damping terms on the rhs of the equation do not depend on the distance between the sites. These dissipative terms cause off-diagonal elements of the density matrix to vanish asymptotically and, at the same time, they also induce a non-trivial dynamics of the diagonal elements since the commutator in the master equation, i.e. the unitary evolution, couples coherences with populations.

For the decoherence model of Eq. (24), we have computed the QC-distance as a function of time for the complete, cycle and star graphs, and for different values of the decoherence parameter \(\gamma \). Results are shown in Fig. 3.

Fig. 3
figure 3

Quantum-classical distance for a walker subject to the Haken–Strobl decoherent dynamics described by Eq. (24) for a a complete b cycle and c star graph with \(N=7\) nodes, computed for different values of the dephasing parameter \(\gamma \)

Full size image

Some features of \(D_{\text {QC}}(t)\) are general and do not depend on the kind of graph at study. In particular, we find that the quantum-classical distance, after one or two local maxima, goes to zero asymptotically. In turn, this means that any decoherent quantum walk achieves the uniform distribution as a stationary state. It also means that at variance with the model of intrinsic decoherence in the energy basis, the map in Eq. (24) eventually suppresses all quantum features of the QW and turns it into a classical random walk asymptotically. The cuspids in Fig. 3c (the star graph case), arise because of the maximization over classical initial states involved in the definition of \(D_{\text {QC}}(t)\). In particular, for large values of \(\gamma \) and at short times, the central node is the one achieving maximal QC-distance, while after the point where the function is not differentiable, the maximum is obtained by preparing the walker in any of the external nodes. On the other hand, for smaller values of \(\gamma \) the maximization is achieved at all times by initializing the QW in the central node of the star graph.

Also in this case, the decoherence parameter \(\gamma \) affects the rate of convergence of the QC-distance to its horizontal asymptote. However, as opposed to the intrinsic decoherence model, it is no longer true that the rate of convergence of \(D_{\text {QC}}\) to its asymptotic value is monotonic with \(\gamma \). In fact, there is a value of \(\gamma \), dependent on the dimension and on the topology of the graph, after which there is an 'inversion' and the convergence rate starts decreasing. This fact can be intuitively understood by noticing that for large values of \(\gamma \) the unitary evolution may be neglected and the off-diagonal elements of the density matrix evolve accordingly to an approximately pure exponential decay. In this regime, the system tends to stay in the initial localized state. We thus conclude that, as \(\gamma \) grows beyond a certain threshold, decoherence effects dominate over the unitary evolution and the system is somehow frozen in the initial state. As a result, it takes increasingly more time for the quantum walk to reach the uniform distribution.

The second model of decoherence in the nodes basis that we consider is the quantum stochastic walk, where the classical and the quantum dynamics are mixed at the master equation level via interpolation through a single real parameter p, see Eq. (5). We can solve this master equation numerically and compute the QC-distance for different values of the mixing parameter p, and for the classes of graphs we have considered in this work. Our numerical results show that this kind of noise is able to classicalize the quantum walk asymptotically, regardless of the topology of the underlying graph and for every value of \(p>0\). The parameter p only affects the rate of convergence of \(D_{\text {QC}}(t)\) to zero, as can be seen in Fig. 4.

Fig. 4
figure 4

Quantum-classical distance for a walker subject to decoherent dynamics induced by QSW for a a complete b cycle and c star graph with \(N=7\) nodes, computed for different values of the mixing parameter p

Full size image

The larger the value of p the faster the QW transitions into a classical random walk, since the classical component in the dynamics has a larger weight in this case, according to Eq. (5). We point out that, contrary to the two previous models of decoherence, in this case we find that the QC-distance of a quantum walker initially localized in the central node of a star graph does not coincide with that of a quantum walk on a complete graph. The discontinuity in the QC-distance derivative in Fig. 4c signals a change of the initial state that satisfies the maximization condition in the definition (6). In particular, while at short times this condition is achieved by having the initial state localized in the central node, at larger times this is attained by initializing the walker to any of the external nodes. As a final remark, we want to highlight the shorter time-scale in Fig. 4 with respect to Fig. 3, indicating a faster classicalization dynamics. The QSW model appears to be the less robust to decoherence for the topologies and choice of parameters considered.

Conclusions

Noise is a challenge to practical realization of quantum walks. Indeed, the presence of noise induces decoherence, and loss of quantum features, which are critical to achieve quantum advantages, i.e. to outperform protocols and algorithms based on classical random walks.

In this work, upon employing a fidelity-based measure of dynamical distance, we have addressed the effects of decoherence on CTQWs. In particular, we have investigated quantitatively the differences between the dynamics of a quantum walker in the presence of noise, and that of the corresponding classical walker on a given graph. In this way, we have been able to assess if, and to which extent, decoherence makes the quantum walker to turn into a classical incoherent random walker.

We have considered three different models of decoherence for a CTQW. We have first focused on intrinsic decoherence, i.e. decoherence in the energy eigenbasis, and linked the degeneracy of the Laplacian spectrum to the impossibility for this kind of noise to completely classicalize the quantum walker. In this case, we have analytically characterized the asymptotic behaviour of the quantum-classical distance and discussed how the connectivity of the graph influences the rate of convergence to its asymptotic value. We have then shifted our attention towards two models of decoherence in the node basis, namely the quantum dynamics arising from the Haken–Strobl master equation, and the quantum stochastic walk model, which interpolates between the classical and quantum RW by means of a single real mixing parameter. In both cases, we have shown that all quantum features of the dynamics are suppressed asymptotically, i.e. the quantum walker behaves like a classical random walker in the long-time limit.

Our analysis has shown that, at least for the considered classes of graphs, the qualitative features of the quantum-classical distance are not influenced by the topology of the graph, and by the number of its nodes. In addition, the asymptotic value of the quantum-classical distance does not depend on the relevant noise parameter. Finally, we have found that there is no universal behaviour of the classicalization rate as a function of the decoherence rates. A larger decoherence corresponds to a faster convergence of the QC-distance to its asymptotic value for intrinsic decoherence and the QSW models, whereas in the Haken–Strobl scenario, larger values of the decoherence rate induce localization of the walker.

Our results contribute to deepen the knowledge on the effects of noise and decoherence on quantum walks, and pave the way to engineering of decoherence, as well as to identifying regimes where its effects may be mitigated.