This paper studies quantum optimization baselines for the Generalized Traveling Salesman Problem (GTSP), a clustered routing problem that naturally models variant selection and sequencing problems under discrete alternatives. We propose a novel GTSP QUBO formulation focused on maintaining feasible solutions for quantum annealing, as well as a hardware-executable gate-based pipeline utilizing the Quantum Approximate Optimization Algorithm (QAOA). We implement a constrained QAOA variant using an XY-mixer, which preserves the stepwise Hamming weight in the ideal circuit model, while feasibility with respect to the full GTSP constraints is tracked explicitly during post-processing. We compare the two quantum optimization paradigms on problem instances from GTSPLIB, an established benchmark dataset, and validate against classical state-of-the-art solvers. To mitigate current quantum hardware size limitations, we further extend a preprocessing method to reduce the node count in instance clusters, constructing new NISQ-friendly instances from reduced subsets. Across all tested instances, quantum solvers often produce competitive solution quality when tested on smaller graphs, but exhibit higher runtimes and a sharp degradation in feasibility and scalability as instance size grows. Our evaluation highlights where quantum optimizers can already succeed and which algorithmic bottlenecks, like sampling rates, runtime issues, and other practical failure modes, remain as open problems.
This paper studies quantum optimization baselines for the Generalized Traveling Salesman Problem (GTSP), a clustered routing problem that naturally models variant selection and sequencing problems under discrete alternatives. We propose a novel GTSP QUBO formulation focused on maintaining feasible solutions for quantum annealing, as well as a hardware-executable gate-based pipeline utilizing the Quantum Approximate Optimization Algorithm (QAOA). We implement a constrained QAOA variant using an XY-mixer, which preserves the stepwise Hamming weight in the ideal circuit model, while feasibility with respect to the full GTSP constraints is tracked explicitly during post-processing. We compare the two quantum optimization paradigms on problem instances from GTSPLIB, an established benchmark dataset, and validate against classical state-of-the-art solvers. To mitigate current quantum hardware size limitations, we further extend a preprocessing method to reduce the node count in instance clusters, constructing new NISQ-friendly instances from reduced subsets. Across all tested instances, quantum solvers often produce competitive solution quality when tested on smaller graphs, but exhibit higher runtimes and a sharp degradation in feasibility and scalability as instance size grows. Our evaluation highlights where quantum optimizers can already succeed and which algorithmic bottlenecks, like sampling rates, runtime issues, and other practical failure modes, remain as open problems.
This study explores quantum computing for combinatorial optimization, focusing on the Traveling Salesman Problem (TSP). Using Qiskit, the Quantum Approximate Optimization Algorithm (QAOA) is implemented on simulators and quantum hardware, and compared with classical optimization using Gurobi. TSP instances are encoded as Quadratic Unconstrained Binary Optimization (QUBO) problems derived from the Miller–Tucker–Zemlin formulation, with quadratic penalties enforcing degree and subtour constraints. Results indicate that QAOA consistently generates feasible tours, but classical branch-and-bound methods achieve better solution quality and runtime. On Noisy Intermediate-Scale Quantum (NISQ) devices, performance degrades with problem size due to sensitivity to parameter tuning, penalty scaling, and hardware noise. Among the tested classical optimizers, COBYLA provides the best balance of 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.
The Traveling Salesman Problem (TSP) is a fundamental challenge in combinatorial optimization, widely applied in logistics and transportation. As the size of TSP instances grows, traditional algorithms often struggle to produce high-quality solutions within reasonable timeframes. This study investigates the potential of the Quantum Approximate Optimization Algorithm (QAOA), a hybrid quantum-classical method, to solve TSP under realistic constraints. We adopt a QUBO-based formulation of TSP that integrates real-world logistical constraints reflecting operational conditions, such as vehicle capacity, road accessibility, and time windows, while ensuring compatibility with the limitations of current quantum hardware. Our experiments are conducted in a simulated environment using high-performance computing (HPC) resources to assess QAOA's performance across different problem sizes and quantum circuit depths. In order to improve scalability, we propose clustering QAOA (Cl-QAOA), a hybrid approach combining classical machine learning with QAOA. This method decomposes large TSP instances into smaller sub-problems, making quantum optimization feasible even on devices with a limited number of qubits. The results offer a comprehensive evaluation of QAOA's strengths and limitations in solving constrained TSP scenarios. This study advances quantum optimization and lays groundwork for future large-scale applications.
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.
The traveling salesman problem (TSP) is one of the most often-used NP-hard problems in computer science to study the effectiveness of computing models and hardware platforms. In this regard, it is also heavily used as a vehicle to study the feasibility of the quantum computing paradigm for this class of problems. In this paper, we tackle the TSP using the quantum approximate optimization algorithm (QAOA) approach by formulating it as an optimization problem. By adopting an improved qubit encoding strategy and a layer-wise learning optimization protocol, we present numerical results obtained from the gate-based digital quantum simulator, specifically targeting TSP instances with 3, 4, and 5 cities. We focus on the evaluations of three distinctive QAOA mixer designs, considering their performances in terms of numerical accuracy and optimization cost. Notably, we find that a well-balanced QAOA mixer design exhibits more promising potential for gate-based simulators and realistic quantum devices in the long run, an observation further supported by our noise model simulations. Furthermore, we investigate the sensitivity of the simulations to the TSP graph. Overall, our simulation results show that the digital quantum simulation of problem-inspired ansatz is a successful candidate for finding optimal TSP solutions.
In this paper, we study the application of emerging photonic and quantum computing architectures to solving the Traveling Salesman Problem (TSP), a well-known NP-hard optimization problem. We investigate several approaches: Simulated Annealing (SA), Quadratic Unconstrained Binary Optimization (QUBO-Ising) methods implemented on quantum annealers and Optical Coherent Ising Machines, as well as the Quantum Approximate Optimization Algorithm (QAOA) and the Quantum Phase Estimation (QPE) algorithm on gate-based quantum computers. QAOA and QPE were tested on the IBM Quantum platform. The QUBO-Ising method was explored using the D-wave quantum annealer, which operates on superconducting Josephson junctions, and the Quantum Computing Inc (QCi) Dirac-1 entropy quantum optimization machine. Gate-based quantum computers demonstrated accurate results for small TSP instances in simulation. However, real quantum devices are hindered by noise and limited scalability. Circuit complexity grows with problem size, restricting performance to TSP instances with a maximum of six nodes. In contrast, Ising-based architectures show improved scalability for larger problem sizes. SQUID-based Ising machines can handle TSP instances with up to 12 nodes, while entropy computing implemented in hybrid optoelectronic components extend this capability to 18 nodes. Nevertheless, the solutions tend to be suboptimal due to hardware limitations and challenges in achieving ground state convergence as the problem size increases. Despite these limitations, Ising machines demonstrate significant time advantages over classical methods, making them a promising candidate for solving larger-scale TSPs efficiently.
The Traveling Salesman Problem (TSP) is one of the most often-used NP-Hard problems in computer science to study the effectiveness of computing models and hardware platforms. In this regard, it is also being used heavily as a vehicle to study the feasibility of the quantum computing paradigm for this class of problems. In this work, we formulate the symmetric TSP as an optimization problem, which we solve using the quantum approximate optimization algorithm (QAOA) approach. By adopting an improved qubit encoding strategy and a layerwise learning optimization protocol, we obtain numerical results on the gate-based digital quantum simulator for the 3-, 4-, and 5-city TSPs. Specifically, we focus on three QAOA mixer designs to evaluate their performances in terms of numerical accuracy and optimization cost. Based on our results, we propose that a well-balanced QAOA mixer design is more prominent on gate-based simulators or realistic quantum devices in the near future. In addition, we study the sensitivity of TSP graph properties such as graph skewness and penalty weight in the TSP-QAOA simulation. Overall, our results prove digital quantum simulation is a powerful candidate for obtaining the optimal solution to the TSP.