Combinatorial optimization problems like the traveling salesman are typically encoded in binary: each variable is 0 or 1, and constraints are enforced through penalty terms in the objective function. Visit each city exactly once becomes a set of quadratic penalties. The penalties work — violating a constraint increases the cost — but they inflate the problem. An N-city TSP requires O(N²) binary variables and many penalty terms. Most of the optimization effort is spent satisfying constraints, not improving the tour.
Reader note (2026-11-17): Checked against the full text of arXiv:2602.20175 (Sakai and Liu; February 2026), which I had earlier held as matching. The method matches: a permutation formulation with autoregressive sampling and masking, so every sample is a valid tour. Context for the benchmark claim: the instances run from 14 to 52 cities (burma14, ulysses16, ulysses22, att48, eil51, berlin52); the two baselines are swap and 2-opt local-search hill-climbers that start from the sequential tour (1, 2, ..., N) and stop when no improving move exists, which the paper chose because, like the model, they exploit local correlations among cities. On the small instances all the variants, including k = 2, find the optimal tour; on the larger ones (att48, eil51, berlin52) the paper says the full model and k = 2 struggle to converge to the optimum while k = 4 and k = 8 consistently reach the optimal tour, outperforming both heuristics. The paper reports moderate k (4 to 8) outperforming both k = 2 and the full model given limited bond dimensions, and notes that for problems that depend on longer-range correlations a larger k would be expected to be needed.
Sakai and Liu (arXiv:2602.20175) use a permutation-based formulation with integer variables. A tour is a permutation of cities. The generative model — a tensor network Born machine — samples permutations directly using autoregressive sampling with masking. At each step, the model picks the next city from those not yet visited. The mask guarantees every generated sample is a valid tour by construction.
No penalty terms. No constraint violations. Every sample from the generator is feasible. The optimization focuses entirely on tour quality rather than splitting attention between feasibility and optimality.
The k-site matrix product state variants learn distributions over city subsequences using a sliding window, enabling scaling to larger instances. On TSPLIB benchmarks up to 52 cities, the approach outperforms classical swap and 2-opt hill-climbing heuristics.
The general observation: encoding a problem with constraints and then optimizing over unconstrained space (plus penalties) is indirect. Encoding the problem so that the representation itself guarantees feasibility eliminates the constraint-satisfaction overhead entirely. The design of the search space — what is representable — matters as much as the search algorithm within that space.