Random walks are fundamental models of stochastic processes with applications in various fields, including physics, biology, and computer science. We study classical and quantum random walks under the influence of stochastic resetting on arbitrary networks. Based on the mathematical formalism of quantum stochastic walks, we provide a framework of classical and quantum walks whose evolution is determined by graph Laplacians. We study the influence of quantum effects on the stationary and long-time average probability distribution by interpolating between the classical and quantum regime. We compare our analytical results on stationary and long-time average probability distributions with numerical simulations on different networks, revealing differences in the way resets affect the sampling properties of classical and quantum walks.
Mean squared displacement has been widely used as the primary metric for comparing quantum and classical random walks, with quantum walks showing quadratic scaling versus linear scaling for classical walks. However, this comparison may not capture the full picture: while the mean squared displacement is well suited for Gaussian distributions, quantum walk distributions exhibit distinctly non-Gaussian features. We propose that the mean hitting time offers a complementary perspective with clear operational meaning for search algorithms. Through analytical calculations, we show that quantum and classical walks yield identical MHT for symmetric initial conditions with two detectors, suggesting that the apparent quantum advantage seen in MSD comparisons may be context dependent. Interestingly, introducing stochastic resetting reveals more dynamics. We demonstrate analytically that quantum walks can achieve reduced MHT under stochastic reset through quasimomentum redistribution, while classical walks see no benefit. This quantum advantage naturally degrades with noise, and the quantum walk converges to classical behavior. We suggest that MHT reduction under stochastic reset can serve as an additional signature of quantum behavior, particularly useful for characterizing quantum walk implementations on noisy quantum devices. Our results indicate that different metrics can reveal different aspects of quantum-classical comparisons in walk-based algorithms.
Restart is a common strategy observed in nature that accelerates first-passage processes, and has been extensively studied using classical random walks. In the quantum regime, restart in continuous-time quantum walks (CTQWs) has been shown to expedite the quantum hitting times []. Here, we study how restarting monitored discrete-time quantum walks (DTQWs) affects the quantum hitting times. We show that the restarted DTQWs outperform classical random walks in target searches, benefiting from quantum ballistic propagation, a feature shared with their continuous-time counterparts. Moreover, the explicit coin degree of freedom in DTQWs allows them to surpass even CTQWs in target detection without sacrificing any quantum advantage. Additionally, knowledge of the target's parity or position relative to the origin can be leveraged to tailor DTQWs for even faster searches. Our study paves the way for more efficient use of DTQWs in quantum-walk-based search algorithms, simulations, and modeling of quantum transport towards targeted sites in complex quantum networks.
We study stochastic and sharp restart in a one-dimensional lackadaisical discrete-time quantum walk with self-loop weight
ℓ. In the absence of restart, the dynamics has a flat band responsible for intrinsic localization and two dispersive bands supporting ballistic propagation. We compare two initially localized benchmark states: a flat-band-active state with finite flat-band overlap and a flat-band-dark state with zero flat-band overlap. For geometric stochastic restart with per-step restart probability
q, the stationary mean-squared displacement scales as
q−2 as
q→0. In the same limit, the restart-site occupation probability approaches the restart-free intrinsic localized value for the flat-band-active state, whereas for the flat-band-dark state it vanishes as
qln(1/q). For power-law restart, where
pm∝m−s is the probability that the waiting time to the next restart is
m steps, a normalized stationary site-occupation distribution exists only for
s>2, while the stationary absolute spatial moment of order
p is finite only for
s>p+2. In the regime
1<s≤2, at every fixed lattice site, the flat-band-active occupation converges to the intrinsic flat-band profile, while the flat-band-dark occupation tends to zero. We also consider monitored first detection with sharp restart, in which the walk is reinitialized after a fixed number
r of consecutive unsuccessful measurements. For fixed
r, the mean first-detected-passage time of the flat-band-active state exhibits a minimum at an intermediate self-loop weight, whereas the flat-band-dark state approaches a ballistic detection limit as
ℓ→∞.
Stochastic resetting describes dynamics which are reinitialized to a reference state at random times. These protocols are attracting significant interest: they can stabilize nonequilibrium stationary states, generate correlations in noninteracting systems, and enable optimal search strategies. While a constant reset probability results in a Markovian dynamics, much less is known about non-Markovian effects in quantum stochastic resetting. Here, we analyze memory effects in these processes -- examining the evolution of quantum states and of observables -- through witnesses of non-Markovianity for open quantum systems. We focus on discrete-time reset processes, which are of particular interest as they can be implemented on existing gate-operated quantum devices. We show that these processes are generically described by non-divisible maps and, in non-classical scenarios where the effective reset probability can become negative, can feature revivals in the state distinguishability. Our results reveal non-Markovian effects in quantum stochastic resetting and show that a time-dependent reset may be exploited to engineer enhanced stationary quantum correlations.
Repeatedly monitored quantum walks with a rate 1/τ yield discrete-time trajectories which are inherently random. With these paths the first-hitting time with sharp restart is studied. We find an instability in the optimal mean hitting time, which is not found in the corresponding classical random-walk process. This instability implies that a small change in parameters can lead to a rather large change of the optimal restart time. We show that the optimal restart time versus τ, as a control parameter, exhibits sets of staircases and plunges. The plunges, are due to the mentioned instability, which in turn is related to the quantum oscillations of the first-hitting time probability, in the absence of restarts. Furthermore, we prove that there are only two patterns of staircase structures, dependent on the parity of the distance between the target and the source in units of lattice constant. The global minimum of the hitting time is controlled not only by the restart time, as in classical problems, but also by the sampling time τ. We provide numerical evidence that this global minimum occurs for the τ minimizing the mean hitting time, given restarts taking place after each measurement. Last, we numerically show that the instability found in this work is relatively robust against stochastic perturbations in the sampling time τ.