Searching via walking: How to find a marked subgraph of a graph using quantum walks

Details Searching via walking: How to find a marked subgraph of a graph using quantum walks Searching via walking: How to find a marked subgraph of a graph using quantum walks

2009-11-05

arxiv.org/abs/0911.1102v1

Physics

Quantum Physics

4 pages, 2 figures

Scientific paper

We show how a quantum walk can be used to find a marked edge or a marked complete subgraph of a complete graph. We employ a version of a quantum walk, the scattering walk, which lends itself to experimental implementation. The edges are marked by adding elements to them that impart a specific phase shift to the particle as it enters or leaves the edge. If the complete graph has N vertices and the subgraph has K vertices, the particle becomes localized on the subgraph in O(N/K) steps. This leads to a quantum search that is quadratically faster than a corresponding classical search. We show how to implement the quantum walk using a quantum circuit and a quantum oracle, which allows us to specify the resource needed for a quantitative comparison of the efficiency of classical and quantum searches -- the number of oracle calls.

Affiliated with

Also associated with

No associations

Rating

Searching via walking: How to find a marked subgraph of a graph using 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 Searching via walking: How to find a marked subgraph of a graph using quantum walks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Searching via walking: How to find a marked subgraph of a graph using quantum walks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-418900