A Comparative Investigation of Classical Random and Quantum Walks in Terms of Algorithms, Implementation, and Characteristics

Abstract: In recent years, there has been a significant development in high performance computing, driven by advances in hardware and software technology. The performance of the computers to the present has improved in accordance with Moore’s law, on the other hand, it seems to be reaching the limits in the near future. The quantum computers, which have the potential to greatly exceed the capabilities of the classical computers, have been the focus of intense researches. In the present study, we investigate the difference of the classical random walk and the quantum walk based on theoretical point of view and the implementation in the simulation, and seek the applicability of the quantum walk in the future. We provide the overview of the fundamental theory in the classical random walk and the quantum walk, and compare the differences of the features, based on the behaviors between the classical random walk and the quantum walk, and the probability distributions. Also, we implement the quantum walk using the Qiskit as the quantum simulator. The quantum circuit representing the quantum walk is mainly composed of the three parts, the coin operator, the shift operator, and the quantum measurement. The coin operator represent the coin flip in the quantum walk, where we use the Hadamard operator. The shift operator indicates the movement of the quantum walk according to the result of the coin operator. The quantum measurement is the process of extracting the quantum state of qubits. In one-dimensional quantum walk, we prepare four cases, as the difference of the number of qubits for the position from two to five qubits. In all cases, the successful implementation of the quantum walk has been seen with respect to the number of qubits and the difference of the initial state. We then extensively investigate the implementation of the two-dimensional quantum walk. In two-dimensional quantum walk, three cases are prepared in terms of the number of qubits for the position in each x and y coordinates, from two to four qubits. Although the complexity of the problem setting is much increased compared to the one-dimensional case, the success of the quantum walk implementation can be seen. We also see that the behavior of the quantum walk and the spread of the probability distribution strongly depends on the initial condition in terms of both the initial coin state and the initial position. The present study has shown the applicability of the quantum walk as the tool for solving the complex problems in a wide range of future applications. In concluding remarks, we offer conceivable perspectives and future prospects of the present study.