Laplacian versus adjacency matrix in quantum walk search

DOI10.1007/S11128-016-1373-1MaRDI QIDQ332103zbMATH OpenOpenAlexFDO

Authors Thomas G. Wong, Luís Tarrataca, Nikolay Nahimov

Publication date 27 October 2016

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.05554

zbMATH Keywords

adjacency matrixLaplaciancontinuous timequantum walkspatial search

Mathematics Subject Classification ID

Searching and sorting (68P10) Quantum computation (81P68)

Abstract: A quantum particle evolving by Schr"odinger'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.

Recommendations

• Walking on vertices and edges by continuous-time quantum walk
• Adjacent vertices can be hard to find by quantum walks
• QUANTUM WALKS ON GENERAL GRAPHS
• Grover search with lackadaisical quantum walks
• Adjacent vertices can be hard to find by quantum walks

Cites work

• scientific article; zbMATH DE number 5899272 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• Analysis and synchronization of a novel chaotic system based on Chen's system
• Birthday paradox, coupon collectors, caching algorithms and self- organizing search
• COMMUNICATION IN XYZ ALL-TO-ALL QUANTUM NETWORKS WITH A MISSING LINK
• Coupon Collecting for Uneqal Probabilities
• Deformations of spin structures and gravity
• Diagrammatic approach to quantum search
• Exponential algorithmic speedup by a quantum walk
• Grover search with lackadaisical quantum walks
• Laplacian state transfer in coronas
• Perfect state transfer in Laplacian quantum walk
• Spatial search by continuous-time quantum walk with multiple marked vertices

Cited in

(15)

• Degenerate perturbation theory to quantum search
• Vertices cannot be hidden from quantum spatial search for almost all random graphs
• Quantum walks in the normalized Laplacian
• Swift chiral quantum walks
• A new definition of hitting time and an embedded Markov chain in continuous-time quantum walks
• Exceptional quantum walk search on the cycle
• Ranking nodes in directed networks via continuous-time quantum walks
• Gluing of graph Laplacians and their spectra
• Lackadaisical discrete-time quantum walk on Johnson graph
• Classical and Quantum Random-Walk Centrality Measures in Multilayer Networks
• Decoherence and classicalization of continuous-time quantum walks on graphs
• Hamiltonians of bipartite walks
• Walking on vertices and edges by continuous-time quantum walk
• Universality of the fully connected vertex in Laplacian continuous-time quantum walk problems
• Search algorithm on strongly regular graph by lackadaisical quantum walk

This page was built for publication: Laplacian versus adjacency matrix in quantum walk search

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q332103)