Revisiting quantum walk advantages: A mean hitting time perspective

Abstract

The 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 new dynamics. We demonstrate analytically that quantum walks can achieve reduced MHT under stochastic reset through quasi-momentum redistribution, while classical walks see no benefit. This quantum advantage naturally degrades with noise, 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.

References in corpus (28)

• Quantum random walks - an introductory overview
• Quantum Computation and Decision Trees
• Quantum algorithms: an overview
• Quantum Walk in Position Space with Single Optically Trapped Atoms
• Exploring Topological Phases With Quantum Walks
• Realization of quantum walks with negligible decoherence in waveguide lattices
• Realization of a quantum walk with one and two trapped ions
• Anderson localization of entangled photons in an integrated quantum walk
• Quantum walk of a trapped ion in phase space
• Quantum walks on a programmable two-dimensional 62-qubit superconducting processor
• Random Walks: A Review of Algorithms and Applications
• Experimental Implementation of Discrete Time Quantum Random Walk on an NMR Quantum Information Processor
• Experimental Implementation of the Quantum Random-Walk Algorithm
• Experimental Two-dimensional Quantum Walk on a Photonic Chip
• Topology and Broken Symmetry in Floquet Systems
• Symmetries, Topological Phases and Bound States in the One-Dimensional Quantum Walk
• Electric quantum walks with individual atoms
• Dynamical moments reveal a topological quantum transition in a photonic quantum walk
• Hitting time for quantum walks on the hypercube
• Observing Topological Invariants Using Quantum Walk in Superconducting Circuits
• Quantum Walk in Momentum Space with a Bose-Einstein Condensate
• Propagation and spectral properties of quantum walks in electric fields
• Quantum walks with infinite hitting times
• Hitting time for the continuous quantum walk
• Quantum phase transition using quantum walks in an optical lattice
• Quantum walks in external gauge fields
• Creating cat states in one-dimensional quantum walks using delocalized initial states
• Twisted quantum walks, generalised Dirac equation and Fermion doubling