Finding a marked node on any graph by continuous-time quantum walk
arXiv:1807.05957 · doi:10.1103/PhysRevA.102.022227
Abstract
Spatial search by discrete-time quantum walk can find a marked node on any ergodic, reversible Markov chain quadratically faster than its classical counterpart, i.e.\ in a time that is in the square root of the hitting time of . However, in the framework of continuous-time quantum walks, it was previously unknown whether such general speed-up 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 . 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 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 . Secondly, using the framework of interpolated Markov chains, we provide a new spatial search algorithm by continuous-time quantum walk which can find a marked node on any 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 novel connection between discrete-time and continuous-time quantum walks and can be used to develop a number of Markov chain-based quantum algorithms.
arXiv commentThis version deals only with new algorithms for spatial search by continuous-time quantum walk (CTQW) on ergodic, reversible Markov chains. Please see arXiv:2004.12686 for results on the necessary and sufficient conditions for the optimality of the Childs and Goldstone algorithm for spatial search by CTQW
References in corpus (22)
- Hamiltonian Simulation by Qubitization
- Spatial search by quantum walk
- Quantum Metropolis Sampling
- Search via Quantum Walk
- Spatial search by quantum walk is optimal for almost all graphs
- Spatial search and the Dirac equation
- A Quantum-Quantum Metropolis Algorithm
- Quantum Google in a Complex Network
- Global Symmetry is Unnecessary for Fast Quantum Search
- Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs
- Connectivity is a Poor Indicator of Fast Quantum Search
- Quantum walks can find a marked element on any graph
- Optimal quantum spatial search on random temporal networks
- Quantum circuit implementation of the Hamiltonian versions of Grover's algorithm
- Spatial search by continuous-time quantum walks on crystal lattices
- Finding spin-glass ground states using quantum walks
- On the optimality of spatial search by continuous-time quantum walk
- Quantum search on graphene lattices
- Continuous-Time Quantum Search on Balanced Trees
- On the adiabatic condition and the quantum hitting time of Markov chains
- Quantum Walk Search on Johnson Graphs
- Analog quantum algorithms for the mixing of Markov chains
Cited by in corpus (18)
- Quadratic speedup for spatial search by continuous-time quantum walk
- Review on Quantum Walk Computing: Theory, Implementation, and Application
- On the optimality of spatial search by continuous-time quantum walk
- An energetic perspective on rapid quenches in quantum annealing
- Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
- How fast do quantum walks mix?
- Analog quantum algorithms for the mixing of Markov chains
- Feedback-assisted quantum search by continuous-time quantum walks
- Improved Upper Bounds for the Hitting Times of Quantum Walks
- Limit theorems and localization of three state quantum walks on a line defined by generalized Grover coins
- Impact of global and local interaction on quantum spatial search on chimera graph
- Multimarked Spatial Search by Continuous-Time Quantum Walk
- Quantum walk in a reinforced free-energy landscape: Quantum annealing with reinforcement
- On Hitting Times for General Quantum Markov Processes
- Searching via nonlinear quantum walk on the 2D-grid
- Quantum Hitting Time according to a given distribution
- Noise tolerance via reinforcement: Learning a reinforced quantum dynamics
- Application of graph theory in quantum computer science