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.
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.
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.
Quantum walks are stochastic processes generated by a quantum evolution mechanism, allowing for speed-up in spreading and hitting-time performance with respect to their classical counterparts. Investigating the role of the memory effects for these models, we address the problem of finding the minimal linear system that exactly reproduces the evolution of the output distribution of a quantum walk. After adapting the classical approach to our setting, we investigate analytically and numerically the structural complexity of quantum walks, both in general and in particular examples. Lastly, we focus on Grover’s algorithm, a quantum computing search algorithm that can be re-framed as a quantum walk, showing that it allows for a dramatic reduction in its representation.
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.
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.
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. Then, 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 (Tulsi A.: Phys. Rev. A 78:012310 2008) for the 2D grid. Extending his result, we show that we can find a unique marked element with constant probability and with the same complexity as detection for a large class of quantum walks—the quantum analogue of state-transitive reversible ergodic Markov chains. 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.
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. Then, 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 (Tulsi A.: Phys. Rev. A 78 :012310 2008 ) for the 2D grid. Extending his result, we show that we can find a unique marked element with constant probability and with the same complexity as detection for a large class of quantum walks—the quantum analogue of state-transitive reversible ergodic Markov chains. 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.