Abstract
Quantum walks [1–6] are quantum analogs of random walks on graphs and have widespread applications in several areas of quantum information processing [7]. In particular, they are a universal model for quantum computation and are crucial to the design of quantum algorithms for a plethora of problems such as element distinctness [8,9], searching for a marked state in graphs [10–16], matrix product verification [17], triangle finding [18], group commutativity [19], and many others [20–24]. In fact, for some oracular problems, quantum walks exhibit an exponential speedup over their classical counterparts [21,22]. For several of these algorithms, the runtime strongly depends on the time required for the quantum walk on a graph to localize at a vertex inside a marked set of vertices of interest. In the context of classical random walks, the hitting time is defined as the expected time required to hit a marked vertex. As such, the quantum hitting time characterizes the running time of the underlying quantum algorithm [14,15,20,21,25,26]. For continuous-time quantum walk (CTQW), the Hamiltonian governing the dynamics of the walk encodes the (vertex or edge) connectivity of the underlying graph. The dynamics involves evolving some initial state according to this Hamiltonian for time T , followed by a measurement in the basis spanned by the vertices of the graph, thus finding a target state with a high probability. However, Hamiltonian evolutions are unitary, and therefore, unlike classical random walks, quantum walks never converge to a fixed state with time. One method to address this is to evolve the system by H
