Combinatorial Optimization using Quantum Computing

This study evaluates the potential of near-term quantum computing for combinatorial optimization, using the Traveling Salesman Problem (TSP) as a canonical benchmark. Using Qiskit, we construct a hybrid quantum-classical workflow based on the Quantum Approximate Optimization Algorithm (QAOA) and then assess its performance on symmetric TSP instances compared to classical exact methods (Gurobi solver). The Miller–Tucker–Zemlin formulation is implemented to create a Quadratic Unconstrained Binary Optimization (QUBO) encoding. Our findings show that conventional branch-and-bound solvers significantly outperform QAOA in both solution quality and runtime on existing hardware, even though QAOA successfully produces feasible tours. On Noisy Intermediate-Scale Quantum (NISQ) devices, the optimality gap for QAOA grows with problem size, demonstrating its sensitivity to hardware noise, penalty scaling, and variational changes in parameters. Among the tested classical optimizers within the QAOA loop, Constrained Optimization BY Linear Approximations (COBYLA) demonstrated the most practical balance between efficiency and noise tolerance. In order to improve near-term quantum heuristics, this paper validates a functional quantum optimization procedure and highlights key factors for optimizer selection, encoding choice, and error mitigation. We conclude that current NISQ technology does not currently provide a quantum advantage for TSP; rather, our work provides a systematic methodology and performance baselines that are essential for the development of future hybrid quantum-classical algorithms.