{"id":{"repo_id":"utc","oai_identifier":"oai:scholar.utc.edu:theses-2263"},"canonical_url":"https://search.dev.ndltd.org/etd/utc/oai:scholar.utc.edu:theses-2263","repository":{"repo_id":"utc","name":"University of Tennessee - Chattanooga","base_url":"https://scholar.utc.edu/do/oai/"},"display":{"title":"Combinatorial optimization using quantum computing","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Oppong, Gloria"],"institution":"University of Tennessee at Chattanooga","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Weerasena; Lakmali","Mukherjee; Rick; Cox, Christopher; Tucker, Emily","College of Arts and Sciences"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2026,"date_issued":"2026-11-30T08:00:00Z","date_published":"2026-11-30T08:00:00Z","updated_at":"2026-07-24T05:47:28Z","subjects":["Combinatorial optimization","Traveling salesman problem","Quantum computing"],"languages":["English","eng"],"rights":[],"rights_urls":["http://rightsstatements.org/vocab/InC/1.0/"],"identifier_entries":[]},"links":{"outbound_url":"https://scholar.utc.edu/theses/1075","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Weerasena; Lakmali","Mukherjee; Rick; Cox, Christopher; Tucker, Emily","College of Arts and Sciences"]},{"key":"dc:creator","label":"Author","values":["Oppong, Gloria"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2026-05-01T07:00:00Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2026-11-30T08:00:00Z"]},{"key":"dc:publisher","label":"Institution","values":["University of Tennessee at Chattanooga","Chattanooga (Tenn.)"]},{"key":"dc:relation","label":"Dc Relation","values":["Masters Theses and Doctoral Dissertations"]},{"key":"dc:type","label":"Dc Type","values":["Masters theses","Text"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Combinatorial optimization","Traveling salesman problem","Quantum computing"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["http://rightsstatements.org/vocab/InC/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://scholar.utc.edu/theses/1075"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Dept. of Mathematics","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."]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["Combinatorial optimization using quantum computing"]}]}],"canonical_facts":{"dc:contributor":["Weerasena; Lakmali","Mukherjee; Rick; Cox, Christopher; Tucker, Emily","College of Arts and Sciences"],"dc:creator":["Oppong, Gloria"],"dc:date":["2026-05-01T07:00:00Z"],"dc:date.available":["2026-11-30T08:00:00Z"],"dc:description":["Dept. of Mathematics","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."],"dc:description.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."],"dc:identifier":["https://scholar.utc.edu/theses/1075"],"dc:language":["English","eng"],"dc:publisher":["University of Tennessee at Chattanooga","Chattanooga (Tenn.)"],"dc:relation":["Masters Theses and Doctoral Dissertations"],"dc:rights":["http://rightsstatements.org/vocab/InC/1.0/"],"dc:subject":["Combinatorial optimization","Traveling salesman problem","Quantum computing"],"dc:title":["Combinatorial optimization using quantum computing"],"dc:type":["Masters theses","Text"]},"updated_at":"2026-07-24T05:47:28Z"}