Finding structural anomalies in graphs by means of quantum walks

Details Finding structural anomalies in graphs by means of quantum walks Finding structural anomalies in graphs by means of quantum walks

2010-09-02

arxiv.org/abs/1009.0482v1

Physics

Quantum Physics

Scientific paper

We explore the possibility of using quantum walks on graphs to find structural anomalies, such as extra edges or loops, on a graph. We focus our attention on star graphs, whose edges are like spokes coming out of a central hub. If there are $N$ spokes, we show that a quantum walk can find an extra edge connecting two of the spokes or a spoke with a loop on it in $O(\sqrt{N})$ steps. We initially find that if all of the spokes have loops except one, the walk will not find the spoke without a loop, but this can be fixed if we choose the phase with which the particle is reflected from the vertex without the loop. Consequently, quantum walks can, under some circumstances, be used to find structural anomalies in graphs.

Affiliated with

Also associated with

No associations

Rating

Finding structural anomalies in graphs by means of quantum walks 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 Finding structural anomalies in graphs by means of quantum walks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding structural anomalies in graphs by means of quantum walks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-376677