Solving the traveling salesman problem on $\lceil \log_2 (N-1)! \rceil$ qubits with a variational quantum Kolmogorov--Arnold network: exact-gradient CVaR training and generalization over time-dependent graphs

Title:Solving the traveling salesman problem on $\lceil \log_2 (N-1)! \rceil$ qubits with a variational quantum Kolmogorov--Arnold network: exact-gradient CVaR training and generalization over time-dependent graphs

Abstract:The one-hot encoding of the traveling salesman problem (TSP) on quantum hardware needs $(N-1)^2$ qubits for $N$ sites and penalty terms that dominate the cost landscape. Permutation encodings that label every tour by its Lehmer code need only $\lceil \log_2 (N-1)! \rceil$ qubits and no penalty term, but variational solvers on them have reached the optimum reliably only up to six sites. Here we show how to train such a solver so that it scales to ten sites and transfers across graphs. A variational quantum Kolmogorov--Arnold network (VQKAN) generates the angles of a shallow circuit from the time and from features of the distance matrix; the circuit is trained on the conditional value at risk (CVaR) of the tour length with an exact adjoint gradient, a risk-level schedule, multi-start, small-angle initialization, and basin-hopping restarts, and the qubits are read as a Gray code so that neighbouring states are neighbouring tours. The method returns the optimal tour on every instance tested for $N = 4$ to $10$ (symmetric polygons and asymmetric random graphs), and in 112 of 120 cases of a thirty-run repetition at $N = 10$ with the remaining gaps at 1\% of the optimum, using 3 to 19 qubits where one-hot encoding needs 9 to 81, with as few as $10^2$ measurement shots. With the distance features as inputs, one parameter set generalizes to unseen times on time-dependent graphs. An ablation identifies basin hopping as the ingredient that removes the residual local minima at $N = 10$, while deeper circuits do not help; controls against 2-opt, the one-hot encoding, and an $N$-qubit one-hot walk separate the circuit's contribution from classical post-processing.

arXiv:2509.22752 [quant-ph]

(or arXiv:2509.22752v2 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2509.22752 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.