Improved Upper Bound for Quantum Walks Hitting Times
Yosi Atia · arXiv (Cornell University) · 2020
In this letter, we present a novel upper-bound for the hitting time of continuous-time quantum walks, based on the spectrum and eigenstates of the Hamiltonian. We apply the new bound to the quantum walk algorithm for the glued-trees problem by Childs et al. (2002), improving their hitting time upper bound by a polynomial factor. The source of the improvement is that our bound depends on the energy gap of a single eigenspace from the rest of the spectrum, while the previous bound depended on the gap between any two eigenstates.