Combinatorial optimization using quantum computing

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.

Grantor dc:publisher

University of Tennessee at Chattanooga

Year dc:date.available

2026

Author dc:creator

• Oppong, Gloria

Contributors dc:contributor

• Weerasena; Lakmali
• Mukherjee; Rick; Cox, Christopher; Tucker, Emily
• College of Arts and Sciences

• Combinatorial optimization
• Traveling salesman problem
• Quantum computing

Licence

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language

English, eng

Repository record dc:identifier

https://scholar.utc.edu/theses/1075

OAI identifier oai:identifier

oai:scholar.utc.edu:theses-2263