Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Physica A Statistical Mechanics and its Applications

Hitting times of quantum and classical random walks in potential spaces

Georgios D. Varsamis, Ioannis G. Karafyllidis, Georgios Ch. Sirakoulis

Published Aug 27, 2022• 9 citations
Publisher
DOI
10.1016/j.physa.2022.128119

Related papers

Open Quantum Random Walks: Ergodicity, Hitting Times, Gambler’s Ruin and Potential Theory

Carlos F. Lardizabal, Rafael R. Souza

arXiv:1510.03454•Journal of Statistical Physics•Jul 11, 2016•21 citations

Quantization of Random Walks: Search Algorithms and Hitting Time

Miklós Sántha

Lecture notes in computer science•Jan 1, 2010•0 citations

Hitting time of quantum walks with perturbation

Chen-Fu Chiang, Guillermo Gomez

arXiv:1107.2965•Quantum Information Processing•Feb 8, 2012•6 citations

A path integral formula with applications to quantum random walks inZd

Wei-Shih Yang, Chaobin Liu, Kai Zhang

We consider general quantum random walks in a d -dimensional half-space. We first obtain a path integral formula for general quantum random walks in a d -dimensional space. Our path integral formula is valid for general quantum random walks on Cayley graphs as well. Then the path integral formula is applied to obtain the scaling limit of the exit distribution, the expectation of exit time and the asymptotic behaviour of the exit probabilities, for general quantum random walks in a half-space under some conditions on amplitude functions. The conditions are shown to be satisfied by both the Hadamard and Grover quantum random walks in two-dimensional half-spaces. For the two-dimensional case, we show that the critical exponent for the scaling limit of the hitting distribution is 1 as the lattice spacing tends to zero, i.e. the natural magnitude of the hitting position is of order O (1) if the lattice spacing is set to be 1/ n . We also show that the rate of convergence of the total hitting probability has lower bound n −2 and upper bound n −2+ for any > 0. For a quantum random walk with a fixed starting point, we show that the probability of hitting times at the hyperplane decays faster than that of the classical random walk. In both one and two dimensions, given the event of a hit, the conditional expectation of hitting times is finite, in contrast to being infinite for the classical case. In the one-dimensional case, we also obtain an exact order of the probability distribution of the hitting time at 0.

Journal of Physics A Mathematical and Theoretical•Jul 3, 2007•12 citations

On the hitting times of quantum versus random walks

Frédéric Magniez, Ashwin Nayak, Peter C. Richter +1 more

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.

Symposium on Discrete Algorithms•Jan 4, 2009•19 citations

On the Hitting Times of Quantum Versus Random Walks

Frédéric Magniez, Ashwin Nayak, Peter C. Richter +1 more

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.

arXiv:0808.0084•Algorithmica•Jan 4, 2009•17 citations
We consider general quantum random walks in a d -dimensional half-space. We first obtain a path integral formula for general quantum random walks in a d -dimensional space. Our path integral formula is valid for general quantum random walks on Cayley graphs as well. Then the path integral formula is applied to obtain the scaling limit of the exit distribution, the expectation of exit time and the asymptotic behaviour of the exit probabilities, for general quantum random walks in a half-space under some conditions on amplitude functions. The conditions are shown to be satisfied by both the Hadamard and Grover quantum random walks in two-dimensional half-spaces. For the two-dimensional case, we show that the critical exponent for the scaling limit of the hitting distribution is 1 as the lattice spacing tends to zero, i.e. the natural magnitude of the hitting position is of order O (1) if the lattice spacing is set to be 1/ n . We also show that the rate of convergence of the total hitting probability has lower bound n −2 and upper bound n −2+ for any > 0. For a quantum random walk with a fixed starting point, we show that the probability of hitting times at the hyperplane decays faster than that of the classical random walk. In both one and two dimensions, given the event of a hit, the conditional expectation of hitting times is finite, in contrast to being infinite for the classical case. In the one-dimensional case, we also obtain an exact order of the probability distribution of the hitting time at 0.
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.