Quantum searches on highly symmetric graphs
arXiv:0805.1237 · doi:10.1103/PhysRevA.79.012323
Abstract
We study scattering quantum walks on highly symmetric graphs and use the walks to solve search problems on these graphs. The particle making the walk resides on the edges of the graph, and at each time step scatters at the vertices. All of the vertices have the same scattering properties except for a subset of special vertices. The object of the search is to find a special vertex. A quantum circuit implementation of these walks is presented in which the set of special vertices is specified by a quantum oracle. We consider the complete graph, a complete bipartite graph, and an -partite graph. In all cases, the dimension of the Hilbert space in which the time evolution of the walk takes place is small (between three and six), so the walks can be completely analyzed analytically. Such dimensional reduction is due to the fact that these graphs have large automorphism groups. We find the usual quadratic quantum speedups in all cases considered.
11 pages, 6 figures; major revisions
References in corpus (11)
- Quantum Mechanics helps in searching for a needle in a haystack
- Quantum random walks - an introductory overview
- Quantum Computation and Decision Trees
- A Quantum Random Walk Search Algorithm
- Tight bounds on quantum searching
- Spatial search by quantum walk
- Quantum walks in higher dimensions
- Decoherence in quantum walks - a review
- Quantum information distributors: Quantum network for symmetric and asymmetric cloning in arbitrary dimension and continuous limit
- Quantum walks based on an interferometric analogy
- Quantum walks on quotient graphs
Cited by in corpus (40)
- Two-particle quantum walks applied to the graph isomorphism problem
- Optimized quantum random-walk search algorithms
- Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs
- Quantum walk-based search and centrality
- Perfect state transfer by means of discrete-time quantum walk search algorithms on highly symmetric graphs
- Quantum Walks
- Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphs
- Non-interacting multi-particle quantum random walks applied to the graph isomorphism problem for strongly regular graphs
- Searching via walking: How to find a marked subgraph of a graph using quantum walks
- Directional correlations in quantum walks with two particles
- Solving the Graph Isomorphism Problem with a Quantum Annealer
- Finding structural anomalies in graphs by means of quantum walks
- Quantum Walk Search on the Complete Bipartite Graph
- Equivalence between discrete quantum walk models in arbitrary topologies
- 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
- Grover search under localized dephasing
- Search by Lackadaisical Quantum Walk with Nonhomogeneous Weights
- Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk
- Robust Quantum Walk Search Without Knowing the Number of Marked Vertices
- Percolated quantum walks with a general shift operator: From trapping to transport
- 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
- Quantum search with interacting Bose-Einstein condensates
- Percolation assisted excitation transport in discrete-time quantum walks
- Quantum walk based state transfer algorithms on the complete M-partite graph
- The quantum walk search algorithm: Factors affecting efficiency
- Green function approach for scattering quantum walks
- Limit theorems for a localization model of 2-state quantum walks
- Adjustable self-loop on discrete-time quantum walk and its application in spatial search
- Quantum walk state transfer on a hypercube
- Entanglement of one-magnon Schur-Weyl states
- Scattering Quantum Random Walks on Square Grids and Randomly Generated Mazes
- Superdiffusivity of quantum walks: A Feynman sum-over-paths description
- Limit distribution with a combination of density functions for a 2-state quantum walk
- Coherence as resource in scattering quantum walk search on complete graph
- Enhancing the spreading of quantum walks on star graphs by additional bonds
- Search and state transfer between hubs by quantum walks
- Key graph properties affecting transport efficiency of flip-flop Grover percolated quantum walks