arxiv: 2604.25531 · v1 · submitted 2026-04-28 · 🪐 quant-ph · cs.ET

Recognition: unknown

Quantum Optimization Methods for the Generalized Traveling Salesman Problem

Maximilian Zorn , Melinda Braun , Michael Ertl , Tommy Kiss , Sara Juarez Oropeza , Claudia Linnhoff-Popien , Jonas Stein

Authors on Pith no claims yet

Pith reviewed 2026-05-07 16:45 UTC · model grok-4.3

classification 🪐 quant-ph cs.ET

keywords quantum optimizationgeneralized traveling salesman problemQAOAquantum annealingQUBOclustered routingNISQ benchmarks

0 comments

The pith

Quantum annealing and QAOA produce competitive GTSP solutions on small graphs but degrade sharply as size increases.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The authors establish quantum optimization baselines for the Generalized Traveling Salesman Problem by creating a QUBO formulation tailored for annealing hardware and a gate-based QAOA pipeline that uses an XY mixer to keep the circuit feasible in the ideal model. They test both approaches on reduced instances from an established benchmark set and compare them directly to classical solvers. The central finding is that these quantum methods match classical solution quality on smaller problems while incurring longer runtimes and losing feasibility once instance size grows. A reader should care because GTSP captures real sequencing tasks with discrete choices, so any method that works at small scale points to where quantum hardware might first become useful if the scaling bottlenecks can be removed.

Core claim

A novel QUBO formulation for GTSP preserves feasible solutions for quantum annealing, and a constrained QAOA variant with XY mixer preserves stepwise Hamming weight in the circuit model while full constraints are enforced only in post-processing. On GTSPLIB instances after node-reduction preprocessing, both quantum solvers deliver competitive solution quality against classical methods on smaller graphs, yet they exhibit higher runtimes and a sharp drop in feasibility and scalability as instance size increases.

What carries the argument

The QUBO formulation for GTSP together with the XY-mixer QAOA variant that maintains Hamming weight while delegating full constraint checking to post-processing.

If this is right

Quantum annealing can already serve as a viable alternative for small clustered routing problems on current hardware.
The XY-mixer QAOA pipeline can be executed on NISQ devices once instances are reduced to hardware size limits.
Sampling rates and runtime overheads remain the dominant practical failure modes that must be addressed before larger use.
Node reduction creates smaller test instances whose solutions still reflect the structure of the original GTSP problem.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If hardware sampling improves, the same formulation could handle larger variant-selection tasks in logistics without classical post-processing.
The observed feasibility collapse suggests that embedding full GTSP constraints directly into the quantum Hamiltonian would be a high-value next step.
The same QUBO and mixer construction may transfer to other routing problems that combine selection and ordering decisions.

Load-bearing premise

The node-reduction preprocessing and post-processing steps for feasibility produce enough valid solutions on real hardware to make the quantum approaches practically useful.

What would settle it

A run on a GTSP instance with more clusters than the tested set in which the quantum pipeline returns zero valid tours within the allotted shots while a classical solver finds an optimal tour in seconds.

Figures

Figures reproduced from arXiv: 2604.25531 by Claudia Linnhoff-Popien, Jonas Stein, Maximilian Zorn, Melinda Braun, Michael Ertl, Sara Juarez Oropeza, Tommy Kiss.

**Figure 1.** Figure 1: Example illustrating the application of the NN2C extended prepro view at source ↗

**Figure 2.** Figure 2: Distribution of solution quality achieved by Q-GTSP on the Subsample view at source ↗

**Figure 3.** Figure 3: Distribution of solution quality achieved by Q-GTSP on the Subsample view at source ↗

**Figure 4.** Figure 4: Distribution of solution quality achieved by C-QAOA on the Subsam view at source ↗

**Figure 5.** Figure 5: Distribution of solution quality achieved by C-QAOA on the Subsam view at source ↗

**Figure 3.** Figure 3: For example, 91% of the solutions sampled for view at source ↗

**Figure 7.** Figure 7: Solution quality of the best shot measured in approximation ratio at 1500 shots. view at source ↗

**Figure 8.** Figure 8: Distribution of solution quality achieved by C-QAOA on the view at source ↗

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives concrete GTSP QUBO and XY-mixer QAOA formulations plus GTSPLIB baselines, but post-processing carries most of the feasibility load.

read the letter

The paper introduces a GTSP-specific QUBO aimed at preserving feasible samples for annealing and pairs it with an XY-mixer QAOA that keeps Hamming weight in the circuit while deferring full cluster and sequencing constraints to post-processing. It also applies node-reduction preprocessing to create smaller instances that fit current hardware and runs both approaches on GTSPLIB data against classical solvers. That combination is the actual new piece: a documented attempt to adapt these quantum tools to the clustered routing setting rather than generic TSP. The evaluation is straightforward about the outcome—competitive quality on the smallest graphs, then clear drops in feasibility and speed as size increases—which is useful to see spelled out with public instances. The work is honest about runtime and sampling limitations. The main limitation is that full GTSP feasibility is enforced only after the quantum step. When the abstract notes sharp feasibility degradation, it becomes unclear how much of the reported solution quality comes from the quantum optimizer versus the classical repair that follows. The node-reduction step adds another layer: it may change cluster structure and optimal costs enough that results on the reduced instances do not directly speak to the original problem. These points are not fatal, but they mean the competitiveness claim on small graphs rests on a hybrid pipeline rather than the quantum component alone. Readers working on quantum methods for routing or variant-selection problems will find the formulations and the explicit failure modes worth looking at. The paper is coherent on its own terms and uses external benchmarks, so it deserves a serious referee who can press on the post-processing analysis and the preprocessing effects.

Referee Report

3 major / 1 minor

Summary. The manuscript introduces a QUBO formulation for the Generalized Traveling Salesman Problem (GTSP) tailored to quantum annealing and an XY-mixer QAOA variant for gate-based devices. Full GTSP feasibility (cluster visitation and sequencing) is enforced only in post-processing after the quantum step, which preserves only Hamming-weight constraints in-circuit. A node-reduction preprocessing step is applied to GTSPLIB instances to produce smaller, NISQ-compatible problems. The central claim is that these quantum approaches yield competitive solution quality versus classical state-of-the-art solvers on small reduced graphs, while exhibiting higher runtimes and sharp degradation in feasibility and scalability as instance size increases.

Significance. If the quantitative claims hold after addressing the post-processing and preprocessing concerns, the work supplies useful empirical baselines for quantum combinatorial optimization on clustered routing problems. It explicitly identifies practical NISQ bottlenecks (sampling rates, runtime, feasibility) and demonstrates a hardware-executable pipeline, which is valuable for guiding future algorithm and hardware development in this domain.

major comments (3)

[Abstract and Evaluation] The competitiveness claim (abstract and evaluation) rests on solution quality after classical post-processing. The manuscript must report the raw fraction of valid GTSP-feasible samples produced by the quantum optimizer (before any repair) across instance sizes; without this metric it is impossible to determine whether observed quality derives from the quantum optimization step or from the classical repair heuristics.
[Preprocessing and Instance Construction] The node-reduction preprocessing (described in the methods) constructs NISQ-friendly subsets by reducing nodes per cluster. The paper should quantify the distortion this introduces to cluster structure, optimal tour costs, and feasibility relative to the original GTSPLIB instances, and state whether results on the reduced instances can be extrapolated to full-scale GTSP scalability.
[Abstract and Results] The abstract states that comparisons were performed and competitiveness holds on small graphs with degradation on larger ones, yet provides no instance sizes, optimality gaps, feasibility rates, runtimes, or error bars. The evaluation section must include these quantitative data (e.g., tables or figures with specific numbers) to substantiate the central claim.

minor comments (1)

[Methods] Notation for the QUBO penalties and the XY-mixer Hamiltonian should be cross-referenced explicitly between the formulation section and the QAOA circuit description to improve readability.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for their constructive and detailed comments on our manuscript. We address each major comment point by point below, agreeing where revisions are warranted to improve clarity and rigor. We have prepared revisions to the manuscript accordingly.

read point-by-point responses

Referee: The competitiveness claim (abstract and evaluation) rests on solution quality after classical post-processing. The manuscript must report the raw fraction of valid GTSP-feasible samples produced by the quantum optimizer (before any repair) across instance sizes; without this metric it is impossible to determine whether observed quality derives from the quantum optimization step or from the classical repair heuristics.

Authors: We agree that the raw fraction of valid GTSP-feasible samples before post-processing is an important metric for isolating the quantum optimizer's contribution. In the revised manuscript, we will add a dedicated subsection and table reporting these raw feasibility rates (pre- and post-processing) for each instance size and quantum solver variant. This will enable direct assessment of whether solution quality stems primarily from the quantum step or the classical repair. revision: yes
Referee: The node-reduction preprocessing (described in the methods) constructs NISQ-friendly subsets by reducing nodes per cluster. The paper should quantify the distortion this introduces to cluster structure, optimal tour costs, and feasibility relative to the original GTSPLIB instances, and state whether results on the reduced instances can be extrapolated to full-scale GTSP scalability.

Authors: We acknowledge the value of quantifying preprocessing effects. We will expand the methods section with metrics on distortion, including average reduction in nodes per cluster, relative changes in optimal tour costs (for instances with known optima), and impacts on feasibility. We will also add an explicit statement that results on reduced instances are intended as NISQ-scale demonstrations and cannot be directly extrapolated to full-scale GTSP due to the introduced simplifications in cluster structure. revision: yes
Referee: The abstract states that comparisons were performed and competitiveness holds on small graphs with degradation on larger ones, yet provides no instance sizes, optimality gaps, feasibility rates, runtimes, or error bars. The evaluation section must include these quantitative data (e.g., tables or figures with specific numbers) to substantiate the central claim.

Authors: We agree that greater specificity is needed. We will revise the abstract to include concrete details such as the range of reduced instance sizes tested, representative optimality gaps, feasibility rates, and runtime comparisons. The evaluation section will be updated with tables and figures containing specific numerical values, including error bars where applicable, to fully substantiate the claims of competitiveness on small graphs and degradation on larger ones. revision: yes

Circularity Check

0 steps flagged

No circularity: empirical evaluation on external benchmarks

full rationale

The paper proposes a QUBO formulation and XY-mixer QAOA variant for GTSP, explicitly notes that full feasibility is handled in post-processing, and evaluates solution quality and feasibility on GTSPLIB instances against independent classical solvers. No derivation step, equation, or claim reduces to its own inputs by construction, self-citation, or renaming; all performance statements are grounded in direct comparison to external data and solvers. This is the standard non-circular case.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review provides no explicit free parameters, axioms, or invented entities; the QUBO formulation likely contains penalty coefficients whose values are not stated here.

pith-pipeline@v0.9.0 · 5536 in / 1233 out tokens · 56638 ms · 2026-05-07T16:45:31.660810+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

35 extracted references · 4 canonical work pages · 1 internal anchor

[1]

Pop, Ovidiu Cosma, Cosmin Sabo, and Corina Pop Sitar

Petric ˘a C. Pop, Ovidiu Cosma, Cosmin Sabo, and Corina Pop Sitar. A comprehensive survey on the generalized traveling salesman problem. European Journal of Operational Research, 314(3):819–835, 2024

2024
[2]

Some applications of the generalized travelling salesman problem

Gilbert Laporte, Ardavan Asef-Vaziri, and Chelliah Sriskandarajah. Some applications of the generalized travelling salesman problem. Journal of the Operational Research Society, 47(12):1461–1467, 1996

1996
[3]

A transformation technique for the clustered generalized traveling salesman problem with applications to logistics.European Journal of Operational Research, 285(2):444–457, 2020

Pouya Baniasadi, Mehdi Foumani, Kate Smith-Miles, and Vladimir Ejov. A transformation technique for the clustered generalized traveling salesman problem with applications to logistics.European Journal of Operational Research, 285(2):444–457, 2020

2020
[4]

Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem.European Journal of Operational Research, 219(2):234–251, 2012

Daniel Karapetyan and Gregory Gutin. Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem.European Journal of Operational Research, 219(2):234–251, 2012

2012
[5]

Robotsp - a fast solution to the robotic task sequencing problem, 2017

Francisco Su ´arez-Ruiz, Teguh Santoso Lembono, and Quang-Cuong Pham. Robotsp - a fast solution to the robotic task sequencing problem, 2017

2017
[6]

Gatsbi: An online gtsp-based algorithm for targeted surface bridge inspection

Harnaik Dhami, Kevin Yu, Troi Williams, Vineeth Vajipey, and Pratap Tokekar. Gatsbi: An online gtsp-based algorithm for targeted surface bridge inspection. In2023 International Conference on Unmanned Aircraft Systems (ICUAS), page 1199–1206. IEEE, June 2023

2023
[7]

Nielsen and Isaac L

Michael A. Nielsen and Isaac L. Chuang.Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010

2010
[8]

Challenges and opportunities in quantum optimization.Nature Reviews Physics, 6(12):718–735, 2024

Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas B ¨artschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel J Egger, Bruce G Elmegreen, et al. Challenges and opportunities in quantum optimization.Nature Reviews Physics, 6(12):718–735, 2024

2024
[9]

Algorithmic qubo formulations for k-sat and hamiltonian cycles

Jonas N ¨ußlein, Thomas Gabor, Claudia Linnhoff-Popien, and Sebastian Feld. Algorithmic qubo formulations for k-sat and hamiltonian cycles. InProceedings of the genetic and evolutionary computation conference companion, pages 2240–2246, 2022

2022
[10]

Mapping a logical representation of tsp to quantum annealing.Quantum Information Processing, 20(12), 2021

Carla Silva, Ana Aguiar, Priscila Lima, and In ˆes Dutra. Mapping a logical representation of tsp to quantum annealing.Quantum Information Processing, 20(12), 2021

2021
[11]

Solving the traveling salesperson problem with quantum approximate optimization algorithms.Preprint, 2024

Siddarth Chander, Naren Sathishkumar, Affan Hussain, and Kostas Blekos. Solving the traveling salesperson problem with quantum approximate optimization algorithms.Preprint, 2024

2024
[12]

Solving the traveling salesman problem via different quantum computing architectures.arXiv preprint arXiv:2502.17725, 2025

Venkat Padmasola, Zhaotong Li, Rupak Chatterjee, and Wesley Dyk. Solving the traveling salesman problem via different quantum computing architectures.arXiv preprint arXiv:2502.17725, 2025

work page arXiv 2025
[13]

A tutorial on formulating and using qubo models, 2019

Fred Glover, Gary Kochenberger, and Yu Du. A tutorial on formulating and using qubo models, 2019

2019
[14]

Ising formulations of many np problems.Frontiers in Physics, 2, 2014

Andrew Lucas. Ising formulations of many np problems.Frontiers in Physics, 2, 2014

2014
[15]

Beweis des Adiabatensatzes.Zeitschrift f ¨ur Phys., 51(3):165–180, 1928

M Born and V Fock. Beweis des Adiabatensatzes.Zeitschrift f ¨ur Phys., 51(3):165–180, 1928

1928
[16]

A Quantum Approximate Optimization Algorithm

Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm.arXiv preprint arXiv:1411.4028, 2014

work page internal anchor Pith review arXiv 2014
[17]

Farhi, J

Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Quantum computation by adiabatic evolution.arXiv preprint quant- ph/0001106, 2000

work page arXiv 2000
[18]

Quantum annealing initialization of the quantum approximate optimization algorithm.quantum, 5:491, 2021

Stefan H Sack and Maksym Serbyn. Quantum annealing initialization of the quantum approximate optimization algorithm.quantum, 5:491, 2021

2021
[19]

Compressed space quantum approximate optimization algorithm for constrained combinatorial op- timization.IEEE Transactions on Quantum Engineering, 2025

Tatsuhiko Shirai and Nozomu Togawa. Compressed space quantum approximate optimization algorithm for constrained combinatorial op- timization.IEEE Transactions on Quantum Engineering, 2025

2025
[20]

Penalty-free approach to accelerating constrained quantum optimization

David Bucher, Jonas Stein, Sebastian Feld, and Claudia Linnhoff-Popien. Penalty-free approach to accelerating constrained quantum optimization. Physical Review A, 112(6):062605, 2025

2025
[21]

From the quantum approximate optimization algorithm to a quantum alternating operator ansatz.Algo- rithms, 12(2):34, 2019

Stuart Hadfield, Zhihui Wang, Bryan O’gorman, Eleanor G Rieffel, Davide Venturelli, and Rupak Biswas. From the quantum approximate optimization algorithm to a quantum alternating operator ansatz.Algo- rithms, 12(2):34, 2019

2019
[22]

Comparative study of variations in quantum approximate optimization algorithms for the traveling salesman problem.Entropy, 25(8):1238, 2023

Wenyang Qian, Robert AM Basili, Mary Mehrnoosh Eshaghian-Wilner, Ashfaq Khokhar, Glenn Luecke, and James P Vary. Comparative study of variations in quantum approximate optimization algorithms for the traveling salesman problem.Entropy, 25(8):1238, 2023

2023
[23]

An edge-based and subspace reduction encoding scheme to solve the traveling salesman problem in quantum computers

Anandu Kalleri Madhu, Chi-Kwong Li, Jami R ¨onkk¨o, Mikio Nakahara, and Ray-Kuang Lee. An edge-based and subspace reduction encoding scheme to solve the traveling salesman problem in quantum computers. arXiv e-prints, pages arXiv–2512, 2025

2025
[24]

Space-efficient binary optimization for variational quantum computing.npj Quantum Information, 8(1):39, 2022

Adam Glos, Aleksandra Krawiec, and Zolt ´an Zimbor ´as. Space-efficient binary optimization for variational quantum computing.npj Quantum Information, 8(1):39, 2022

2022
[25]

Prog- qaoa: Framework for resource-efficient quantum optimization through classical programs.Quantum, 9:1663, 2025

Bence Bak ´o, Adam Glos, ¨Ozlem Salehi, and Zolt ´an Zimbor ´as. Prog- qaoa: Framework for resource-efficient quantum optimization through classical programs.Quantum, 9:1663, 2025

2025
[26]

A pre-processing reduction method for the generalized travelling salesman problem.Operational Research, 21(4):2543–2591, 2021

Mehdi El Krari, Bela ¨ıd Ahiod, and Youssef Bouazza El Benani. A pre-processing reduction method for the generalized travelling salesman problem.Operational Research, 21(4):2543–2591, 2021

2021
[27]

Quantum annealing and gnn for solving tsp with qubo

Haoqi He. Quantum annealing and gnn for solving tsp with qubo. In Smita Ghosh and Zhao Zhang, editors,Algorithmic Aspects in Informa- tion and Management, Singapore, 2024. Springer Nature Singapore

2024
[28]

GTSPLIB – gtsp instances library

Alexei Zverovich. GTSPLIB – gtsp instances library. https://www.cs. rhul.ac.uk/home/zvero/GTSPLIB/, 2002. Accessed: 2026-01-26

2002
[29]

What is quantum annealing?, 2026

D-Wave Quantum. What is quantum annealing?, 2026. Accessed: 2026- 01-27

2026
[30]

The advantage™ quantum computer

D-Wave Quantum Inc. The advantage™ quantum computer. https: //www.dwavequantum.com/solutions-and-products/systems/, 2026. Ac- cessed: 2026-01-30

2026
[31]

Processor types

IBM Quantum Documentation. Processor types. https://quantum.cloud. ibm.com/docs/en/guides/processor-types, 2026. Accessed: 2026-01-30

2026
[32]

Controlling privacy loss in sampling schemes: An analysis of stratified and cluster sampling.arXiv preprint arXiv:2007.12674, 2020

Mark Bun, J ¨org Drechsler, Marco Gaboardi, Audra McMillan, and Jayshree Sarathy. Controlling privacy loss in sampling schemes: An analysis of stratified and cluster sampling.arXiv preprint arXiv:2007.12674, 2020

work page arXiv 2007
[33]

Smith and Frank Imeson

Stephen L. Smith and Frank Imeson. Glns: An effective large neighbor- hood search heuristic for the generalized traveling salesman problem. Computers & Operations Research, 87:1–19, 2017

2017
[34]

Gurobi Optimizer Reference Manual, 2026

Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2026

2026
[35]

Grover mixers for qaoa: Shifting complexity from mixer design to state preparation

Andreas B ¨artschi and Stephan Eidenbenz. Grover mixers for qaoa: Shifting complexity from mixer design to state preparation. In2020 IEEE International Conference on Quantum Computing and Engineer- ing (QCE), pages 72–82, 2020

2020