Committee Chair
Weerasena; Lakmali
Committee Member
Mukherjee; Rick; Cox, Christopher; Tucker, Emily
College
College of Arts and Sciences
Publisher
University of Tennessee at Chattanooga
Place of Publication
Chattanooga (Tenn.)
Abstract
This thesis explores quantum computing for combinatorial optimization through the Traveling Salesman Problem (TSP), which aims to find a minimum-cost Hamiltonian cycle visiting each city exactly once. Using Qiskit, we implement the Quantum Approximate Optimization Algorithm (QAOA) on both simulators and quantum hardware, and compare its performance with that of classical exact optimization via the Gurobi solver. TSP instances are encoded as Quadratic Unconstrained Binary Optimization (QUBO) problems derived from the Miller–Tucker–Zemlin formulation, with degree and subtour constraints embedded using quadratic penalties. Results indicate that QAOA consistently generates feasible tours, but classical branch-and-bound solvers outperform it in both solution quality and runtime. On Noisy Intermediate-Scale Quantum (NISQ) devices, the optimality gap grows with problem size, reflecting sensitivity to variational parameter tuning, penalty scaling, and hardware noise. Among classical optimizers for QAOA, COBYLA offers the most effective tradeoff between efficiency and noise tolerance. Overall, this work establishes a reproducible quantum-classical workflow, provides performance baselines, and identifies critical factors such as encoding design, optimizer choice, and error mitigation for improving near-term quantum heuristic performance.
Acknowledgments
This research was made possible through the support and guidance of many people. First, I would like to thank the Mathematics Department and the Graduate School of UTC for providing me with the opportunity to earn a graduate degree in Mathematics. Additionally, I would like to extend my sincerest gratitude to my Supervisor and Mentor, Prof. Lakmali Weerasena, for her remarkable guidance and direction throughout the research process. Further, I would like to express my heartfelt gratitude to my committee members, Prof. Christopher L. Cox, Prof. Emily Tucker, and Prof. Rick Mukherjee, for the valuable feedback and suggestions they provided.
Degree
M. S.; A thesis submitted to the faculty of the University of Tennessee at Chattanooga in partial fulfillment of the requirements of the degree of Master of Science.
Date
5-2026
Subject
Combinatorial optimization; Traveling salesman problem; Quantum computing
Document Type
Masters theses
DCMI Type
Text
Extent
xi, 107 leaves
Language
English
Rights
http://rightsstatements.org/vocab/InC/1.0/
License
http://creativecommons.org/licenses/by/4.0/
Date Available
11-30-2026
Recommended Citation
Oppong, Gloria, "Combinatorial optimization using quantum computing" (2026). Masters Theses and Doctoral Dissertations.
https://scholar.utc.edu/theses/1075
Department
Dept. of Mathematics