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.
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.
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 τ.
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.
Even after decades of research, the problem of first passage time statistics for quantum dynamics remains a challenging topic of fundamental and practical importance. Using a projective measurement approach, with a sampling time τ, we obtain the statistics of first detection events for quantum dynamics on a lattice, with the detector located at the origin. A quantum renewal equation for a first detection wave function, in terms of which the first detection probability can be calculated, is derived. This formula gives the relation between first detection statistics and the solution of the corresponding Schrödinger equation in the absence of measurement. We illustrate our results with tight-binding quantum walk models. We examine a closed system, i.e., a ring, and reveal the intricate influence of the sampling time τ on the statistics of detection, discussing the quantum Zeno effect, half dark states, revivals, and optimal detection. The initial condition modifies the statistics of a quantum walk on a finite ring in surprising ways. In some cases, the average detection time is independent of the sampling time while in others the average exhibits multiple divergences as the sampling time is modified. For an unbounded one-dimensional quantum walk, the probability of first detection decays like (time)^{(-3)} with superimposed oscillations, with exceptional behavior when the sampling period τ times the tunneling rate γ is a multiple of π/2. The amplitude of the power-law decay is suppressed as τ→0 due to the Zeno effect. Our work, an extended version of our previously published paper, predicts rich physical behaviors compared with classical Brownian motion, for which the first passage probability density decays monotonically like (time)^{-3/2}, as elucidated by Schrödinger in 1915.
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 ℓ→∞.
In the classical context, it is well known that, sometimes, if a search does not find its target, it is better to start the process anew. This is known as resetting. The quantum counterpart of resetting also indicates speeding up the detection process by eliminating the dark states, i.e., situations in which the particle avoids detection. In this work, we introduce the most probable position resetting (MPR) protocol, in which, at a given resetting step, resets are done with certain probabilities to the set of possible peak positions (where the probability of finding the particle is maximum) that could occur because of the previous resets and followed by uninterrupted unitary evolution, irrespective of which path was taken by the particle in previous steps. In a tight-binding lattice model, there exists a twofold degeneracy (left and right) of the positions of maximum probability. The survival probability with optimal restart rate approaches 0 (detection probability approaches 1) when the particle is reset with equal probability on both sides path independently. This protocol significantly reduces the optimal mean first-detected-passage time (FDT), and it performs better even if the detector is far apart compared to the usual resetting protocols in which the particle is brought back to the initial position. We propose a modified protocol, an adaptive two-stage MPR, by making the associated probabilities of going to the right and left a function of steps. In this protocol, we see a further reduction of the optimal mean FDT and improvement in the search process when the detector is far apart.
The hitting time of a classical random walk (Markov chain) is the time required to detect the presence of -- or equivalently, to find -- a marked state. The hitting time of a quantum walk is subtler to define; in particular, it is unknown whether the detection and finding problems have the same time complexity. In this paper we define new Monte Carlo type classical and quantum hitting times, and we prove several relationships among these and the already existing Las Vegas type definitions. In particular, we show that for some marked state the two types of hitting time are of the same order in both the classical and the quantum case.Further, we prove that for any reversible ergodic Markov chain P, the quantum hitting time of the quantum analogue of P has the same order as the square root of the classical hitting time of P. We also investigate the (im)possibility of achieving a gap greater than quadratic using an alternative quantum walk. In doing so, we define a notion of reversibility for a broad class of quantum walks and show how to derive from any such quantum walk a classical analogue. For the special case of quantum walks built on reflections, we show that the hitting time of the classical analogue is exactly the square of the quantum walk.Finally, we present new quantum algorithms for the detection and finding problems. The complexities of both algorithms are related to the new, potentially smaller, quantum hitting times. The detection algorithm is based on phase estimation and is particularly simple. The finding algorithm combines a similar phase estimation based procedure with ideas of Tulsi from his recent theorem [19] for the 2D grid. Extending his result, we show that for any state-transitive Markov chain with unique marked state, the quantum hitting time is of the same order for both the detection and finding problems.