Quantum Optimization Methods for the Generalized Traveling Salesman Problem

Maximilian Zorn, Melinda Braun, Michael Ertl, Tommy Kiss, Sara Juarez Oropeza, Claudia Linnhoff-Popien, Jonas SteinarXiv 2026 · arXiv

TL;DR

This paper establishes the first comprehensive quantum optimization baselines for the Generalized Traveling Salesman Problem (GTSP) using both quantum annealing and gate-based QAOA. While both approaches successfully find optimal solutions for very small graphs, the study reveals that maintaining constraint feasibility—rather than finding the absolute shortest path—is the primary bottleneck preventing these methods from scaling on near-term quantum hardware.

What Problem Does This Paper Address?

The Traveling Salesman Problem (TSP) is a classic optimization challenge: find the shortest route that visits a set of cities exactly once and returns home. The Generalized Traveling Salesman Problem (GTSP) takes this a step further by grouping cities into disjoint clusters. The goal shifts to visiting exactly one representative city per cluster while minimizing total travel costs. This structure naturally models real-world industrial problems, such as optimizing a robot's path through a sequence of multi-variant subtasks (e.g., choosing between different welding angles or entry points).

While quantum approaches for the standard TSP have been heavily researched, the GTSP has been largely ignored in quantum literature. Because it introduces complex, multi-layered constraints (step-wise sequencing and cluster-selection rules), mapping it to quantum architectures without blowing up the qubit budget or destroying solution feasibility is incredibly difficult. This paper tackles that gap by designing and benchmarking the first end-to-end quantum pipelines for the GTSP.

Methods

The authors develop two distinct quantum optimization workflows and a classical preprocessing technique:

  1. Q-GTSP (Quantum Annealing): The authors formulate a novel Quadratic Unconstrained Binary Optimization (QUBO) matrix tailored for GTSP. Crucially, they mathematically define a strict penalty weight ($\lambda$) that acts as a trivial upper bound for any valid tour cost. This ensures that even the cheapest invalid solution is explicitly more expensive than the most expensive valid one, guiding the quantum annealer toward the feasible search space.
  2. C-QAOA (Constrained QAOA): For gate-based quantum computers, they implement a Quantum Approximate Optimization Algorithm pipeline. To minimize circuit depth and improve feasibility, they use a one-hot-preserving XY-mixer arranged in a low-depth ring topology. This natively enforces the constraint that exactly one node is visited per time step, while the remaining cluster constraints are managed via quadratic penalties.
  3. Extended NN2C Preprocessing: To combat the qubit limitations of Noisy Intermediate-Scale Quantum (NISQ) devices, the authors extend the classical Nearest Nodes to Clusters (NN2C) algorithm to handle asymmetric graphs. This method filters out nodes least likely to contribute to an optimal tour, reducing the node count per cluster down to a maximum of two (one optimal entry node and one exit node).

Datasets

The algorithms were evaluated using instances derived from GTSPLIB, the standard classical benchmark library for the GTSP. Because original instances are too large for current quantum hardware, the authors created two types of scaled-down datasets:

  • Subsampled Datasets (Small & Medium): Generated using a single-stage cluster sampling strategy that randomly selects whole clusters until a target node count (ranging from 3 to 20 nodes) is reached.
  • Preprocessed Datasets (Small & Medium): Created by taking original GTSPLIB instances (up to 100 nodes) and applying the authors' Extended NN2C method to shrink them down to NISQ-tractable sizes (3 to 20 nodes).

Key Insights and Ideas

  • Feasibility is the Real Enemy: The biggest hurdle for quantum GTSP solvers isn't finding the optimal tour out of a pool of valid ones; it's finding any valid tour at all. As instance sizes grow, the valid search space becomes a needle in a haystack.
  • The Penalty-Term Bottleneck: Relying on quadratic penalty terms to enforce complex constraints scales incredibly poorly. The energy landscapes become messy, causing solvers to frequently return invalid solutions.
  • Preprocessing is a Double-Edged Sword: The Extended NN2C preprocessing significantly boosted the feasibility rate for Quantum Annealing (up to 98% on small instances). However, it had the opposite effect on C-QAOA, increasing structural complexity and causing the simulator to time out or fail entirely on 5-node instances.

Key Results

  • Small-Scale Success: On very small graphs (3 to 5 nodes), both Q-GTSP (executed on D-Wave’s Advantage2 QPU) and C-QAOA (simulated via Qiskit Aer) consistently found optimal or near-optimal solutions.
  • The Scalability Cliff: Performance degraded sharply beyond 13–15 nodes. For the 11ft53 instance (13 nodes), the feasibility ratio for Quantum Annealing plummeted to a mere 0.1%, meaning the vast majority of shots yielded invalid tours.
  • Annealing vs. QAOA: Quantum Annealing generally outperformed the constrained QAOA variant in terms of feasibility stability. For example, on the preprocessed 3burma14 instance, Quantum Annealing achieved a 95.4% feasibility rate compared to C-QAOA’s 22.7%. However, the authors note this is partly due to limiting QAOA to a shallow layer depth ($p=1$).

Limitations and Future Work

The primary limitation of this study is the strict hardware constraint of the NISQ era: embedding overhead and qubit budgets limited physical evaluations to tiny graphs. Furthermore, due to QPU runtime limitations, QAOA experiments had to be simulated and restricted to a single layer ($p=1$), which inherently limits its optimization power.

The authors conclude that future quantum routing research must move away from simple penalty-based QUBO formulations. Instead, the path forward lies in developing advanced, problem-specific constraint-preserving mixers for QAOA that can natively restrict the quantum evolution entirely within the valid GTSP subspace.

Summary updated

Abstract

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.
BibTeX
@misc{zorn2026quantum,
  author = {Maximilian Zorn and Melinda Braun and Michael Ertl and Tommy Kiss and Sara Juarez Oropeza and Claudia Linnhoff-Popien and Jonas Stein},
  title = {{Quantum Optimization Methods for the Generalized Traveling Salesman Problem}},
  year = {2026},
  eprint = {2604.25531},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2604.25531},
}

Loading related content...

Figure