Physics – Quantum Physics
Scientific paper
2008-05-08
Phys. Rev. A 79, 012323 (2009)
Physics
Quantum Physics
11 pages, 6 figures; major revisions
Scientific paper
10.1103/PhysRevA.79.012323
We study scattering quantum walks on highly symmetric graphs and use the walks to solve search problems on these graphs. The particle making the walk resides on the edges of the graph, and at each time step scatters at the vertices. All of the vertices have the same scattering properties except for a subset of special vertices. The object of the search is to find a special vertex. A quantum circuit implementation of these walks is presented in which the set of special vertices is specified by a quantum oracle. We consider the complete graph, a complete bipartite graph, and an $M$-partite graph. In all cases, the dimension of the Hilbert space in which the time evolution of the walk takes place is small (between three and six), so the walks can be completely analyzed analytically. Such dimensional reduction is due to the fact that these graphs have large automorphism groups. We find the usual quadratic quantum speedups in all cases considered.
Buzek Vladimir
Feldman Edgar
Hillery Mark
Reitzner Daniel
No associations
LandOfFree
Quantum searches on highly symmetric graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quantum searches on highly symmetric graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum searches on highly symmetric graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-331918