View Proposal

---

Proposer

Kai Lin Ong

Title

Quantum Walk Based Path Finding in Graphs

Goal

Description

Path finding is a fundamental problem in computer science, with applications in robotics, network routing, game development and artificial intelligence. Classical algorithms such as Breadth-First Search (BFS), Dijkstra's algorithm and A* search are widely used to identify paths between vertices in a graph. This project investigates whether quantum walks (the quantum analogue of random walks) can provide an alternative approach to path finding and how their behaviour compares with classical methods. A simulation of a discrete-time quantum walk on graphs will be developed, where the walker evolves through a combination of a coin operation and a shift operator. Different graph structures, including grids, cycles and general connected graphs, will be considered. A marked vertex will represent the target, and a quantum-walk-based search mechanism will be investigated for identifying paths from a specified starting vertex to the target. Finally, their performance will be compared with the classical algorithms.

Resources

Portugal, R. (2013). Quantum walks and search algorithms. Springer. https://doi.org/10.1007/978-1-4614-6336-8 Reitzner, D., Hillery, M., & Koch, D. (2017). Finding paths with quantum walks or quantum walking through a maze. Physical Review A, 96(3), 032323. https://doi.org/10.1103/PhysRevA.96.032323 Matsuoka, L., Yuki, K., Lavička, H., & Segawa, E. (2021). Maze Solving by a Quantum Walk with Sinks and Self-Loops: Numerical Analysis. Symmetry, 13(12), 2263. https://doi.org/10.3390/sym13122263

Background

Url

Difficulty Level

Variable

Ethical Approval

None

Number Of Students

1

Supervisor

Kai Lin Ong

Keywords

quantum computing, search algorithms, path finding, quantum walk

Degrees

Bachelor of Science in Computing Science