Combinatorial Optimization with Tensor Networks

A new study explores the application of tensor networks to solve the traveling salesman problem (TSP), a classic example of combinatorial optimization. The method, called TN-GEO (Tensor Network Generator-Enhanced Optimization), is based on a tensor network Born machine that uses automatically differentiable matrix product states (MPS) as a generative model.

Formulation and Advantages

Unlike approaches based on binary encoding, which require a quadratic number of variables and penalty terms to ensure valid solutions, this method adopts a permutation-based formulation with integer variables. The use of autoregressive sampling with masking ensures that every generated solution is a valid tour.

Efficient Modeling with k-grams

The study also introduces a k-site MPS variant that learns distributions over k-grams (consecutive city subsequences) using a sliding window approach. This allows for parameter-efficient modeling for larger instances.

Performance and Validation

Experimental validation on TSPLIB benchmarks with instances up to 52 cities demonstrates that TN-GEO can outperform classical heuristics, such as swap and 2-opt hill-climbing algorithms. The k-site variants, which focus more on local correlations, show better results than the full-MPS case.