Partition of graphs and quantum walk based search algorithms
arXiv:1812.06376
Abstract
In this paper, we show reduction methods for search algorithms on graphs using quantum walks. By using a graph partitioning method called equitable partition for the the given graph, we determine "effective subspace" for the search algorithm to reduce the size of the problem. We introduce the equitable partition for quantum walk based search algorithms and show how to determine "effective subspace" and reduced operator.
arXiv commentaccepted for publication in Nonlinear Theory and Its Applications
References in corpus (10)
- A Quantum Random Walk Search Algorithm
- Universal computation by quantum walk
- Exponential algorithmic speedup by quantum walk
- Spatial search by quantum walk
- Quantum Walk in Position Space with Single Optically Trapped Atoms
- Exploring Topological Phases With Quantum Walks
- Universal quantum computation using the discrete time quantum walk
- A 2D Quantum Walk Simulation of Two-Particle Dynamics
- Spatial search by quantum walk is optimal for almost all graphs
- Edge-state enhanced transport in a 2-dimensional quantum walk