Review on Quantum Walk Computing: Theory, Implementation, and Application

Abstract

Classical random walk formalism shows a significant role across a wide range of applications. As its quantum counterpart, the quantum walk is proposed as an important theoretical model for quantum computing. By exploiting the quantum effects such as superposition, interference and entanglement, quantum walks and their variety have been extensively studied for achieving beyond classical computing power, and they have been broadly used in designing quantum algorithms in fields ranging from algebraic and optimization problems, graph and network analysis, to quantum Hamiltonian and biochemical process simulations, and even further quantum walk models have proven their capabilities for universal quantum computation. Compared to the conventional quantum circuit models, quantum walks show a feasible path for implementing application-specific quantum computing in particularly the noisy intermediate-scale quantum era. Recently remarkable progress has been achieved in implementing a wide variety of quantum walks and quantum walk applications, demonstrating the great potential of quantum walks. In this review, we provide a thorough summary of quantum walks and quantum walk computing, including aspects of quantum walk theories and characteristics, advances in their physical implementations and the flourishingly developed quantum walk computing applications. We also discuss the challenges facing quantum walk computing, toward realizing a practical quantum computer in the near future.