Tensor-Network Formulation of the Traveling Salesman Problem and Variants

Aitor Moreno Fdez. de Leceta; Alejandro Mata Ali; I\~nigo Perez Delgado

REVIEW 1 major objections 1 minor 3 cited by

Tensor-Network Formulation of the Traveling Salesman Problem and Variants

T0 review · 1 major / 1 minor · reviewed 2026-05-24 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Tensor networks represent traveling salesman tours so their zero-temperature marginals select an optimal feasible path via sequential rules.

desk verdict The paper's new piece is an explicit tensor-network marginal formula for TSP whose zero-temperature limit recovers optimal tours via sequential marginals, using standard layers plus counting filters. read the letter →

arxiv 2311.14344 v3 pith:TKW6EDSS submitted 2023-11-24 quant-ph cs.ET

Alejandro Mata Ali , Iñigo Perez Delgado , Aitor Moreno Fdez. de Leceta This is my paper · ORCID

classification quant-phcs.ET

keywords tensornetworkstravelingsalesmanproblemcombinatorialoptimizationmarginalformulaBoltzmannweightingcountingfiltersjobreassignmentzero-temperaturelimit

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper constructs a tensor-network representation of candidate tours for the traveling salesman problem and its variants. Tours are encoded in network layers, weighted by Boltzmann factors according to their costs, and constrained by explicit counting filters that enforce validity. This setup produces an explicit marginal formula whose zero-temperature, exact-arithmetic limit extracts an optimal tour by sequential application of the marginal rule. The same construction adapts directly to generalizations such as the job reassignment problem. At finite temperature or finite precision the extraction functions as a heuristic whose outcome depends on numerical contrast and near-degeneracies.

What carries the argument

The tensor-network marginal formula obtained from layers weighted by Boltzmann factors and constrained by counting filters; it supplies the sequential marginal rule that recovers the optimum in the zero-temperature exact limit.

What would settle it

For any small TSP instance whose optimum is known by exhaustive enumeration, the sequential marginal rule applied to the exact-arithmetic tensor-network marginals fails to recover that optimum.

Watch

Extended reading notes

Core claim

Candidate tours are represented with tensor-network layers, weighted by Boltzmann factors, and constrained through explicit counting filters. The construction yields an explicit tensor-network marginal formula whose zero-temperature, exact-arithmetic limit identifies an optimal feasible tour through a sequential marginal rule.

Load-bearing premise

The counting filters and Boltzmann weighting together produce a tensor network whose marginals remain numerically stable and contractible enough to extract the optimum without the extraction rule itself becoming equivalent to exhaustive search.

Editorial extensions

If this is right

The same tensor-network layers and filters extend without change to several standard generalizations of the TSP.
The construction supplies a concrete tensor-network implementation for the job reassignment problem.
At any finite temperature the extraction procedure becomes a heuristic whose success depends on numerical contrast, calibration, and near-degeneracies.
The experiments remain deliberately small and serve only to illustrate the method against exact and heuristic references.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If tensor-network contraction routines can be applied at scale, the same marginal formula might serve as a contraction-based solver for other routing or assignment problems.
The sequential marginal rule could be compared directly with belief-propagation or message-passing heuristics on the same constraint graphs.
Near-degeneracies that appear at finite temperature might be used to generate diverse near-optimal tours without additional sampling steps.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

read the letter

The main thing to know is that this work encodes TSP tours as tensor-network layers, applies Boltzmann weights for the costs, and uses counting-filter tensors to enforce the visit-once and degree constraints. From that network it derives a marginal formula whose exact zero-temperature limit, in exact arithmetic, identifies a feasible optimum through a sequential rule. The authors flag that finite-temperature, finite-precision extraction is only a heuristic and that the tests are small and illustrative only. That combination of layers, filters, and marginal rule does not appear in the TSP literature they cite, so the encoding itself is new even though the underlying tensor-network machinery is not. They also adapt the same construction to several TSP variants and run it on a job-reassignment instance as an industrial example. The stress-test note finds no internal inconsistency in the central claim: if the network contracts exactly, the marginals do encode the support of the minimum-cost feasible configurations. The paper is therefore on solid ground as a formulation. The soft spots are exactly what the abstract states. No derivation steps are supplied in the material I saw, the practical extraction rule is acknowledged to be heuristic, and the experiments do not claim or demonstrate computational advantage over existing solvers. Numerical stability of the contractions for larger instances is not addressed. This is a paper for people already working on tensor networks for combinatorial optimization who want to see one more encoding. It is not aimed at readers looking for new algorithms or scaling results. The work shows clear thinking and states its limits plainly, so it deserves a serious referee rather than a desk reject.

Referee Report

1 major / 1 minor

Summary. The manuscript presents a tensor-network formulation of the Traveling Salesman Problem (TSP) and variants. Candidate tours are represented via tensor-network layers, weighted by Boltzmann factors according to tour cost, and constrained by explicit counting-filter tensors (e.g., visit-once and degree-2 conditions). The central claim is that this construction yields an explicit tensor-network marginal formula whose zero-temperature, exact-arithmetic limit recovers an optimal feasible tour via a sequential marginal rule. The approach is adapted to several TSP generalizations and demonstrated on the Job Reassignment Problem; all experiments are small and illustrative, with finite-τ extraction explicitly qualified as heuristic.

Significance. If the unshown derivation of the marginal formula and its limiting behavior can be supplied and verified, the work would supply a novel, constraint-explicit encoding of combinatorial optimization inside the tensor-network formalism. This could open routes to contraction-based solvers or quantum-inspired algorithms. The manuscript's honesty about the heuristic status of finite-τ extraction and its deliberate choice of illustrative rather than competitive experiments are positive features that keep the claims proportionate.

major comments (1)

[Abstract] Abstract (and the corresponding construction section): the central claim that the zero-temperature, exact-arithmetic limit of the tensor-network marginal formula identifies an optimal feasible tour through a sequential marginal rule is stated without any derivation steps, explicit marginal expression, or proof that the resulting marginals remain supported only on feasible tours and select a minimum-cost one. This derivation is load-bearing for the paper's primary contribution.

minor comments (1)

The manuscript repeatedly notes that finite-τ behavior is heuristic and depends on numerical contrast and near-degeneracies, but does not supply a quantitative characterization (e.g., condition-number bounds or failure-mode examples) that would help readers assess when the heuristic is reliable.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading, balanced summary, and recognition that a verified marginal formula would constitute a novel contribution. We agree that the central claim requires explicit derivation and supporting proofs, which were omitted from the original manuscript.

read point-by-point responses

Referee: [Abstract] Abstract (and the corresponding construction section): the central claim that the zero-temperature, exact-arithmetic limit of the tensor-network marginal formula identifies an optimal feasible tour through a sequential marginal rule is stated without any derivation steps, explicit marginal expression, or proof that the resulting marginals remain supported only on feasible tours and select a minimum-cost one. This derivation is load-bearing for the paper's primary contribution.

Authors: We fully agree that the derivation, explicit marginal expression, and supporting proofs are missing and constitute a load-bearing gap. In the revised manuscript we will insert a dedicated subsection (placed after the tensor-network construction) that (i) writes the explicit marginal formula obtained by contracting all but one index of the weighted, filtered network, (ii) proves by induction on the filter tensors that every marginal is supported exclusively on feasible partial tours, and (iii) shows that, in the joint limit of exact arithmetic and τ→0, the Boltzmann weights concentrate on minimum-cost configurations, so that the sequential marginal rule recovers an optimal feasible tour. The added material will also clarify the precise sense in which finite-τ extraction remains heuristic. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; derivation self-contained

full rationale

The paper defines a tensor-network encoding of TSP tours via explicit layers, Boltzmann weighting, and counting-filter tensors for constraints. The marginal formula and its zero-temperature limit are direct mathematical consequences of this network definition and the sequential marginal rule; they do not reduce to fitted parameters, renamed inputs, or load-bearing self-citations. No uniqueness theorem or ansatz is smuggled in via prior author work. The construction is presented as a fresh encoding whose formal properties follow from the tensor algebra without circular reduction.

Assumptions & free parameters 0 free parameters · 0 assumptions · 0 invented entities

Only the abstract is available; no explicit free parameters, axioms, or invented entities are stated. The construction implicitly assumes that the tensor network can be defined and contracted without introducing new fitted scales beyond the temperature parameter already named.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Tensor-Network Formulation of the Traveling Salesman Problem and Variants." pith.science (2026). https://pith.science/paper/TKW6EDSS

@misc{pith2026231114344,
  author       = {Pith},
  title        = {Pith review of: Tensor-Network Formulation of the Traveling Salesman Problem and Variants},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TKW6EDSS}},
  note         = {Machine review of arXiv:2311.14344}
}

abstract

This work presents a tensor-network formulation of the Traveling Salesman Problem (TSP) and several of its variants. The approach represents candidate tours with tensor-network layers, weights them by Boltzmann factors, and enforces constraints through explicit counting filters. This formalism also yields an explicit tensor-network marginal formula whose zero-temperature, exact-arithmetic limit identifies an optimal feasible tour through a sequential marginal rule. At finite $\tau$ and finite precision, the implemented extraction is a heuristic whose behavior depends on numerical contrast, calibration, and near-degeneracies. We adapt the construction to several generalizations of the TSP and apply it to the Job Reassignment Problem, as a representative industrial integration. The experiments are deliberately small and illustrative; they contextualize the method against exact and heuristic references but do not establish general computational superiority over specialized classical solvers.

Figures

Figures reproduced from arXiv: 2311.14344 by the authors.

**Figure 1.** TSP graph with the solution ⃗x = (0, 3, 1, 6, 4, 2, 9, 8, 13, 11, 7, 12, 10, 5). The blue edges represent possible paths that were not taken, and arrowed red edges represent the path taken by the solution. Edges with weight considered infinite are not represented. With this formulation, the problem can be expressed as ⃗xopt = arg min ⃗x (C (⃗x)) xt ∈ [0, N − 1] ∀t ∈ [0, N − 1] xt ̸= xt ′ ∀t ̸= t ′ ∈ [0, N − 1] C… view at source ↗

**Figure 2.** TSP tensor network, with the initialization and [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** Notation for all indexes used in all tensors in [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Contraction scheme for 3 variables with the [PITH_FULL_IMAGE:figures/full_fig_p006_4.png]

**Figure 5.** Figure 5: MPO layer for 3 multiple bond index tensors. [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

A quantum speedup algorithm for TSP based on quantum dynamic programming with very few qubits
quant-ph 2025-02 conditional novelty 6.0 of 10

A quantum dynamic programming circuit prepares the uniform superposition of all Hamiltonian cycles in polynomial gates, reducing Grover-based TSP search complexity to O(sqrt((N-1)!).
Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN
cs.ET 2025-02 reject novelty 4.0 of 10

Any finite combinatorial problem with a known logical circuit can be encoded as a tensor network whose contraction defines an explicit, though generally inefficient, solution equation.
Quantum Computing in Industrial Environments: Where Do We Stand and Where Are We Headed?
quant-ph 2025-05 unverdicted novelty 1.0 of 10

A review of quantum computing for industrial optimization that summarizes existing approaches and introduces a web demonstrator for job-shop scheduling, without presenting new research results.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages · cited by 3 Pith papers

[1]

A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems

Manfred Padberg and Giovanni Rinaldi. A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Review, 33(1):60–100, 1991. DOI: 10.1137/1033004. URLhttps://doi. org/10.1137/1033004

work page doi:10.1137/1033004 1991
[2]

Michael Held and Richard M. Karp. A dy- namic programming approach to sequencing problems. Journal of the Society for Indus- trial and Applied Mathematics , 10(1):196– 210, 1962. ISSN 03684245. URL http: //www.jstor.org/stable/2098806

work page arXiv 1962
[3]

A genetic algorithm for solving travelling salesman problem

Adewole Philip, Akinwale Adio Taofiki, and Otunbanowo Kehinde. A genetic algorithm for solving travelling salesman problem. International Journal of Advanced Com- puter Science and Applications , 2(1), 2011. DOI: 10.14569/IJACSA.2011.020104. URL http://dx.doi.org/10.14569/IJACSA. 2011.020104

work page doi:10.14569/ijacsa.2011.020104 2011
[4]

Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem,

Nicos Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. Operations Research Forum , 3 (1):20, Mar 2022. ISSN 2662-2556. DOI: 10.1007/s43069-021-00101-z. URLhttps:// doi.org/10.1007/s43069-021-00101-z

work page doi:10.1007/s43069-021-00101-z 2022
[5]

P.W. Shor. Algorithms for quantum com- putation: discrete logarithms and fac- toring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124–134, 1994. DOI: 10.1109/SFCS.1994.365700

work page doi:10.1109/sfcs.1994.365700 1994
[6]

A quantum approximate opti- mization algorithm, 2014

Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate opti- mization algorithm, 2014

work page 2014
[7]

Peruzzo , author J

Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O’Brien. A variational eigen- value solver on a photonic quantum pro- cessor. Nature Communications , 5(1): 4213, Jul 2014. ISSN 2041-1723. DOI: 10.1038/ncomms5213. URL https://doi. org/10.1038/ncomms5213

work page doi:10.1038/ncomms5213 2014
[8]

Fixed-point grover adaptive search for binary optimiza- tion problems, 2024

ÁkosNagy, JaimePark, CindyZhang, Atithi Acharya, and Alex Khan. Fixed-point grover adaptive search for binary optimiza- tion problems, 2024

work page 2024

Show all 21 references

[9]

Behera, and Prasanta K

Karthik Srinivasan, Saipriya Satyajit, Bikash K. Behera, and Prasanta K. Pan- igrahi. Efficient quantum algorithm for solving travelling salesman problem: An ibm quantum experience, 2018

2018
[10]

A realizable gas-based quantum algorithm for traveling salesman problem, 2022

Jieao Zhu, Yihuai Gao, Hansen Wang, Tiefu Li, and Hao Wu. A realizable gas-based quantum algorithm for traveling salesman problem, 2022

2022
[11]

DOI: 10.1137/1.9781611975482.107

Andris Ambainis, Kaspars Balodis, J¯ anis Iraids, Martins Kokainis, Krišj¯ anis Pr¯ usis, and Jevg¯ enijs Vihrovs.Quantum Speedups for Exponential-Time Dynamic Pro- gramming Algorithms , pages 1783–1793. DOI: 10.1137/1.9781611975482.107. URL https://epubs.siam.org/doi/abs/10. ...

doi
[12]

Tensor networks in a nutshell, 2017

Jacob Biamonte and Ville Bergholm. Tensor networks in a nutshell, 2017

2017
[13]

Perez-Garcia, F

D. Perez-Garcia, F. Verstraete, M. M. Wolf, and J. I. Cirac. Matrix product state repre- sentations, 2007

2007
[14]

V. Murg F. Verstraete and J.I. Cirac. Matrix product states, projected en- tangled pair states, and variational renormalization group methods for quantum spin systems. Advances in Physics, 57(2):143–224, 2008. DOI: Accepted inQuantum 9999-99-99, click title to verify. Publishe...

2008 doi
[15]

Implementation of quantum imaginary-time evolution method on nisq devices by introducing nonlocal approximation

Hirofumi Nishi, Taichi Kosugi, and Yu- ichiro Matsushita. Implementation of quantum imaginary-time evolution method on nisq devices by introducing nonlocal approximation. npj Quantum Informa- tion, 7(1):85, Jun 2021. ISSN 2056-

2021
[16]

URL https://doi.org/10.1038/ s41534-021-00409-y

DOI: 10.1038/s41534-021-00409- y. URL https://doi.org/10.1038/ s41534-021-00409-y

doi
[17]

Ttopt: A max- imum volume quantized tensor train-based optimization and its application to reinforce- ment learning, 2022

Konstantin Sozykin, Andrei Chertkov, Ro- man Schutski, Anh-Huy Phan, Andrzej Ci- chocki, and Ivan Oseledets. Ttopt: A max- imum volume quantized tensor train-based optimization and its application to reinforce- ment learning, 2022

2022
[18]

Kalayci, and Alejandro Perdomo- Ortiz

Javier Alcazar, Mohammad Ghazi Vakili, Can B. Kalayci, and Alejandro Perdomo- Ortiz. Enhancing combinatorial opti- mization with classical and quantum gen- erative models. Nature Communica- tions, 15(1):2761, Mar 2024. ISSN 2041-1723. DOI: 10.1038/s41467-024- 46959-5. URL http...

2024 doi
[19]

A quantum-inspired tensor network algorithm for constrained combinatorial optimization problems

Tianyi Hao, Xuxin Huang, Chunjing Jia, and Cheng Peng. A quantum-inspired tensor network algorithm for constrained combinatorial optimization problems. Frontiers in Physics , 10, 2022. ISSN 2296-424X. DOI: 10.3389/fphy.2022.906590. URL https://www.frontiersin.org/ articles/10....

2022 doi
[20]

de Leceta

Alejandro Mata Ali, Iñigo Perez Del- gado, Marina Ristol Roura, and Aitor Moreno Fdez. de Leceta. Polynomial-time solver of tridiagonal qubo and qudo prob- lems with tensor networks, 2024

2024
[21]

Qubo resolu- tion of the job reassignment problem

Iñigo Perez Delgado, Beatriz García Markaida, Alejandro Mata Ali, and Aitor Moreno Fdez de Leceta. Qubo resolu- tion of the job reassignment problem. In 2023 IEEE 26th International Conference on Intelligent Transportation Systems (ITSC), pages 4847–4852, 2023. DOI: 10.1109/IT...

2023 doi

Pith tools

Reviewed May 24, 2026 · model on record in the stance chip above.

[1] [1]

A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems

Manfred Padberg and Giovanni Rinaldi. A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Review, 33(1):60–100, 1991. DOI: 10.1137/1033004. URLhttps://doi. org/10.1137/1033004

work page doi:10.1137/1033004 1991

[2] [2]

Michael Held and Richard M. Karp. A dy- namic programming approach to sequencing problems. Journal of the Society for Indus- trial and Applied Mathematics , 10(1):196– 210, 1962. ISSN 03684245. URL http: //www.jstor.org/stable/2098806

work page arXiv 1962

[3] [3]

A genetic algorithm for solving travelling salesman problem

Adewole Philip, Akinwale Adio Taofiki, and Otunbanowo Kehinde. A genetic algorithm for solving travelling salesman problem. International Journal of Advanced Com- puter Science and Applications , 2(1), 2011. DOI: 10.14569/IJACSA.2011.020104. URL http://dx.doi.org/10.14569/IJACSA. 2011.020104

work page doi:10.14569/ijacsa.2011.020104 2011

[4] [4]

Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem,

Nicos Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. Operations Research Forum , 3 (1):20, Mar 2022. ISSN 2662-2556. DOI: 10.1007/s43069-021-00101-z. URLhttps:// doi.org/10.1007/s43069-021-00101-z

work page doi:10.1007/s43069-021-00101-z 2022

[5] [5]

P.W. Shor. Algorithms for quantum com- putation: discrete logarithms and fac- toring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124–134, 1994. DOI: 10.1109/SFCS.1994.365700

work page doi:10.1109/sfcs.1994.365700 1994

[6] [6]

A quantum approximate opti- mization algorithm, 2014

Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate opti- mization algorithm, 2014

work page 2014

[7] [7]

Peruzzo , author J

Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O’Brien. A variational eigen- value solver on a photonic quantum pro- cessor. Nature Communications , 5(1): 4213, Jul 2014. ISSN 2041-1723. DOI: 10.1038/ncomms5213. URL https://doi. org/10.1038/ncomms5213

work page doi:10.1038/ncomms5213 2014

[8] [8]

Fixed-point grover adaptive search for binary optimiza- tion problems, 2024

ÁkosNagy, JaimePark, CindyZhang, Atithi Acharya, and Alex Khan. Fixed-point grover adaptive search for binary optimiza- tion problems, 2024

work page 2024