Abstract

Continuous-time quantum walks provide a natural framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search. Whether spatial search by continuous-time quantum walk provides a quadratic advantage over classical random walks has been an outstanding problem. Thus far, this advantage is obtained only for specific graphs or when a single node of the underlying graph is marked. In this article, we provide a new continuous-time quantum walk search algorithm that completely resolves this: our algorithm can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks. The overall algorithm is quite simple, requiring time evolution of the quantum walk Hamiltonian followed by a projective measurement. A key component of our algorithm is a purely analog procedure to perform operations on a state of the form $e^{-tH^2}|\psi\rangle$, for a given Hamiltonian H: it only requires evolving H for time scaling as $\sqrt{t}$. This allows us to quadratically fast-forward the dynamics of a continuous-time classical random walk. The applications of our work thus go beyond the realm of quantum walks and can lead to new analog quantum algorithms for preparing ground states of Hamiltonians or solving optimization problems.

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

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)].