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.
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.
Classical first-passage times under restart are used in a wide variety of models, yet the quantum version of the problem still misses key concepts. We study the quantum hitting time with restart using a monitored quantum walk. The restart strategy eliminates the problem of dark states, i.e., cases where the particle evades detection, while maintaining the ballistic propagation which is important for a fast search. We find profound effects of quantum oscillations on the restart problem, namely, a type of instability of the mean detection time, and optimal restart times that form staircases, with sudden drops as the rate of sampling is modified. In the absence of restart and in the Zeno limit, the detection of the walker is not possible, and we examine how restart overcomes this well-known problem, showing that the optimal restart time becomes insensitive to the sampling period.
Quantum walks can be defined in two quite distinct ways: discrete-time and continuous-time quantum walks (DTQWs and CTQWs). For classical random walks, there is a natural sense in which continuous-time walks are a limit of discrete-time walks. Quantum mechanically, in the discrete-time case, an additional ``coin space'' must be appended for the walk to have nontrivial time evolution. Continuous-time quantum walks, however, have no such constraints. This means that there is no completely straightforward way to treat a CTQW as a limit of a DTQW, as can be done in the classical case. Various approaches to this problem have been taken in the past. We give a construction for walks on d-regular, d-colorable graphs when the coin flip operator is Hermitian: from a standard DTQW we construct a family of discrete-time walks with a well-defined continuous-time limit on a related graph. One can think of this limit as a ``coined'' continuous-time walk. We show that these CTQWs share some properties with coined DTQWs. In particular, we look at a spatial search by a DTQW over the two-dimensional (2D) torus (a grid with periodic boundary conditions) of size $\sqrt{N}\ifmmode\times\else\texttimes\fi{}\sqrt{N}$, where it was shown that a coined DTQW can search in time O(NlogN), but a standard CTQW takes $\mathrm{\ensuremath{\Omega}}(N)$ time to search for a marked element. The continuous limit of the DTQW search over the 2D torus exhibits the O(NlogN) scaling, like the coined walk it is derived from. We also look at the effects of graph symmetry on the limiting walk, and show that the properties are similar to those of the DTQW as shown in Krovi and Brun, Phys. Rev. A 75, 062332 (2007).
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 τ.
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 ℓ→∞.
We investigate the effect of stochastic restart/resetting on discrete-time quantum walks concerning its impact on the meantime to absorption in the walk on the one-dimensional lattice terminated by a pair of totally absorbing sites. The two distinguished sites also play the role of an apparatus that detects the moment of time when a quantum walk reaches these boundaries. Our results reveal a notable difference between the quantum walk and its classical counterpart. Specifically, we focus on instances of classical random walks in which stochastic resetting fails to reduce the meantime to absorption. Conversely, we show that stochastic resetting can be utilized to effectively diminish the meantime to absorption in the quantum version of this walk. We relate the observed difference between quantum and classical cases to the fact that restarting the quantum state not only changes position distribution but inevitably changes complementary quasimomentum distribution.
Continuous time quantum walks (CTQWs) do not necessarily perform better than their classical counterparts, the continuous time random walks (CTRWs). For one special graph, where a recent analysis showed that in a particular direction of propagation the penetration of the graph is faster by CTQWs than by CTRWs, we demonstrate that in another direction of propagation the opposite is true. In this case a CTQW initially localized at one site displays a slow transport. We furthermore show that when the CTQW's initial condition is a totally symmetric superposition of states of equivalent sites, the transport gets to be much more rapid.