Probabilistic greedy algorithm solver using magnetic tunneling junctions for traveling salesman problem

Abstract

Abstract Combinatorial optimization underpins applications in artificial intelligence, logistics, and network design, yet classical techniques such as greedy search and dynamic programming struggle to balance efficiency and solution quality at scale. We present a probabilistic framework that embeds true random number generators based on spin-transfer-torque magnetic tunnel junctions into a greedy solver. Intrinsic stochastic switching enables configurable random number distributions, which we use to inject controlled randomness via a temperature parameter that interpolates between deterministic and stochastic choices, balancing exploration and exploitation. Applied to the traveling salesman problem, the framework yields high-quality tours and outperforms simulated annealing and genetic algorithms in solution quality and convergence speed. In larger instances with up to 70 cities, it maintains its advantage, reaching near-optimal solutions with fewer iterations and reduced computational cost. These results show that hardware true randomness with tunable statistics can improve heuristic search and motivate integrated, energy-efficient probabilistic hardware for scalable optimization.