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 (5)
Cited by in corpus (40)
- 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
- Classical and quantum random-walk centrality measures in multilayer networks
- Link prediction with continuous-time classical and quantum walks
- Quantum-classical distance as a tool to design optimal chiral quantum walk
- Feedback-assisted quantum search by continuous-time quantum walks
- Transport efficiency of continuous-time quantum walks on graphs
- Continuous-time quantum walks on planar lattices and the role of the magnetic field
- Exceptional Quantum Walk Search on the Cycle
- Vertices cannot be hidden from quantum spatial search for almost all random graphs
- 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
- Continuous-time quantum walks in the presence of a quadratic perturbation
- Swift chiral quantum walks
- Spectrum of the tight-binding model on Cayley Trees and comparison with Bethe Lattices
- Role of topology in determining the precision of a finite thermometer
- 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
- Optimal Quantum Walk Search on Kronecker Graphs with Dominant or Fixed Regular Initiators
- Enhanced quantum transport in chiral quantum walks
- Asymptotic entropy of the Gibbs state of complex networks
- Multimarked Spatial Search by Continuous-Time Quantum Walk
- Multiple-scale integro-differential perturbation method for generic non-Markovian environments
- Scoring Anomalous Vertices Through Quantum Walks
- Searching Weighted Barbell Graphs with Laplacian and Adjacency Quantum Walks
- Optimization for the propagation of a multiparticle quantum walk in a one-dimensional lattice
- Decoherence and classicalization of continuous-time quantum walks on graphs
- Quantum Search with the Signless Laplacian
- Universality of the fully connected vertex in Laplacian continuous-time quantum walk problems
- Application of graph theory in quantum computer science
- Equivalent Laplacian and Adjacency Quantum Walks on Irregular Graphs
- Continuous-time quantum walks on a defective lattice: Boosting the spreading of delocalized states through Parrondo's strategy