Multimarked Spatial Search by Continuous-Time Quantum Walk

Abstract

The quantum-walk-based spatial search problem aims to find a marked vertex using a quantum walk on a graph with marked vertices. We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs by providing a recipe for finding the optimal running time and the success probability of the algorithm. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices. The success of our framework depends on the knowledge of the eigenvalues and eigenvectors of the adjacency matrix. The spectrum of the Hamiltonian is subsequently obtained from the roots of the determinant of a real symmetric matrix $M$, the dimensions of which depend on the number of marked vertices. The eigenvectors are determined from a basis of the kernel of $M$. We show each step of the framework by solving the spatial searching problem on the Johnson graphs with a fixed diameter and with two marked vertices. Our calculations show that the optimal running time is $O(\sqrt{N})$ with an asymptotic probability of $1+o(1)$, where $N$ is the number of vertices.

arXiv comment23 pages

References in corpus (27)

• Quantum Mechanics helps in searching for a needle in a haystack
• Quantum Computation and Decision Trees
• A Quantum Random Walk Search Algorithm
• Spatial search by quantum walk
• An example of the difference between quantum and classical random walks
• Search via Quantum Walk
• Distance-regular graphs
• Spatial search by quantum walk is optimal for almost all graphs
• Quantum walks can find a marked element on any graph
• Commutative association schemes
• Quadratic speedup for spatial search by continuous-time quantum walk
• Laplacian versus Adjacency Matrix in Quantum Walk Search
• On the optimality of spatial search by continuous-time quantum walk
• Continuous-Time Quantum Search on Balanced Trees
• Spatial Search by Continuous-Time Quantum Walk with Multiple Marked Vertices
• Quantum spatial search on graphs subject to dynamical noise
• Finding a marked node on any graph by continuous-time quantum walk
• Quantum spatial search in two-dimensional waveguide arrays
• Quantum walk-based search algorithms with multiple marked vertices
• Quantum Walk Search on Johnson Graphs
• Continuous-Time Quantum Walks on Dynamic Graphs
• Spatial Search on Johnson Graphs by Continuous-Time Quantum Walk
• Quantum search on the two-dimensional lattice using the staggered model with Hamiltonians
• Quantum search with a continuous-time quantum walk in momentum space
• Controlled quantum search on structured databases
• Staggered Quantum Walk on Hexagonal Lattices
• Quantum search by continuous-time quantum walk on t-designs

Cited by in corpus (1)

• Implementation of Continuous-Time Quantum Walks on Quantum Computers