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.
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.
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 continuous-time quantum walk (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(n5) to O(n2logn). Furthermore, our methods also help to exponentially improve the dependence on precision of the CTQW based algorithm to find a marked node on any ergodic, reversible Markov chain by Chakraborty et al. [Phys. Rev. A 102, 022227 (2020)].
Quantum walks on graphs play an important role in the field of quantum algorithms. Fast hitting is one of the properties that quantum walk algorithms can utilize to outperform classical random walk algorithms. Fast hitting refers to a particle starting from the entrance node on a graph and trying to hit the exit node quickly. Especially, continuous-time quantum walks on random glued binary trees have been investigated in theories extensively for their exponentially faster hitting speed over classical random walks. Here, using heralded single photons to represent quantum walkers and laser-written waveguide arrays to simulate the theoretical graph, we are able to demonstrate the hitting efficiency of quantum walks with tree depth as high as 16 layers for the first time. Furthermore, we expand the graph’s branching rate from 2 to 5, revealing that quantum walks can exhibit more superiority over classical random walks as the branching rate increases. Our results may shed light on the physical implementation of quantum walk algorithms as well as quantum computation and quantum simulation.
In this paper, we explore analytically and experimentally a quasi-quantum analogue of the hitting time of the continuous-time quantum walk on a graph. For the classical random walk, the hitting time has been shown to be robust to errors in edge weight structure and to lead to spectral clustering algorithms with improved performance. Our analysis shows that the quasi-quantum analogue of the hitting time of the continuoustime quantum walk can be determined via integrals of the Laplacian spectrum, calculated using Gauss-Laguerre quadrature. We analyse the quantum hitting times with reference to their classical counterpart. Specifically, we explore the graph embeddings that preserve hitting time. Experimentally, we show that the quantum hitting times can be used to emphasise cluster-structure.
In this paper, we explore analytically and experimentally a quasi-quantum analogue of the hitting time of the continuous-time quantum walk on a graph. For the classical random walk, the hitting time has been shown to be robust to errors in edge weight structure and to lead to spectral clustering algorithms with improved performance. Our analysis shows that the quasi-quantum analogue of the hitting time of the continuous-time quantum walk can be determined via integrals of the Laplacian spectrum, calculated using Gauss-Laguerre quadrature. We analyse the quantum hitting times with reference to their classical counterpart. Specifically, we explore the graph embeddings that preserve hitting time. Experimentally, we show that the quantum hitting times can be used to emphasise cluster-structure.
One of the most important algorithmic applications of quantum walks is to solve spatial search problems. A widely used quantum algorithm for this problem, introduced by Childs and Goldstone [Phys. Rev. A 70, 022314 (2004)], finds a marked node on a graph of n nodes via a continuous-time quantum walk. This algorithm is said to be optimal if it can find any of the nodes in O(n) time. However, given a graph, no general conditions for the optimality of the algorithm are known and previous works demonstrating optimal quantum search for certain graphs required an instance-specific analysis. In fact, the demonstration of the necessary and sufficient conditions that a graph must fulfill for quantum search to be optimal has been a long-standing open problem. In this work we make significant progress towards solving this problem. We derive general expressions, depending on the spectral properties of the Hamiltonian driving the walk, that predict the performance of this quantum search algorithm provided certain spectral conditions are fulfilled. Our predictions are valid, for example, for (normalized) Hamiltonians whose spectral gap is considerably larger than ${n}^{\ensuremath{-}1/2}$. This allows us to derive necessary and sufficient conditions for optimal quantum search in this regime, as well as provide examples of graphs where quantum search is suboptimal. In addition, by extending this analysis, we are also able to show the optimality of quantum search for certain graphs with very small spectral gaps, such as graphs that can be efficiently partitioned into clusters. Our results imply that, to the best of our knowledge, all prior results analytically demonstrating the optimality of this algorithm for specific graphs can be recovered from our general results.
Spatial search by a discrete-time quantum walk can find a marked node on any ergodic, reversible Markov chain P quadratically faster than its classical counterpart, i.e., in a time that is in the square root of the hitting time of P. However, in the framework of continuous-time quantum walks, it was previously unknown whether such general speedup is possible. In fact, in this framework, the widely used quantum algorithm by Childs and Goldstone fails to achieve such a speedup. Furthermore, it is not clear how to apply this algorithm for searching any Markov chain P. In this article we aim to reconcile the apparent differences between the running times of spatial search algorithms in these two frameworks. We first present a modified version of the Childs and Goldstone algorithm which can search for a marked element for any ergodic, reversible P by performing a quantum walk on its edges. Although this approach improves the algorithmic running time for several instances, it cannot provide a generic quadratic speedup for any P. Second, using the framework of interpolated Markov chains, we provide a spatial search algorithm by a continuous-time quantum walk which can find a marked node on any P in the square root of the classical hitting time. In the scenario where multiple nodes are marked, the algorithmic running time scales as the square root of a quantity known as the extended hitting time. Our results establish a connection between discrete-time and continuous-time quantum walks and can be used to develop a number of Markov chain-based quantum algorithms.