Novel approach to solving stochastic constrained shortest path problem with quantum computing

• Main Author: Yang, Richard Chen Xiao
• Other Authors: Dusit Niyato
• Format: Final Year Project
• Language: English
• Published: Nanyang Technological University 2023
• Subjects: Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity
• Online Access: https://hdl.handle.net/10356/172135
• Institution: Nanyang Technological University

This thesis presents a new approach to tackling the stochastic constraint shortest path problem by using a quasi-optimal quantum algorithm. These problems are highly relevant in the real world, with broad applications in areas like transportation, logistics, and network optimization. We start the thesis by outlining the problem, explaining the limitations of traditional methods, and introducing the background information necessary to understanding our proposed algorithm. Then, we present our quantum-based solution and experiment results. Our unique algorithm combines classical techniques like Monte Carlo Sampling with quantum methods, like the Variational Quantum Eigensolver. The result is a potentially sub-exponential time complexity algorithm that is faster than what is achieved in classical computers. We conducted a thorough computational analysis to understand the algorithm's performance using the open-source quantum computing platform, Qiskit. Our findings suggest that the quantum algorithm shows promise in solving this problem faster, and provides reliable results. The results of this thesis suggest the potential of solving large-scale problems using quantum computers in the future.