Quantum walk and its application domains: A systematic review

Quantum random walk is the quantum counterpart of a classical random walk. The classical random walk concept has long been used as a computational framework for designing classical algorithms for complex problems. Quantum analogues of random walk provide speed-up in computational power for various algorithms such as element distinctness, spatial search, graph connectivity, etc. Quantum walks have emerged to be a universal computational model over the last decade. Quantum walk formulations applied in graph theory have shown quadratic and polynomial time in graph traversal as opposed to the exponential time taken by classical algorithms. Quantum walk models have also found use in designing quantum computers. Inspired by these facts, this article presents a substantial systematic literature review and analysis of various quantum walk formulations and their strengths and limitations w.r.t. application domains used in literature up-to-date by researchers in various fields. The analysis provided in this article may help upcoming researchers to gain new insights towards the application of quantum walk formulation in varied domains. Various performance metrics, physical implementation set-ups, coin operators, and simulators used to analyze classical and quantum walk dynamics on graphs have been described. Finally, the article discusses existing open problems and notable future directions related to quantum walk application for potential researchers.