Laplacian versus Adjacency Matrix in Quantum Walk Search
arXiv:1512.05554 · doi:10.1007/s11128-016-1373-1
Abstract
A quantum particle evolving by Schrödinger's equation contains, from the kinetic energy of the particle, a term in its Hamiltonian proportional to Laplace's operator. In discrete space, this is replaced by the discrete or graph Laplacian, which gives rise to a continuous-time quantum walk. Besides this natural definition, some quantum walk algorithms instead use the adjacency matrix to effect the walk. While this is equivalent to the Laplacian for regular graphs, it is different for non-regular graphs, and is thus an inequivalent quantum walk. We algorithmically explore this distinction by analyzing search on the complete bipartite graph with multiple marked vertices, using both the Laplacian and adjacency matrix. The two walks differ qualitatively and quantitatively in their required jumping rate, runtime, sampling of marked vertices, and in what constitutes a natural initial state. Thus the choice of the Laplacian or adjacency matrix to effect the walk has important algorithmic consequences.
21 pages, 8 figures
References in corpus (12)
- Exponential algorithmic speedup by quantum walk
- Spatial search by quantum walk
- Spatial search by quantum walk is optimal for almost all graphs
- Grover Search with Lackadaisical Quantum Walks
- Systematic Dimensionality Reduction for Quantum Walks: Optimal Spatial Search and Transport on Non-Regular Graphs
- Connectivity is a Poor Indicator of Fast Quantum Search
- A Quantum Algorithm for the Hamiltonian NAND Tree
- Spatial Search by Continuous-Time Quantum Walk with Multiple Marked Vertices
- Quantum Search with Multiple Walk Steps per Oracle Query
- Diagrammatic Approach to Quantum Search
- Faster Quantum Walk Search on a Weighted Graph
- Perfect State Transfer in Laplacian Quantum Walk
Cited by in corpus (41)
- Centrality measure based on continuous-time quantum walks and experimental realization
- On the optimality of spatial search by continuous-time quantum walk
- Quantum Walk Search on the Complete Bipartite Graph
- Generalized quantum-classical correspondence for random walks on graphs
- Quantum spatial search on graphs subject to dynamical noise
- Continuous-time quantum walks on dynamical percolation graphs
- Quantum Walk Search on Johnson Graphs
- Quantum-classical dynamical distance and quantumness of quantum walks
- Quantum-classical distance as a tool to design optimal chiral quantum walk
- Link prediction with continuous-time classical and quantum walks
- Classical and quantum random-walk centrality measures in multilayer networks
- Transport efficiency of continuous-time quantum walks on graphs
- Feedback-assisted quantum search by continuous-time quantum walks
- Continuous-time quantum walks on planar lattices and the role of the magnetic field
- Vertices cannot be hidden from quantum spatial search for almost all random graphs
- Exceptional Quantum Walk Search on the Cycle
- Irreconcilable Difference Between Quantum Walks and Adiabatic Quantum Computing
- Isolated Vertices in Continuous-Time Quantum Walks on Dynamic Graphs
- Scattering as a quantum metrology problem: a quantum walk approach
- Engineering the Success of Quantum Walk Search Using Weighted Graphs
- Swift chiral quantum walks
- Continuous-time quantum walks in the presence of a quadratic perturbation
- Spectrum of the tight-binding model on Cayley Trees and comparison with Bethe Lattices
- Non-reciprocity is necessary for robust dimensional reduction and strong responses in stochastic topological systems
- Quantum hub and authority centrality measures for directed networks based on continuous-time quantum walks
- Role of topology in determining the precision of a finite thermometer
- Optimal Quantum Walk Search on Kronecker Graphs with Dominant or Fixed Regular Initiators
- Quantum Walk Search through Potential Barriers
- Enhanced quantum transport in chiral quantum walks
- Multiple-scale integro-differential perturbation method for generic non-Markovian environments
- Multimarked Spatial Search by Continuous-Time Quantum Walk
- Scoring Anomalous Vertices Through Quantum Walks
- Asymptotic entropy of the Gibbs state of complex networks
- Searching Weighted Barbell Graphs with Laplacian and Adjacency Quantum Walks
- Quantum Search with the Signless Laplacian
- Optimization for the propagation of a multiparticle quantum walk in a one-dimensional lattice
- Decoherence and classicalization of continuous-time quantum walks on graphs
- Continuous-time quantum walks on a defective lattice: Boosting the spreading of delocalized states through Parrondo's strategy
- Equivalent Laplacian and Adjacency Quantum Walks on Irregular Graphs
- Application of graph theory in quantum computer science
- Universality of the fully connected vertex in Laplacian continuous-time quantum walk problems