Improved Upper Bounds for the Hitting Times of Quantum Walks
arXiv:2005.04062 · doi:10.1103/PhysRevA.104.032215
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 to . 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 (25)
- Quantum random walks - an introductory overview
- Quantum Computation and Decision Trees
- A Quantum Random Walk Search Algorithm
- Exponential algorithmic speedup by quantum walk
- Environment-Assisted Quantum Transport
- Spatial search by quantum walk
- From quantum cellular automata to quantum lattice gases
- Universal computation by multi-particle quantum walk
- An example of the difference between quantum and classical random walks
- Search via Quantum Walk
- Faster quantum walk algorithm for the two dimensional spatial search
- Spatial search by quantum walk is optimal for almost all graphs
- Hitting time for quantum walks on the hypercube
- Thermally assisted adiabatic quantum computation
- Quantum Random Walks Hit Exponentially Faster
- Fast-forwarding of Hamiltonians and Exponentially Precise Measurements
- Quantum walks can find a marked element on any graph
- Quantum algorithms for hidden nonlinear structures
- Measuring Energy, Estimating Hamiltonians, and the Time-Energy Uncertainty Relation
- On the optimality of spatial search by continuous-time quantum walk
- Finding spin-glass ground states using quantum walks
- How fast do quantum walks mix?
- Finding a marked node on any graph by continuous-time quantum walk
- Analog quantum algorithms for the mixing of Markov chains
- Environment-assisted analog quantum search
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