Searches on star graphs and equivalent oracle problems
arXiv:1102.5480 · doi:10.1103/PhysRevA.83.022318
Abstract
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.
References in corpus (19)
- Quantum Mechanics helps in searching for a needle in a haystack
- Strengths and Weaknesses of Quantum Computing
- A Quantum Random Walk Search Algorithm
- Quantum walks of correlated particles
- Tight bounds on quantum searching
- Quantum Walk in Position Space with Single Optically Trapped Atoms
- Grover's quantum searching algorithm is optimal
- Photons Walking the Line: A quantum walk with adjustable coin operations
- Realization of quantum walks with negligible decoherence in waveguide lattices
- Realization of a quantum walk with one and two trapped ions
- Quantum walk of a trapped ion in phase space
- Discrete single-photon quantum walks with tunable decoherence
- Implementing the quantum random walk
- Quantum random walks in optical lattices
- Quantum walk on the line as an interference phenomenon
- Optimized quantum random-walk search algorithms
- Quantum walk on a line for a trapped ion
- Quantum walks based on an interferometric analogy
- Simulation of quantum random walks using interference of classical field
Cited by in corpus (7)
- Quantum walks as a probe of structural anomalies in graphs
- Finding structural anomalies in star graphs: A general approach
- Finding paths in tree graphs with a quantum walk
- Finding paths with quantum walks or quantum walking through a maze
- Green function approach for scattering quantum walks
- Scattering Quantum Random Walks on Square Grids and Randomly Generated Mazes
- Superdiffusivity of quantum walks: A Feynman sum-over-paths description