Controlled quantum search on structured databases
arXiv:1803.01481 · doi:10.1103/PhysRevResearch.1.033016
Abstract
We present quantum algorithms to search for marked vertices in structured databases with low connectivity. Adopting a multi-stage search process, we achieve a success probability close to on Cayley trees with large branching factors. We find that the number of stages required is given by the height of the Cayley tree. At each stage, the jumping rate should be chosen as different values. The dominant term of the runtime in the search process is proportional to for the Cayley tree of height with vertices. We further find that one can control the number of stages by adjusting the weight of the edges in the graphs. The multi-stage search process can be merged into a single stage, and then an optimal runtime proportional to is achieved, yielding a substantial speedup. The search process is quite robust under various kinds of small perturbations.
arXiv comment10 pages, 18 figures
References in corpus (45)
- 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
- Universal computation by quantum walk
- Quantum random access memory
- Quantum walks of correlated particles
- Quantum walks: a comprehensive review
- Spatial search by quantum walk
- Quantum Walk in Position Space with Single Optically Trapped Atoms
- Realization of quantum walks with negligible decoherence in waveguide lattices
- Realization of a quantum walk with one and two trapped ions
- Universal quantum computation using the discrete time quantum walk
- Anderson localization of entangled photons in an integrated quantum walk
- Quantum walk of a trapped ion in phase space
- Universal computation by multi-particle quantum walk
- Discrete single-photon quantum walks with tunable decoherence
- Architectures for a quantum random access memory
- Controlling discrete quantum walks: coins and intitial states
- Experimental Implementation of the Quantum Random-Walk Algorithm
- Experimental Two-dimensional Quantum Walk on a Photonic Chip
- Ideal negative measurements in quantum walks disprove theories based on classical trajectories
- Electric quantum walks with individual atoms
- Spatial search by quantum walk is optimal for almost all graphs
- Entanglement in coined quantum walks on regular graphs
- Observing Topological Invariants Using Quantum Walk in Superconducting Circuits
- Efficient Quantum Walk on a Quantum Processor
- Coherent exciton transport in dendrimers and continuous-time quantum walks
- Mimicking the probability distribution of a two-dimensional Grover walk with a single-qubit coin
- Quantum walk on a line for a trapped ion
- Quantum walk approach to search on fractal structures
- Global Symmetry is Unnecessary for Fast Quantum Search
- 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
- Experimental realisation of a delayed-choice quantum walk
- A Robust Quantum Random Access Memory
- Dynamics of continuous-time quantum walks in restricted geometries
- Degree Distribution in Quantum Walks on Complex Networks
- Rigorous free fermion entanglement renormalization from wavelet theory
- Continuous-Time Quantum Search on Balanced Trees
- Finding paths in tree graphs with a quantum walk
- Faster Quantum Walk Search on a Weighted Graph
- Localization in Quantum Walks on a Honeycomb Network
- Engineering the Success of Quantum Walk Search Using Weighted Graphs