Open Collections

Tejani, Raveel

This thesis presents the development and analysis of a quantum algorithm tailored for solving the decision problem variant of the Bottleneck Travelling Salesman Problem (BTSP). The decision problem asks whether there exists a Hamiltonian cycle such that no edge weight within the cycle is less than a specified value (α). We construct two unitary matrices, both of whose eigenvalues are phases corresponding to the total cost associated with the Hamiltonian cycle. One matrix applies after all edge weights ≥ α are set to zero. Utilizing quantum phase estimation, we construct an algorithm to evaluate a Hamiltonian cycle of a graph before and after removing edge weights that do not satisfy the condition. If the total cost remains unaffected, we can conclude it is a solution. The proposed quantum algorithm maintains the inherent computational complexity of the classical BTSP, O((N − 1)!), yet introduces the potential for parallelization. We thoroughly examine the algorithm’s performance by applying it to both a 4-city and 5-city graph, simulating the quantum operations using Qiskit, an open-source quantum computing framework. Results from the simulations affirm that the algorithm effectively identifies minimized bottleneck paths. Notably, the thesis also delves into the potential scalability of the algorithm, assessing its applicability to larger graphs and more complex datasets. By analyzing various outcomes, we establish insights into the practical implementation of this quantum algorithm.

Text

University of British Columbia. PHYS 449

Vancouver : University of British Columbia Library

10.14288/1.0442410

Science, Faculty of; Physics and Astronomy, Department of

Undergraduate

DSpace