Searching via walking: How to find a marked subgraph of a graph using quantum walks
arXiv:0911.1102 · doi:10.1103/PhysRevA.81.062324
Abstract
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.
4 pages, 2 figures
References in corpus (12)
- Universal computation by quantum walk
- Spatial search by quantum walk
- Quantum Walk in Position Space with Single Optically Trapped Atoms
- 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
- Decoherence in quantum walks - a review
- Quantum walk on a line for a trapped ion
- Quantum walks on quotient graphs
- Quantum searches on highly symmetric graphs
Cited by in corpus (19)
- Quantum walks: a comprehensive review
- A 2D Quantum Walk Simulation of Two-Particle Dynamics
- Spontaneous Parametric Down-Conversion and Quantum Walks in Arrays of Quadratic Nonlinear Waveguides
- Parrondo's game using a discrete-time quantum walk
- Limit distributions of three-state quantum walks: the role of coin eigenstates
- Finding structural anomalies in graphs by means of quantum walks
- Spin systems dynamics and faults detection in threshold networks
- Finding paths in tree graphs with a quantum walk
- Engineering topological states and quantum-inspired information processing using classical circuits
- Framework for discrete-time quantum walks and a symmetric walk on a binary tree
- Finding paths with quantum walks or quantum walking through a maze
- Percolation assisted excitation transport in discrete-time quantum walks
- Unveiling and exemplifying the unitary equivalence of discrete time quantum walk models
- Finding Structural Anomalies in Star Graphs Using Quantum Walks: A General Approach
- Green function approach for scattering quantum walks
- Suitable bases for quantum walks with Wigner coins
- Superdiffusivity of quantum walks: A Feynman sum-over-paths description
- Scattering Quantum Random Walks on Square Grids and Randomly Generated Mazes
- Persistence of unvisited sites in quantum walks on a line