arxiv: 2605.00739 · v1 · submitted 2026-05-01 · 🪐 quant-ph

Recognition: unknown

A Resource-Efficient Variational Quantum Framework for the Traveling Salesman Problem

Yuefeng Lin , Chao Zheng , Cong Guo

Authors on Pith no claims yet

Pith reviewed 2026-05-09 19:44 UTC · model grok-4.3

classification 🪐 quant-ph

keywords traveling salesman problemvariational quantum algorithmsquantum combinatorial optimizationdivide-and-conquercompact encodingpermutation-preserving ansatzresource-efficient quantum computingNMR quantum computers

0 comments

The pith

A variational quantum framework solves small TSP instances using O(n log n) qubits and divide-and-conquer with up to 100% success rates.

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

This paper presents a new way to run the traveling salesman problem on quantum computers that uses much less hardware resources than previous approaches. Instead of encoding cities with many qubits per city, it uses a compact binary encoding that needs only O(n log n) qubits total. It also splits the problem into smaller parts with a divide-and-conquer method so that each piece fits on today's small quantum devices. Simulations show it finds the best tour almost every time for 4, 5, and 6 city cases, and a real experiment on NMR quantum computers succeeded for 5 cities using only two qubits at a time. Readers should care because this could let us test quantum optimization on problems that are currently too big for the hardware we have.

Core claim

The framework combines compact binary-register encoding to represent permutations efficiently, a permutation-preserving ansatz tailored to the problem, and a divide-and-conquer strategy that decomposes the TSP into local subproblems solved variationally with classical post-processing to assemble the full solution. This setup achieves best average success rates of 100% on 4-city and 5-city TSP instances and 95.5% on 6-city instances in numerical simulations. The divide-and-conquer approximation was implemented locally with two qubits and tested on SpinQ NMR quantum computers for a 5-city instance.

What carries the argument

Compact binary-register encoding of city permutations paired with a permutation-preserving variational ansatz and divide-and-conquer execution that reduces per-run qubit demand to subsystem size.

Load-bearing premise

The permutation-preserving ansatz and divide-and-conquer strategy together preserve enough solution quality that the variational optimizer finds good or optimal tours without major loss from the full-problem encoding.

What would settle it

Executing the method on a 7-city TSP instance and finding that the best average success rate falls below 80% despite extensive optimization would indicate the approach does not maintain high quality as problem size increases.

Figures

Figures reproduced from arXiv: 2605.00739 by Chao Zheng, Cong Guo, Yuefeng Lin.

**Figure 1.** Figure 1: Two-qubit variational circuit used in the hardware experiments. 3.2 Simulation performance of the problem-inspired ansatz We assessed the dependence of the proposed problem-inspired ansatz on circuit depth for TSP instances with n = 4,5,6 cities view at source ↗

**Figure 2.** Figure 2: Success rate as a function of circuit depth for the proposed problem-inspired ansatz. Results are shown for TSP instances with n = 4,5,6 cities. Solid curves denote the average success rate over 10 randomly generated graph instances. Shaded regions indicate the absolute performance range across the 10 instances, bounded by the minimum and maximum success rates. 3.3 Comparison with a prior feasible-subspace… view at source ↗

**Figure 3.** Figure 3: Performance comparison between the proposed problem-inspired ansatz and the prior one-hot feasible-subspace ansatz reported in Ref.19. Bars denote the average success rate over 10 randomly generated TSP instances for each problem size. Error bars indicate the absolute performance range across instances, bounded by the minimum and maximum success rates view at source ↗

**Figure 4.** Figure 4: Optimization trajectories on SpinQ Gemini Pro for the 5-city TSP instance. Panel (a) shows the loss values obtained from raw noisy measurements, iterative Bayesian unfolding (IBU), matrix-inversion-based mitigation, and the noise-free simulator. Panel (b) shows the corresponding target-state probabilities during optimization. 0 20 40 60 80 100 120 Iteration 100 105 110 115 120 Loss SpinQ_Triangulum (Noise)… view at source ↗

**Figure 5.** Figure 5: Optimization trajectories on Triangulum II for the 5-city TSP instance. Panel (a) shows the loss values obtained from raw noisy measurements, iterative Bayesian unfolding (IBU), matrix-inversion-based mitigation, and the noise-free simulator. Panel (b) shows the corresponding target-state probabilities during optimization. The hardware trajectories are broadly consistent with the noise-free reference, whil… view at source ↗

read the original abstract

The Traveling Salesman Problem (TSP) is a prototypical combinatorial optimization problem, but its quantum implementation is limited by the O(n^2)-qubit overhead of standard one-hot encodings. Here, we propose a resource-efficient variational quantum framework based on compact binary-register encoding, a permutation-preserving problem-inspired ansatz, and a complementary divide-and-conquer execution strategy. The compact encoding reduces the data-qubit requirement to O(n log n), while the divide-and-conquer formulation lowers the number of qubits required in each local hardware execution to the size of the largest subsystem. Numerical simulations on TSP instances with 4, 5, and 6 cities achieve best average success rates of 100%, 100%, and 95.5%, respectively. A local two-qubit implementation of the divide-and-conquer approximation is further evaluated for a 5-city TSP instance on SpinQ Gemini Pro and SpinQ Triangulum II NMR quantum computers. Taken together, the results indicate how compact encoding and divide-and-conquer execution with classical post-processing can be used to study small combinatorial optimization instances on resource-constrained quantum hardware.

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 a practical qubit cut for tiny TSP cases via binary encoding and divide-and-conquer, with strong small-scale simulation and NMR hardware results, but stays within easy regimes.

read the letter

The core advance here is swapping the usual one-hot encoding for a compact binary one that drops qubit needs to O(n log n) for TSP, then layering a permutation-preserving ansatz and a divide-and-conquer split so each quantum execution stays small. Simulations hit 100% average success on 4- and 5-city instances and 95.5% on 6 cities, and they ran the local two-qubit piece of the 5-city case on actual SpinQ NMR hardware. That combination is new as a package even if pieces have been tried before, and it directly tackles the resource wall that keeps variational TSP off NISQ devices today. The ansatz construction is clean because it never samples invalid tours, and the post-processing step to glue subsystems together is a straightforward engineering choice that keeps everything runnable on limited hardware. The hardware demo, limited as it is, shows they are not just simulating. The main limitation is scale. These are toy instances where the reduced search space is small enough that a variational optimizer can exhaust or nearly exhaust it, and the 95.5% figure for n=6 already shows some drop-off. No baselines against classical solvers or other quantum encodings appear in the reported results, and the abstract gives no error bars or noise-model details beyond the demo. For readers focused on near-term combinatorial optimization, this is worth trying on their own small problems because the recipe is explicit and the qubit savings are real. It deserves peer review because the evidence is positive and the method is concrete, even if larger instances and fuller comparisons will be needed to judge broader impact.

Referee Report

2 major / 1 minor

Summary. The paper proposes a variational quantum framework for the Traveling Salesman Problem that employs compact binary-register encoding (reducing qubits to O(n log n)), a permutation-preserving problem-inspired ansatz, and a divide-and-conquer execution strategy with classical post-processing. Numerical simulations report best average success rates of 100%, 100%, and 95.5% for TSP instances with 4, 5, and 6 cities, respectively, while a local two-qubit implementation of the divide-and-conquer step is demonstrated on SpinQ Gemini Pro and Triangulum II NMR quantum computers for a 5-city instance.

Significance. If the reported success rates and hardware results hold under detailed scrutiny, the work illustrates a practical route to studying small combinatorial optimization problems on severely resource-constrained near-term hardware by combining compact encoding with subsystem decomposition. The permutation-preserving ansatz and divide-and-conquer approach are strengths that could generalize to other permutation-based problems.

major comments (2)

[Abstract] Abstract and results section: the reported best average success rates (100%, 100%, 95.5%) lack accompanying details on the number of distinct TSP instances tested per city count, the specific variational optimizer and its hyperparameters, number of optimization runs, convergence criteria, or any statistical measures such as standard deviations or error bars. Without these, it is impossible to determine whether the high rates reflect robust performance or favorable instance selection and exhaustive search in the reduced space.
[Hardware demonstration] Hardware demonstration section: the two-qubit local implementation on the SpinQ NMR devices for the 5-city divide-and-conquer step provides no information on circuit depth, gate fidelities, noise characterization, or how the classical post-processing reconstructs the global tour from subsystem results. This omission prevents assessment of whether the hardware run meaningfully validates the approximation beyond classical simulation.

minor comments (1)

[Abstract] The abstract states 'best average success rates' without defining the averaging procedure or the baseline against which 'best' is measured; a brief clarification would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive major comments. We agree that additional experimental details are required for reproducibility and assessment of robustness. We will revise the manuscript to incorporate the requested information in both the abstract/results and hardware sections. Point-by-point responses follow.

read point-by-point responses

Referee: [Abstract] Abstract and results section: the reported best average success rates (100%, 100%, 95.5%) lack accompanying details on the number of distinct TSP instances tested per city count, the specific variational optimizer and its hyperparameters, number of optimization runs, convergence criteria, or any statistical measures such as standard deviations or error bars. Without these, it is impossible to determine whether the high rates reflect robust performance or favorable instance selection and exhaustive search in the reduced space.

Authors: We agree that the current presentation lacks sufficient detail for independent evaluation. In the revised manuscript we will expand the numerical results section (and update the abstract accordingly) to report: the number of distinct random TSP instances evaluated for each city count, the specific classical optimizer and its hyperparameters, the number of independent optimization runs per instance, the convergence tolerance employed, and statistical measures including standard deviations and error bars on the success rates. These additions will demonstrate that the quoted best-average figures are obtained from multiple instances and runs rather than exhaustive enumeration or cherry-picked cases. The variational nature of the approach (as opposed to exhaustive search) will also be emphasized. revision: yes
Referee: [Hardware demonstration] Hardware demonstration section: the two-qubit local implementation on the SpinQ NMR devices for the 5-city divide-and-conquer step provides no information on circuit depth, gate fidelities, noise characterization, or how the classical post-processing reconstructs the global tour from subsystem results. This omission prevents assessment of whether the hardware run meaningfully validates the approximation beyond classical simulation.

Authors: We acknowledge that the hardware section is currently too terse. In the revised manuscript we will augment this section with: the explicit circuit depth of the two-qubit divide-and-conquer circuit, the gate fidelities and coherence times reported by the SpinQ devices, a brief noise characterization, and a step-by-step description of the classical post-processing routine that merges the local subsystem solutions into a global tour. These additions will allow readers to judge the extent to which the hardware execution validates the divide-and-conquer approximation beyond pure simulation. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper proposes a compact binary encoding, permutation-preserving ansatz, and divide-and-conquer strategy for variational quantum TSP solving. All performance claims rest on explicit numerical simulations for n=4-6 instances and a 2-qubit hardware run, with success rates reported as direct empirical outcomes rather than derived predictions. No equations reduce by construction to fitted parameters renamed as forecasts, no ansatz is defined circularly in terms of the target solution, and no load-bearing uniqueness theorem or result is imported solely via self-citation. The framework is self-contained against external benchmarks (simulation and hardware data), satisfying the criteria for an honest non-finding of circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available, preventing identification of specific free parameters or ad-hoc elements; the work relies on standard variational quantum algorithm assumptions such as the ability to variationally minimize a cost function encoding the TSP objective.

pith-pipeline@v0.9.0 · 5495 in / 1186 out tokens · 43691 ms · 2026-05-09T19:44:18.793952+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

20 extracted references · 12 canonical work pages · 1 internal anchor

[1]

Papadimitriou, C. H. & Steiglitz, K.Combinatorial optimization: algorithms and complexity(Courier Corporation, 1998)

1998
[2]

& Karp, R

Held, M. & Karp, R. M. A dynamic programming approach to sequencing problems.J. Soc. for Ind. Appl. mathematics10, 196–210 (1962)

1962
[3]

L., Bixby, R

Applegate, D. L., Bixby, R. E., Chvátal, V . & Cook, W. J. The traveling salesman problem: a computational study. InThe traveling salesman problem(Princeton university press, 2011). 4.Preskill, J. Quantum computing in the nisq era and beyond.Quantum2, 79 (2018)

2011
[4]

Cerezo, M.et al.Variational quantum algorithms.Nat. Rev. Phys.3, 625–644, DOI: 10.1038/s42254-021-00348-9 (2021)

work page doi:10.1038/s42254-021-00348-9 2021
[5]

Bharti, K.et al.Noisy intermediate-scale quantum algorithms.Rev. Mod. Phys.94, 015004, DOI: 10.1103/RevModPhys. 94.015004 (2022)

work page doi:10.1103/revmodphys 2022
[6]

communications5, 4213 (2014)

Peruzzo, A.et al.A variational eigenvalue solver on a photonic quantum processor.Nat. communications5, 4213 (2014)

2014
[7]

A Quantum Approximate Optimization Algorithm

Farhi, E., Goldstone, J. & Gutmann, S. A quantum approximate optimization algorithm.arXiv preprint arXiv:1411.4028 (2014)

work page internal anchor Pith review Pith/arXiv arXiv 2014
[8]

& Lacomme, P

Bourreau, E., Fleury, G. & Lacomme, P. Indirect quantum approximate optimization algorithms: application to the tsp. arXiv preprint arXiv:2311.03294(2023)

work page arXiv 2023
[9]

Palackal, L.et al.Quantum-assisted solution paths for the capacitated vehicle routing problem.arXiv preprint arXiv:2304.09629(2023)

work page arXiv 2023
[10]

& Bertels, K

Sarkar, A., Al-Ars, Z. & Bertels, K. Quaser: Quantum accelerated de novo dna sequence reconstruction.Plos one16, e0249850 (2021)

2021
[11]

PRX Life2, 023006, DOI: 10.1103/PRXLife.2.023006 (2024)

Fang, J.-K.et al.Divide-and-conquer quantum algorithm for hybrid denovo genome assembly of short and long reads. PRX Life2, 023006, DOI: 10.1103/PRXLife.2.023006 (2024). 13.Lucas, A. Ising formulations of many np problems.Front. Phys.2, 5, DOI: 10.3389/fphy.2014.00005 (2014). 11/12

work page doi:10.1103/prxlife.2.023006 2024
[12]

& Bahrampour, A

Ramezani, M., Salami, S., Shokhmkar, M., Moradi, M. & Bahrampour, A. Reducing the number of qubits from n2 to nlog 2 n to solve the traveling salesman problem with quantum computers: A proposal for demonstrating quantum supremacy in the nisq era.arXiv preprint arXiv:2402.18530(2024)

work page arXiv 2024
[13]

& Brodutch, A

Khait, I., Tham, E., Segal, D. & Brodutch, A. Variational quantum eigensolvers in the era of distributed quantum computers. Phys. Rev. A108, L050401, DOI: 10.1103/PhysRevA.108.L050401 (2023). 16.https://github.com/spinqtech/spinqit

work page doi:10.1103/physreva.108.l050401 2023
[14]

8, 1–23 (2021)

Hou, S.-Y .et al.Spinq gemini: a desktop quantum computing platform for education and research.EPJ Quantum Technol. 8, 1–23 (2021)

2021
[15]

Mag.16, 20–29 (2022)

Feng, G.et al.Spinq triangulum: A commercial three-qubit desktop quantum computer.IEEE Nanotechnol. Mag.16, 20–29 (2022)

2022
[16]

& Yamashita, S

Matsuo, A., Suzuki, Y ., Hamamura, I. & Yamashita, S. Enhancing vqe convergence for optimization problems with problem-specific parameterized quantum circuits.IEICE TRANSACTIONS on Inf. Syst.106, 1772–1782 (2023)

2023
[17]

Bauer, W.et al.Scalable measurement error mitigation via iterative bayesian unfolding.Phys. Rev. Res.6, 013187, DOI: 10.1103/PhysRevResearch.6.013187 (2024)

work page doi:10.1103/physrevresearch.6.013187 2024
[18]

Bravyi, S., Sheldon, S., Kandala, A., Mckay, D. C. & Gambetta, J. M. Mitigating measurement errors in multiqubit experiments.Phys. Rev. A103, 042605, DOI: 10.1103/PhysRevA.103.042605 (2021)

work page doi:10.1103/physreva.103.042605 2021
[19]

Nature Communications9(1) (2018) https:// doi.org/10.1038/s41467-018-07090-4

McClean, J. R., Boixo, S., Smelyanskiy, V . N., Babbush, R. & Neven, H. Barren plateaus in quantum neural network training landscapes.Nat. Commun.9, 4812, DOI: 10.1038/s41467-018-07090-4 (2018)

work page doi:10.1038/s41467-018-07090-4 2018
[20]

& Hou, S.-Y

Chen, R., Zhou, G., Guo, C., Feng, G. & Hou, S.-Y . Pure quantum gradient descent algorithm and full quantum variational eigensolver.Front. Phys.19, 21202, DOI: 10.1007/s11467-023-1346-7 (2024). 12/12

work page doi:10.1007/s11467-023-1346-7 2024