Restart Expedites Quantum Walk Hitting Times

Optimal conditions for first passage of jump processes with resetting

We investigate the first passage time beyond a barrier located at b≥0 of a random walk with independent and identically distributed jumps, starting from x0=0. The walk is subject to stochastic resetting, meaning that after each step the evolution is restarted with fixed probability r. We consider a resetting protocol that is an intermediate situation between a random walk (r=0) and an uncorrelated sequence of jumps all starting from the origin (r=1) and derive a general condition for determining when restarting the process with 0 Collapse

Key Words Collapse

MESH Headings Collapse

Grants Collapse

Affiliation(s)

Mattia Radice Max Planck Institute for the Physics of Complex Systems, 01187 Dresden, Germany
Giampaolo Cristadoro Dipartimento di Matematica e Applicazioni, Università degli Studi Milano-Bicocca, 20126 Milan, Italy
Samudrajit Thapa Max Planck Institute for the Physics of Complex Systems, 01187 Dresden, Germany

Collapse

Restart uncertainty relation for monitored quantum dynamics

We introduce a time-energy uncertainty relation within the context of restarts in monitored quantum dynamics. Previous studies have established that the mean recurrence time, which represents the time taken to return to the initial state, is quantized as an integer multiple of the sampling time, displaying pointwise discontinuous transitions at resonances. Our findings demonstrate that the natural utilization of the restart mechanism in laboratory experiments, driven by finite data collection time spans, leads to a broadening effect on the transitions of the mean recurrence time. Our proposed uncertainty relation captures the underlying essence of these phenomena, by connecting the broadening of the mean hitting time near resonances, to the intrinsic energies of the quantum system and to the fluctuations of recurrence time. Our uncertainty relation has also been validated through remote experiments conducted on an International Business Machines Corporation (IBM) quantum computer. This work not only contributes to our understanding of fundamental aspects related to quantum measurements and dynamics, but also offers practical insights for the design of efficient quantum algorithms with mid-circuit measurements.

Drift-diffusive resetting search process with stochastic returns: Speedup beyond optimal instantaneous return

Stochastic resetting has recently emerged as a proficient strategy to reduce the completion time for a broad class of first-passage processes. In the canonical setup, one intermittently resets a given system to its initial configuration only to start afresh and continue evolving in time until the target goal is met. This is, however, an instantaneous process and thus less feasible for any practical purposes. A crucial generalization in this regard is to consider a finite-time return process which has significant ramifications to the firstpassage properties. Intriguingly, it has recently been shown that for diffusive search processes, returning in finite but stochastic time can gain significant speedup over the instantaneous resetting process. Unlike diffusion which has a diverging mean completion time, in this paper, we ask whether this phenomena can also be observed for a first-passage process with finite mean completion time. To this end, we explore the setup of a classical drift-diffusive search process in one dimension with stochastic resetting and further assume that the return phase is modulated by a potential U(x)=λ|x| with λ>0. For this process, we compute the mean first-passage time exactly and underpin its characteristics with respect to the resetting rate and potential strength. We find a unified phase space that allows us to explore and identify the system parameter regions where stochastic return supersedes over both the underlying process and the process under instantaneous resetting. Furthermore and quite interestingly, we find that for a range of parameters the mean completion time under stochastic return protocol can be reduced further than the optimally restarted instantaneous processes. We thus believe that resetting with stochastic returns can serve as a better optimization strategy owing to its dominance over classical first passage under resetting.

First Hitting Times on a Quantum Computer: Tracking vs. Local Monitoring, Topological Effects, and Dark States

We investigate a quantum walk on a ring represented by a directed triangle graph with complex edge weights and monitored at a constant rate until the quantum walker is detected. To this end, the first hitting time statistics are recorded using unitary dynamics interspersed stroboscopically by measurements, which are implemented on IBM quantum computers with a midcircuit readout option. Unlike classical hitting times, the statistical aspect of the problem depends on the way we construct the measured path, an effect that we quantify experimentally. First, we experimentally verify the theoretical prediction that the mean return time to a target state is quantized, with abrupt discontinuities found for specific sampling times and other control parameters, which has a well-known topological interpretation. Second, depending on the initial state, system parameters, and measurement protocol, the detection probability can be less than one or even zero, which is related to dark-state physics. Both return-time quantization and the appearance of the dark states are related to degeneracies in the eigenvalues of the unitary time evolution operator. We conclude that, for the IBM quantum computer under study, the first hitting times of monitored quantum walks are resilient to noise. However, a finite number of measurements leads to broadening effects, which modify the topological quantization and chiral effects of the asymptotic theory with an infinite number of measurements.

Search with stochastic home returns can expedite classical first passage under resetting

Classical first passage under resetting is a paradigm in the search process. Despite its multitude of applications across interdisciplinary sciences, experimental realizations of such resetting processes posit practical challenges in calibrating these zero time irreversible transitions. Here, we consider a strategy in which resetting is performed using finite-time return protocols in lieu of instantaneous returns. These controls could also be accompanied with random fluctuations or errors allowing target detection even during the return phase. To better understand the phenomena, we develop a unified renewal approach that can encapsulate arbitrary search processes centered around home in a fairly general topography containing targets, various resetting times, and return mechanisms in arbitrary dimensions. While such finite-time protocols would apparently seem to prolong the overall search time in comparison to the instantaneous resetting process, we show on the contrary that a significant speed-up can be gained by leveraging the stochasticity in home returns. The formalism is then explored to reveal a universal criterion distilling the benefits of this strategy. We demonstrate how this general principle can be utilized to improve overall performance of a one-dimensional diffusive search process reinforced with experimentally feasible parameters. We believe that such strategies designed with inherent randomness can be made optimal with precise controllability in complex search processes.

Quest for optimal quantum resetting: Protocols for a particle on a chain

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.

Stochastic dynamics of a non-Markovian random walk in the presence of resetting

The discrete stochastic dynamics of a random walker in the presence of resetting and memory is analyzed. Resetting and memory effects may compete in certain parameter regimes, and lead to significant changes in the long-time dynamics of the walker. Analytic exact results are obtained for a model memory where the walker remembers all the past events equally. In most cases, resetting effects dominate at long times and dictate the asymptotic dynamics. We discuss the full phase diagram of the asymptotic dynamics and the resulting changes due to the resetting and the memory effects.

Instability in the quantum restart problem

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 τ.

Kuramoto model subject to subsystem resetting: How resetting a part of the system may synchronize the whole of it

We introduce and investigate the effects of a new class of stochastic resetting protocol called subsystem resetting, whereby a subset of the system constituents in a many-body interacting system undergoes bare evolution interspersed with simultaneous resets at random times, while the remaining constituents evolve solely under the bare dynamics. Here, by reset is meant a reinitialization of the dynamics from a given state. We pursue our investigation within the ambit of the well-known Kuramoto model of coupled phase-only oscillators of distributed natural frequencies. Here, the reset protocol corresponds to a chosen set of oscillators being reset to a synchronized state at random times. We find that the mean ω_{0} of the natural frequencies plays a defining role in determining the long-time state of the system. For ω_{0}=0, the system reaches a synchronized stationary state at long times, characterized by a time-independent nonzero value of the synchronization order parameter that quantifies macroscopic order in the system. Moreover, we find that resetting even an infinitesimal fraction of the total number of oscillators, in the extreme limit of infinite resetting rate, has the drastic effect of synchronizing the entire system, even in parameter regimes in which the bare evolution does not support global synchrony. By contrast, for ω_{0}≠0, the dynamics allows at long times either a synchronized stationary state or an oscillatory synchronized state, with the latter characterized by an oscillatory behavior as a function of time of the order parameter, with a nonzero time-independent time average. Our results thus imply that the nonreset subsystem always gets synchronized at long times through the act of resetting of the reset subsystem. Our results, analytical using the Ott-Antonsen ansatz as well as those based on numerical simulations, are obtained for two representative oscillator frequency distributions, namely, a Lorentzian and a Gaussian. Given that it is easier to reset a fraction of the system constituents than the entire system, we discuss how subsystem resetting may be employed as an efficient mechanism to control attainment of global synchrony in the Kuramoto system.

Universal and nonuniversal probability laws in Markovian open quantum dynamics subject to generalized reset processes

We consider quantum-jump trajectories of Markovian open quantum systems subject to stochastic in time resets of their state to an initial configuration. The reset events provide a partitioning of quantum trajectories into consecutive time intervals, defining sequences of random variables from the values of a trajectory observable within each of the intervals. For observables related to functions of the quantum state, we show that the probability of certain orderings in the sequences obeys a universal law. This law does not depend on the chosen observable and, in the case of Poissonian reset processes, not even on the details of the dynamics. When considering (discrete) observables associated with the counting of quantum jumps, the probabilities in general lose their universal character. Universality is only recovered in cases when the probability of observing equal outcomes in the same sequence is vanishingly small, which we can achieve in a weak-reset-rate limit. Our results extend previous findings on classical stochastic processes [N. R. Smith et al., Europhys. Lett. 142, 51002 (2023)0295-507510.1209/0295-5075/acd79e] to the quantum domain and to state-dependent reset processes, shedding light on relevant aspects for the emergence of universal probability laws.

Exact fluctuation and long-range correlations in a single-file model under resetting

Resetting is a renewal mechanism in which a process is intermittently repeated after a random or fixed time. This simple act of stop and repeat profoundly influences the behavior of a system as exemplified by the emergence of nonequilibrium properties and expedition of search processes. Herein we explore the ramifications of stochastic resetting in the context of a single-file system called random average process (RAP) in one dimension. In particular, we focus on the dynamics of tracer particles and analytically compute the variance, equal time correlation, autocorrelation, and unequal time correlation between the positions of different tracer particles. Our study unveils that resetting gives rise to rather different behaviors depending on whether the particles move symmetrically or asymmetrically. For the asymmetric case, the system for instance exhibits a long-range correlation which is not seen in absence of the resetting. Similarly, in contrast to the reset-free RAP, the variance shows distinct scalings for symmetric and asymmetric cases. While for the symmetric case, it decays (towards its steady value) as ∼e^{-rt}/sqrt[t], we find ∼te^{-rt} decay for the asymmetric case (r being the resetting rate). Finally, we examine the autocorrelation and unequal time correlation in the steady state and demonstrate that they obey interesting scaling forms at late times. All our analytical results are substantiated by extensive numerical simulations.

Diffusion with two resetting points

We study the problem of a target search by a Brownian particle subject to stochastic resetting to a pair of sites. The mean search time is minimized by an optimal resetting rate which does not vary smoothly, in contrast with the well-known single site case, but exhibits a discontinuous transition as the position of one resetting site is varied while keeping the initial position of the particle fixed, or vice versa. The discontinuity vanishes at a "liquid-gas" critical point in position space. This critical point exists provided that the relative weight m of the further site is comprised in the interval [2.9028...,8.5603...]. When the initial position is a random variable that follows the resetting point distribution, a discontinuous transition also exists for the optimal rate as the distance between the resetting points is varied, provided that m exceeds the critical value m_{c}=6.6008.... This setup can be mapped onto an intermittent search problem with switching diffusion coefficients and represents a minimal model for the study of distributed resetting.

Combining stochastic resetting with Metadynamics to speed-up molecular dynamics simulations

Metadynamics is a powerful method to accelerate molecular dynamics simulations, but its efficiency critically depends on the identification of collective variables that capture the slow modes of the process. Unfortunately, collective variables are usually not known a priori and finding them can be very challenging. We recently presented a collective variables-free approach to enhanced sampling using stochastic resetting. Here, we combine the two methods, showing that it can lead to greater acceleration than either of them separately. We also demonstrate that resetting Metadynamics simulations performed with suboptimal collective variables can lead to speedups comparable with those obtained with optimal collective variables. Therefore, applying stochastic resetting can be an alternative to the challenging task of improving suboptimal collective variables, at almost no additional computational cost. Finally, we propose a method to extract unbiased mean first-passage times from Metadynamics simulations with resetting, resulting in an improved tradeoff between speedup and accuracy. This work enables combining stochastic resetting with other enhanced sampling methods to accelerate a broad range of molecular simulations.

Semi-Markov processes in open quantum systems. II. Counting statistics with resetting

A semi-Markov process method for obtaining general counting statistics for open quantum systems is extended to the scenario of resetting. The simultaneous presence of random resets and wave function collapses means that the quantum jump trajectories are no longer semi-Markov. However, focusing on trajectories and using simple probability formulas, general counting statistics can still be constructed from reset-free statistics. An exact tilted matrix equation is also obtained. The inputs of these methods are the survival distributions and waiting-time density distributions instead of quantum operators. In addition, a continuous-time cloning algorithm is introduced to simulate the large-deviation properties of open quantum systems. Several quantum optics systems are used to demonstrate these results.

Tight-binding model subject to conditional resets at random times

We investigate the dynamics of a quantum system subjected to a time-dependent and conditional resetting protocol. Namely, we ask what happens when the unitary evolution of the system is repeatedly interrupted at random time instants with an instantaneous reset to a specified set of reset configurations taking place with a probability that depends on the current configuration of the system at the instant of reset? Analyzing the protocol in the framework of the so-called tight-binding model describing the hopping of a quantum particle to nearest-neighbor sites in a one-dimensional open lattice, we obtain analytical results for the probability of finding the particle on the different sites of the lattice. We explore a variety of dynamical scenarios, including the one in which the resetting time intervals are sampled from an exponential as well as from a power-law distribution, and a setup that includes a Floquet-type Hamiltonian involving an external periodic forcing. Under exponential resetting, and in both the presence and absence of the external forcing, the system relaxes to a stationary state characterized by localization of the particle around the reset sites. The choice of the reset sites plays a defining role in dictating the relative probability of finding the particle at the reset sites as well as in determining the overall spatial profile of the site-occupation probability. Indeed, a simple choice can be engineered that makes the spatial profile highly asymmetric even when the bare dynamics does not involve the effect of any bias. Furthermore, analyzing the case of power-law resetting serves to demonstrate that the attainment of the stationary state in this quantum problem is not always evident and depends crucially on whether the distribution of reset time intervals has a finite or an infinite mean.

Ergodic properties of Brownian motion under stochastic resetting

We study the ergodic properties of one-dimensional Brownian motion with resetting. Using generic classes of statistics of times between resets, we find respectively for thin- or fat-tailed distributions the normalized or non-normalized invariant density of this process. The former case corresponds to known results in the resetting literature and the latter to infinite ergodic theory. Two types of ergodic transitions are found in this system. The first is when the mean waiting time between resets diverges, when standard ergodic theory switches to infinite ergodic theory. The second is when the mean of the square root of time between resets diverges and the properties of the invariant density are drastically modified. We then find a fractional integral equation describing the density of particles. This finite time tool is particularly useful close to the ergodic transition where convergence to asymptotic limits is logarithmically slow. Our study implies rich ergodic behaviors for this nonequilibrium process which should hold far beyond the case of Brownian motion analyzed here.

Controls that expedite first-passage times in disordered systems

First-passage time statistics in disordered systems exhibiting scale invariance are studied widely. In particular, long trapping times in energy or entropic traps are fat-tailed distributed, which slow the overall transport process. We study the statistical properties of the first-passage time of biased processes in different models, and we employ the big-jump principle that shows the dominance of the maximum trapping time on the first-passage time. We demonstrate that the removal of this maximum significantly expedites transport. As the disorder increases, the system enters a phase where the removal shows a dramatic effect. Our results show how we may speed up transport in strongly disordered systems exploiting scale invariance. In contrast to the disordered systems studied here, the removal principle has essentially no effect in homogeneous systems; this indicates that improving the conductance of a poorly conducting system is, theoretically, relatively easy as compared to a homogeneous system.