Quantum walk-based search and centrality
arXiv:1010.0764 · doi:10.1103/PhysRevA.82.042333
Abstract
We study the discrete-time quantum walk-based search for a marked vertex on a graph. By considering various structures in which not all vertices are equivalent, we investigate the relationship between the successful search probability and the position of the marked vertex, in particular its centrality. We find that the maximum value of the search probability does not necessarily increase as the marked vertex becomes more central and we investigate an interesting relationship between the frequency of the successful search probability and the centrality of the marked vertex.
29 pages, 17 figures
References in corpus (12)
- Spatial search by quantum walk
- Discrete single-photon quantum walks with tunable decoherence
- Decoherence in quantum walks - a review
- Classical approach to the graph isomorphism problem using quantum walks
- Coherent exciton transport in dendrimers and continuous-time quantum walks
- Quantum walk approach to search on fractal structures
- Quantum searches on highly symmetric graphs
- Exact analytical results for quantum walks on star graph
- Dynamics of continuous-time quantum walks in restricted geometries
- Coherent dynamics on hierarchical systems
- Quantum walks and orbital states of a Weyl particle
- Random Walks on Complex Networks
Cited by in corpus (33)
- Quantum walks: a comprehensive review
- Efficient Quantum Walk on a Quantum Processor
- Centrality measure based on continuous-time quantum walks and experimental realization
- Review on Quantum Walk Computing: Theory, Implementation, and Application
- Combinatorial optimisation via highly efficient quantum walks
- Discrete-time quantum walk on complex networks for community detection
- Continuous-Time Quantum Search on Balanced Trees
- Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
- Implementation of multidimensional quantum walks using linear optics and classical light
- Experimental parity-time symmetry quantum walks on a directed graph
- QSWalk: a Mathematica package for quantum stochastic walks on arbitrary graphs
- Photonic quantum walks with four-dimensional coins
- Continuous-time quantum walk spatial search on the Bollobás scale-free network
- Generic Quantum Walks with Memory
- Quantum centrality testing on directed graphs via PT-symmetric quantum walks
- Classical and quantum random-walk centrality measures in multilayer networks
- One dimensional lazy quantum walks and occupancy rate
- Qcompiler: quantum compilation with CSD method
- Highly noise resistant multipartite quantum correlations
- Controlled quantum search on structured databases
- Localization of discrete time quantum walks on the glued trees
- Experimental Quantum Simulation of Dynamic Localization on Curved Photonic Lattices
- Adjustable self-loop on discrete-time quantum walk and its application in spatial search
- Quantum walks on two kinds of two-dimensional models
- Transfiguration of Quantum Walks on a line
- Induced on-demand revival in coined quantum walks on infinite -dimensional lattices
- Quantum Walk Inspired Neural Networks for Graph-Structured Data
- Quantum walk on simplicial complexes for simplicial community detection
- Quantum walks with spatiotemporal fractal disorder
- History states of one-dimensional quantum walks
- Optimizing Quantum Walk Search on a Reduced Uniform Complete Multi-Partite Graph
- Reversion of Quantum Walks via interventions on coin space
- Quantum Search on Simplicial Complexes