Searches on star graphs and equivalent oracle problems

Details Searches on star graphs and equivalent oracle problems Searches on star graphs and equivalent oracle problems

2011-02-27

arxiv.org/abs/1102.5480v1

Phys. Rev. A 83, 022318 (2011)

Physics

Quantum Physics

Scientific paper

10.1103/PhysRevA.83.022318

We examine a search on a graph among a number of different kinds of objects (vertices), one of which we want to find. In a standard graph search, all of the vertices are the same, except for one, the marked vertex, and that is the one we wish to find. We examine the case in which the unmarked vertices can be of different types, so the background against which the search is done is not uniform. We find that the search can still be successful, but the probability of success is lower than in the uniform background case, and that probability decreases with the number of types of unmarked vertices. We also show how the graph searches can be rephrased as equivalent oracle problems.

Affiliated with

Also associated with

No associations

Rating

Searches on star graphs and equivalent oracle problems 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 Searches on star graphs and equivalent oracle problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Searches on star graphs and equivalent oracle problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-53923