Connectivity is a Poor Indicator of Fast Quantum Search
arXiv:1409.5876 · doi:10.1103/PhysRevLett.114.110503
Abstract
A randomly walking quantum particle evolving by Schrödinger's equation searches on -dimensional cubic lattices in time when , and with progressively slower runtime as decreases. This suggests that graph connectivity (including vertex, edge, algebraic, and normalized algebraic connectivities) is an indicator of fast quantum search, a belief supported by fast quantum search on complete graphs, strongly regular graphs, and hypercubes, all of which are highly connected. In this paper, we show this intuition to be false by giving two examples of graphs for which the opposite holds true: one with low connectivity but fast search, and one with high connectivity but slow search. The second example is a novel two-stage quantum walk algorithm in which the walking rate must be adjusted to yield high search probability.
arXiv comment5 pages, 9 figures; additional 10 pages of supplemental material
References in corpus (4)
Cited by in corpus (57)
- Spatial search by quantum walk is optimal for almost all graphs
- Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs
- Quadratic speedup for spatial search by continuous-time quantum walk
- Laplacian versus Adjacency Matrix in Quantum Walk Search
- Perfect state transfer by means of discrete-time quantum walk search algorithms on highly symmetric graphs
- Optimal quantum spatial search on random temporal networks
- Faster Search by Lackadaisical Quantum Walk
- Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphs
- On the optimality of spatial search by continuous-time quantum walk
- Biunitary constructions in quantum information
- Continuous-Time Quantum Search on Balanced Trees
- Spatial Search by Continuous-Time Quantum Walk with Multiple Marked Vertices
- Quantum Search with Multiple Walk Steps per Oracle Query
- Quantum spatial search on graphs subject to dynamical noise
- Finding a marked node on any graph by continuous-time quantum walk
- Continuous-time quantum walks on dynamical percolation graphs
- Quantum spatial search in two-dimensional waveguide arrays
- Quantum Walk Search on Johnson Graphs
- Faster Quantum Walk Search on a Weighted Graph
- Diagrammatic Approach to Quantum Search
- Lackadaisical quantum walk for spatial search
- Analog quantum algorithms for the mixing of Markov chains
- Transport efficiency of continuous-time quantum walks on graphs
- Engineering topological states and quantum-inspired information processing using classical circuits
- Quantum Walk Search on Kronecker Graphs
- Irreconcilable Difference Between Quantum Walks and Adiabatic Quantum Computing
- Engineering the Success of Quantum Walk Search Using Weighted Graphs
- Quantum walk based state transfer algorithms on the complete M-partite graph
- Controlled quantum search on structured databases
- Long-lived quantum speedup based on plasmonic hot spot systems
- Quantum walk search by Grover search on coin space
- Spatial search by continuous-time quantum walks on renormalized Internet networks
- Realizable Quantum Adiabatic Search
- Quantum transport efficiency in noisy random-removal and small-world networks
- Search of clustered marked states with lackadaisical quantum walks
- Optimal Quantum Walk Search on Kronecker Graphs with Dominant or Fixed Regular Initiators
- On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids
- Role of symmetry in quantum search via continuous-time quantum walk
- Quantum walk search on a two-dimensional grid with extra edges
- Quantum search in many-body interacting system with long-range interaction
- Doubling the Success of Quantum Walk Search Using Internal-State Measurements
- Perfect chiral quantum routing
- Quantum search on Hanoi network
- Impact of global and local interaction on quantum spatial search on chimera graph
- Efficient quantum walk on the grid with multiple marked elements
- Short time behavior of continuous time quantum walks on graphs
- Improving the query complexity of quantum spatial search in two dimensions
- A Complete Characterization of Pretty Good State Transfer on Paths
- Quantum walks on two-dimensional grids with multiple marked locations
- Scalable Structure For Chiral Quantum Routing
- Optimal spatial searches with long-range tunneling
- Searching Weighted Barbell Graphs with Laplacian and Adjacency Quantum Walks
- Dimerized Decomposition of Quantum Evolution on an Arbitrary Graph
- Quantum search by continuous-time quantum walk on t-designs
- Quantum walk search for exceptional configurations
- Quantum Search with a Generalized Laplacian
- Application of graph theory in quantum computer science