A powerful strategy to accelerate quantum-walk-based search algorithms leverages on resetting protocols, where a detector monitors a target site and the evolution of the walker is restarted if no detection occurs within a fixed time interval. The optimal resetting rate can be extracted from the time evolution of the probability S(t) that the detector has not clicked up to time t. We analyze S(t) for a quantum walk on a one-dimensional lattice when the coupling between sites decays algebraically as d^{-α} with the distance d, for α∈(0,∞). At long times, S(t) decays with a universal power-law exponent that is independent of α. At short times, S(t) exhibits a plethora of phase transitions as a function of α. From this, we provide a strategy to determine the optimal resetting rate. We identify two regimes: for α>1, the resetting rate r is bounded from below by the velocity with which information propagates causally across the lattice; for α<1, instead, the long-range hopping tends to localize the walker: The optimal resetting rate depends on the size of the lattice and diverges as α→0. Our strategy directly connects local measurement outcomes with the global dynamics encoded in S(t). We derive simple models explaining our numerical results, shedding light on the interplay of long-range coherent dynamics, symmetries, and local quantum measurement processes in determining equilibrium. Our findings offer experimentally testable predictions and provide new physical insights on optimizing quantum search through resetting.
A powerful strategy to accelerate quantum-walk-based search algorithms leverages on resetting protocols, where a detector monitors a target site and the evolution of the walker is restarted if no detection occurs within a fixed time interval. The optimal resetting rate can be extracted from the time evolution of the probability S(t) that the detector has not clicked up to time t. We analyze S(t) for a quantum walk on a one-dimensional lattice when the coupling between sites decays algebraically as d^{-α} with the distance d, for α∈(0,∞). At long times, S(t) decays with a universal power-law exponent that is independent of α. At short times, S(t) exhibits a plethora of phase transitions as a function of α. From this, we provide a strategy to determine the optimal resetting rate. We identify two regimes: for α>1, the resetting rate r is bounded from below by the velocity with which information propagates causally across the lattice; for α<1, instead, the long-range hopping tends to localize the walker: The optimal resetting rate depends on the size of the lattice and diverges as α→0. Our strategy directly connects local measurement outcomes with the global dynamics encoded in S(t). We derive simple models explaining our numerical results, shedding light on the interplay of long-range coherent dynamics, symmetries, and local quantum measurement processes in determining equilibrium. Our findings offer experimentally testable predictions and provide new physical insights on optimizing quantum search through resetting.
Searching a database is a central task in computer science and is paradigmatic of transport and optimization problems in physics. For an unstructured search, Grover's algorithm predicts a quadratic speedup, with the search time τ(N)=Θ(N) and N the database size. Numerical studies suggest that the time complexity can change in the presence of feedback, injecting information during the search. Here, we determine the time complexity of the quantum analog of a randomized algorithm, which implements feedback in a simple form. The search is a continuous-time quantum walk on a complete graph, where the target is continuously monitored by a detector. Additionally, the quantum state is reset if the detector does not click within a specified time interval. This yields a non-unitary, non-Markovian dynamics. We optimize the search time as a function of the hopping amplitude, detection rate, and resetting rate, and identify the conditions under which time complexity could outperform Grover's scaling. The overall search time does not violate Grover's optimality bound when including the time budget of the physical implementation of the measurement. For databases of finite sizes monitoring can warrant rapid convergence and provides a promising avenue for fault-tolerant quantum searches.
In a quantum walk, the first-detection return probability (FDRP) characterizes salient features, determining whether the quantum walk is transient or recurrent. We study the FDRP of quantum walks on a chain where the initial site is stroboscopically monitored by a detector and the walker performs long-range hopping between sites. We assume that the hopping strength decays with the distance d as d−α and α≥0 and show that the power-law exponent α critically determines the behavior of the FDRP. The value α=1 separates recurrent (α<1) from transient (α>1) quantum walks through a continuous phase transition in the total detection probability. For α<1, strong long-range hopping induces localization, resulting in unit total detection probability. Instead, for α>1 the long-range walk is transient and the return probability decays algebraically as a function of time as t−β. The associated decay exponent β features nonanalytic points as a function of α. Such singularities are not exclusively determined by the low-energy spectrum, but are caused by the interference between infrared and ultraviolet energy modes induced by projective measurements, signalling the emergence of critical behavior intrinsic to the non-unitary dynamics. These dynamics are solely controlled by tuning the long-range exponent α and can thus be experimentally probed in atomic and molecular systems.
A quantum walk on a lattice is a paradigm of a quantum search in a database. The database qubit strings are the lattice sites, qubit rotations are tunneling events, and the target site is tagged by an energy shift. For quantum walks on a continuous time, the walker diffuses across the lattice and the search ends when it localizes at the target site. The search time T can exhibit Grover's optimal scaling with the lattice size N , namely, T ∼ N , on an all-connected, complete lattice. For finite-range tunneling between sites, instead, Grover's optimal scaling is warranted when the lattice is a hypercube of d > 4 dimensions. Here, we show that Grover's optimum can be reached in lower dimensions on lattices of long-range interacting particles, when the interaction strength scales algebraically with the distance r as 1 / r α and 0 < α < 3 d / 2 . For α < d the dynamics mimics the one of a globally connected graph. For d < α < d + 2 , the quantum search on the graph can be mapped to a short-range model on a hypercube with spatial dimension d s = 2 d / ( α − d ) , indicating that the search is optimal for d s > 4 . Our work identifies an exact relation between criticality of long-range and short-range systems, it provides a quantitative demonstration of the resources that long-range interactions provide for quantum technologies, and indicates when existing experimental platforms can implement efficient analog quantum search algorithms.
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.
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.
Abstract The problem of the detection statistics of a quantum walker has received increasing interest. We investigate the effect of employing a moving detector, using a projective measurement approach with fixed sampling time , with the detector moving right before every detection attempt. For a tight-binding quantum walk on the line, the moving detector allows one to target a specific range of group velocities of the walker, qualitatively modifying the behavior of the quantum first-detection probabilities. We map the problem to that of a stationary detector with a modified unitary evolution operator and use established methods for the solution of that problem to study the first-detection statistics for a moving detector on a finite ring and on an infinite 1D lattice. On the line, the system exhibits a dynamical phase transition at a critical value of , from a state where the probability of detection decreases exponentially in time and the total detection probability is very small, to a state with power-law decay and a significantly higher total probability to detect the particle. The exponent describing the power-law decay of the detection probability at this critical is 10/3, as opposed to 3 for every larger . In addition, the moving detector strongly modifies the Zeno effect.