Revisiting quantum walk advantages: A mean hitting time perspective

• URL: http://arxiv.org/abs/2510.27377v1
• Date: Fri, 31 Oct 2025 11:12:35 GMT
• Title: Revisiting quantum walk advantages: A mean hitting time perspective
• Authors: Jan Wójcik,
• Abstract summary: We show that quantum and classical walks yield identical MHT for symmetric initial conditions with two detectors.<n>This quantum advantage naturally degrades noise, the quantum walk converges to classical behavior.<n>Our results indicate that different metrics can reveal different aspects of quantum-classical comparisons in walk-based algorithms.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• QAMA: Scalable Quantum Annealing Multi-Head Attention Operator for Deep Learning [48.12231190677108]
  Quantum Annealing Multi-Head Attention (QAMA) is proposed, a novel drop-in operator that reformulates attention as an energy-based Hamiltonian optimization problem.<n>In this framework, token interactions are encoded into binary quadratic terms, and quantum annealing is employed to search for low-energy configurations.<n> Empirically, evaluation on both natural language and vision benchmarks shows that, across tasks, accuracy deviates by at most 2.7 points from standard multi-head attention.
  arXiv  Detail & Related papers  (2025-04-15T11:29:09Z)
• Bayesian Quantum Amplitude Estimation [46.03321798937855]
  We present BAE, a problem-tailored and noise-aware Bayesian algorithm for quantum amplitude estimation.<n>In a fault tolerant scenario, BAE is capable of saturating the Heisenberg limit; if device noise is present, BAE can dynamically characterize it and self-adapt.<n>We propose a benchmark for amplitude estimation algorithms and use it to test BAE against other approaches.
  arXiv  Detail & Related papers  (2024-12-05T18:09:41Z)
• Quantum Dissipative Search via Lindbladians [0.0]
  We analyze a purely dissipative quantum random walk on an unstructured classical search space.<n>We show that certain jump operators make the quantum process replicate a classical one, while others yield differences between open quantum (OQRW) and classical random walks.<n>We also clarify a previously observed quadratic speedup, demonstrating that OQRWs are no more efficient than classical search.
  arXiv  Detail & Related papers  (2024-07-16T14:39:18Z)
• QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum Circuits [82.50620782471485]
  QuantumSEA is an in-time sparse exploration for noise-adaptive quantum circuits. It aims to achieve two key objectives: (1) implicit circuits capacity during training and (2) noise robustness. Our method establishes state-of-the-art results with only half the number of quantum gates and 2x time saving of circuit executions.
  arXiv  Detail & Related papers  (2024-01-10T22:33:00Z)
• Applicability of Measurement-based Quantum Computation towards Physically-driven Variational Quantum Eigensolver [17.975555487972166]
  Variational quantum algorithms are considered one of the most promising methods for obtaining near-term quantum advantages. The roadblock to developing quantum algorithms with the measurement-based quantum computation scheme is resource cost. We propose an efficient measurement-based quantum algorithm for quantum many-body system simulation tasks, called measurement-based Hamiltonian variational ansatz (MBHVA)
  arXiv  Detail & Related papers  (2023-07-19T08:07:53Z)
• Discrete-time Semiclassical Szegedy Quantum Walks [0.0]
  We introduce the semiclassical walks in discrete time, which are algorithms that combines classical and quantum dynamics. We have demonstrated experimentally that the semiclassical walks can be applied on real quantum computers using the platform IBM Quantum.
  arXiv  Detail & Related papers  (2023-03-31T16:57:13Z)
• Quantum walks on random lattices: Diffusion, localization and the absence of parametric quantum speed-up [0.0]
  We study propagation of quantum walks on percolation-generated two-dimensional random lattices. We show that even arbitrarily weak concentrations of randomly removed lattice sites give rise to a complete breakdown of the superdiffusive quantum speed-up. The fragility of quantum speed-up implies dramatic limitations for quantum information applications of quantum walks on random geometries and graphs.
  arXiv  Detail & Related papers  (2022-10-11T10:07:52Z)
• Anticipative measurements in hybrid quantum-classical computation [68.8204255655161]
  We present an approach where the quantum computation is supplemented by a classical result. Taking advantage of its anticipation also leads to a new type of quantum measurements, which we call anticipative. In an anticipative quantum measurement the combination of the results from classical and quantum computations happens only in the end.
  arXiv  Detail & Related papers  (2022-09-12T15:47:44Z)
• Interactive Protocols for Classically-Verifiable Quantum Advantage [46.093185827838035]
  "Interactions" between a prover and a verifier can bridge the gap between verifiability and implementation. We demonstrate the first implementation of an interactive quantum advantage protocol, using an ion trap quantum computer.
  arXiv  Detail & Related papers  (2021-12-09T19:00:00Z)
• Sampling, rates, and reaction currents through reverse stochastic quantization on quantum computers [0.0]
  We show how to tackle the problem using a suitably quantum computer. We propose a hybrid quantum-classical sampling scheme to escape local minima.
  arXiv  Detail & Related papers  (2021-08-25T18:04:52Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• Quantum-classical distance as a tool to design optimal chiral quantum walk [0.0]
  Continuous-time quantum walks (CTQWs) provide a valuable model for quantum transport, universal quantum computation and quantum spatial search. We argue that the quantum-classical distance, a figure of merit introduced to capture the difference in dynamics between a CTQW and its classical counterpart, guides the optimization of parameters of the Hamiltonian.
  arXiv  Detail & Related papers  (2021-06-22T11:38:58Z)
• Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
  Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling. We examine the constraints of the observed quantum runtime advantage in a larger number of qubits and gates.
  arXiv  Detail & Related papers  (2020-05-05T20:11:53Z)
• Quantum Statistical Complexity Measure as a Signalling of Correlation Transitions [55.41644538483948]
  We introduce a quantum version for the statistical complexity measure, in the context of quantum information theory, and use it as a signalling function of quantum order-disorder transitions. We apply our measure to two exactly solvable Hamiltonian models, namely: the $1D$-Quantum Ising Model and the Heisenberg XXZ spin-$1/2$ chain. We also compute this measure for one-qubit and two-qubit reduced states for the considered models, and analyse its behaviour across its quantum phase transitions for finite system sizes as well as in the thermodynamic limit by using Bethe ansatz.
  arXiv  Detail & Related papers  (2020-02-05T00:45:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.