# Many-Qudit representation for the Travelling Salesman Problem Optimisation

arXiv: https://arxiv.org/abs/2102.13298 · HTML: https://mlsanity.com/paper/2102.13298/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2021.

## Built on by (most cited first, 2 of 2)

- [Supplementing Recurrent Neural Networks with Annealing to Solve Combinatorial Optimization Problems](https://mlsanity.com/paper/2207.08189/) (2022)
- [Variational decision diagrams for quantum-inspired machine learning applications](https://mlsanity.com/paper/2502.04271/) (2025)

## Abstract (arXiv)

We present a map from the travelling salesman problem (TSP), a prototypical NP-complete combinatorial optimisation task, to the ground state associated with a system of many-qudits. Conventionally, the TSP is cast into a quadratic unconstrained binary optimisation (QUBO) problem, that can be solved on an Ising machine. The size of the corresponding physical system's Hilbert space is 2N2, where N is the number of cities considered in the TSP. Our proposal provides a many-qudit system with a Hilbert space of dimension 2Nlog2N, which is considerably smaller than the dimension of the Hilbert space of the system resulting from the usual QUBO map. This reduction can yield a significant speedup in quantum and classical computers. We simulate and validate our proposal using variational Monte Carlo with a neural quantum state, solving the TSP in a linear layout for up to almost 100 cities.