Improved Upper Bounds for the Hitting Times of Quantum Walks

Abstract

Continuous-time quantum walks have proven to be an extremely useful framework for the design of several quantum algorithms. Often, the running time of quantum algorithms in this framework is characterized by the quantum hitting time: the time required by the quantum walk to find a vertex of interest with a high probability. In this article, we provide improved upper bounds for the quantum hitting time that can be applied to several CTQW-based quantum algorithms. In particular, we apply our techniques to the glued-trees problem, improving their hitting time upper bound by a polynomial factor: from $O(n^5)$ to $O(n^2\log n)$. Furthermore, our methods also help to exponentially improve the dependence on precision of the continuous-time quantum walk based algorithm to find a marked node on any ergodic, reversible Markov chain by Chakraborty et al. [PRA 102, 022227 (2020)].

References in corpus (11)

• Exponential algorithmic speedup by quantum walk
• Environment-Assisted Quantum Transport
• Spatial search by quantum walk
• Universal computation by multi-particle quantum walk
• Faster quantum walk algorithm for the two dimensional spatial search
• Quantum Random Walks Hit Exponentially Faster
• Quantum algorithms for hidden nonlinear structures
• Finding spin-glass ground states using quantum walks
• On the optimality of spatial search by continuous-time quantum walk
• How fast do quantum walks mix?
• Analog quantum algorithms for the mixing of Markov chains

Cited by in corpus (5)

• Quantum walk approach to simulating parton showers
• On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks
• Multiparameter estimation of continuous-time Quantum Walk Hamiltonians through Machine Learning
• Limit theorems and localization of three state quantum walks on a line defined by generalized Grover coins
• On Hitting Times for General Quantum Markov Processes