Continuous-Time Quantum Search on Balanced Trees
arXiv:1601.01154 · doi:10.1103/PhysRevA.93.032305
Abstract
We examine the effect of network heterogeneity on the performance of quantum search algorithms. To this end, we study quantum search on a tree for the oracle Hamiltonian formulation employed by continuous-time quantum walks. We use analytical and numerical arguments to show that the exponent of the asymptotic running time changes uniformly from to as the searched-for site is moved from the root of the tree towards the leaves. These results imply that the time complexity of the quantum search algorithm on a balanced tree is closely correlated with certain path-based centrality measures of the searched-for site.
References in corpus (14)
- Strengths and Weaknesses of Quantum Computing
- Subgraph Centrality in Complex Networks
- Communicability in complex networks
- Spatial search by quantum walk
- An example of the difference between quantum and classical random walks
- Spatial search by quantum walk is optimal for almost all graphs
- On the limiting behavior of parameter-dependent network centrality measures
- Quantum Google in a Complex Network
- Quantum walk approach to search on fractal structures
- Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs
- Connectivity is a Poor Indicator of Fast Quantum Search
- Quantum walk-based search and centrality
- Spatial Search by Continuous-Time Quantum Walk with Multiple Marked Vertices
- Faster Quantum Walk Search on a Weighted Graph
Cited by in corpus (25)
- On the optimality of spatial search by continuous-time quantum walk
- Quantum spatial search on graphs subject to dynamical noise
- Finding a marked node on any graph by continuous-time quantum walk
- Quantum spatial search in two-dimensional waveguide arrays
- Continuous Time Quantum Walks in finite Dimensions
- Continuous-Time Quantum Walks on Dynamic Graphs
- Spatial Search on Johnson Graphs by Continuous-Time Quantum Walk
- Continuous-time quantum walk spatial search on the Bollobás scale-free network
- Analog quantum algorithms for the mixing of Markov chains
- Quantum walks induced by Dirichlet random walks on infinite trees
- Classical and quantum random-walk centrality measures in multilayer networks
- Feedback-assisted quantum search by continuous-time quantum walks
- Vertices cannot be hidden from quantum spatial search for almost all random graphs
- Engineering the Success of Quantum Walk Search Using Weighted Graphs
- Continuous-time quantum walks in the presence of a quadratic perturbation
- Controlled quantum search on structured databases
- Role of symmetry in quantum search via continuous-time quantum walk
- Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact
- Impact of global and local interaction on quantum spatial search on chimera graph
- Multimarked Spatial Search by Continuous-Time Quantum Walk
- Short time behavior of continuous time quantum walks on graphs
- Quantum search by continuous-time quantum walk on t-designs
- Stable Configurations in Social Networks
- Application of graph theory in quantum computer science
- Implementation of Continuous-Time Quantum Walks on Quantum Computers