Quantum Optimization Methods for the Generalized Traveling Salesman Problem
Quantum computers can solve a complex routing problem on small instances, but classical solvers still dominate as problem size grows.
The Thesis
The Generalized Traveling Salesman Problem (GTSP) asks a traveler to visit exactly one city from each of several pre-defined clusters — a structure that shows up naturally in supply-chain variant selection, gene sequencing, and manufacturing job routing. This paper tests two quantum optimization approaches against classical solvers on that problem: quantum annealing (a hardware technique that exploits quantum tunneling to find low-energy solutions) and QAOA, the Quantum Approximate Optimization Algorithm (a gate-based circuit approach that mixes quantum and classical computation iteratively). The honest finding is that quantum methods match classical quality only on the smallest instances, and they get substantially slower and less reliable as the problem grows. The paper is a careful, self-aware benchmarking study — not a breakthrough claim — and its value is in mapping exactly where quantum optimizers succeed and where they break down today.
Catalyst
NISQ-era hardware — meaning Noisy Intermediate-Scale Quantum devices with dozens to hundreds of qubits but significant error rates — has matured just enough that researchers can run meaningful small-scale experiments on real machines rather than simulators alone. Benchmark libraries like GTSPLIB now provide standardized, reproducible problem instances, making apples-to-apples comparisons across paradigms possible. At the same time, classical solvers for combinatorial routing have become so strong that any honest quantum evaluation must contend with them directly, which this paper does.
What's New
Prior quantum work on routing problems focused almost exclusively on the standard Traveling Salesman Problem (TSP), where a traveler must visit every city exactly once. The GTSP adds a cluster structure — visit one city per group — which dramatically changes the problem's constraint geometry. Earlier QUBO formulations (QUBO stands for Quadratic Unconstrained Binary Optimization, the mathematical format quantum annealers require) for routing tended to embed all constraints loosely, leading to many infeasible outputs. This paper introduces a new GTSP QUBO designed to keep solutions feasible during annealing, and it also implements a constrained QAOA variant using an XY-mixer — a specialized quantum gate sequence that preserves the number of '1' bits in a solution string, naturally enforcing the 'pick exactly one city per cluster' rule.
The Counter
This paper is largely a confirmation of what the quantum computing community already suspects: quantum optimization does not beat classical solvers on practically relevant problem sizes, and it isn't close. The authors candidly acknowledge that feasibility — the fraction of outputs that are even valid solutions — degrades sharply as instance size grows, which is a fundamental problem, not a tuning issue. The QUBO formulation requires embedding problem constraints as penalty terms, a process that consumes additional qubits and makes the energy landscape harder to navigate; as problems grow, this overhead compounds. The XY-mixer QAOA approach is theoretically elegant but requires deep circuits with many two-qubit gates, which current noisy hardware executes poorly. Classical heuristics like the Lin-Kernighan-Helsgott solver have decades of engineering behind them and solve large GTSP instances in seconds. Nothing in this paper suggests a near-term path to quantum advantage on real-world routing scales — the smallest 'NISQ-friendly' instances tested here are trivial for classical methods. The contribution is honest documentation of failure modes, which is scientifically valuable but not commercially exciting.
Longs
- IONQ — gate-based quantum hardware directly relevant to QAOA experiments
- QBTS (D-Wave Quantum) — quantum annealing hardware tested in this class of work
- RGTI (Rigetti Computing) — superconducting NISQ hardware for combinatorial optimization
- QTUM (ETF) — broad quantum computing index exposure
- IBM (IBM) — quantum cloud access via IBM Quantum used in QAOA research
Shorts
- Classical combinatorial optimization software vendors (e.g., Gurobi, CPLEX) face long-term narrative pressure if quantum methods ever scale — but this paper actually reinforces their current dominance
- Early-stage quantum software startups overselling near-term routing advantages may face credibility erosion as honest benchmark studies like this proliferate
Enablers (Picks & Shovels)
- GTSPLIB — the open benchmark dataset used for standardized evaluation in this paper
- Qiskit — IBM's open-source quantum SDK used for QAOA circuit construction
- D-Wave Ocean SDK — software stack for formulating and submitting QUBO problems to annealing hardware
- GTSP classical solvers (Helsgott, LKH-3) — the baseline comparators that set the performance bar any quantum approach must beat
Private Watchlist
- 1QBit — quantum software focused on combinatorial optimization
- Multiverse Computing — quantum and quantum-inspired optimization for logistics
- Qubit Pharmaceuticals — quantum methods for discrete selection problems (adjacent domain)
- Qu & Co (now Pasqal partnership) — quantum algorithms for industry optimization
Resources
The Paper
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.