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.
arXiv comment29 pages, 17 figures
References in corpus (23)
- 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
- Spatial search by quantum walk
- Quantum computers can search arbitrarily large databases by a single query
- Discrete single-photon quantum walks with tunable decoherence
- Controlling discrete quantum walks: coins and intitial states
- Decoherence in quantum walks - a review
- Modeling the Searching Behavior of Social Monkeys
- Entanglement in coined quantum walks on regular graphs
- Classical approach to the graph isomorphism problem using quantum walks
- Breakdown of an Electric-Field Driven System: a Mapping to a Quantum Walk
- Coherent exciton transport in dendrimers and continuous-time quantum walks
- Quantum walk approach to search on fractal structures
- Quantum searches on highly symmetric graphs
- Complementarity and quantum walks
- Exact analytical results for quantum walks on star graph
- Dynamics of continuous-time quantum walks in restricted geometries
- Coherent dynamics on hierarchical systems
- Relativistic effects in quantum walks: Klein's paradox and Zitterbewegung
- 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