How can a delivery truck visit dozens of cities exactly once and return home on the shortest possible route? This famous question, known as the traveling salesman problem (TSP), lies at the heart of logistics, network design and even parts of artificial intelligence. It is also notoriously hard to solve efficiently when the number of cities becomes large.

In the study entitled "Probabilistic Greedy Algorithm Solver Using Magnetic Tunneling Junctions for Traveling Salesman Problem" published in Nature Communications, team from the Institute of Physics, Chinese Academy of Sciences (IOP, CAS), together with collaborators in Germany and industry partners in China, has demonstrated a new way to tackle this classic problem. By combining a hardware true random number generator based on magnetic tunnel junctions (MTJs) with a "probabilistic greedy" algorithm, they build a solver that finds high-quality routes faster and more efficiently than widely used methods such as simulated annealing and genetic algorithms.

From magnetic memory to hardware randomness

MTJs are the core building blocks of modern spintronic memories. They consist of two magnetic layers separated by an ultra-thin insulating barrier. Depending on the relative orientation of the magnetizations, the device shows a high or low electrical resistance.

In this work, the team led by Prof. Xiufeng Han, A. Prof. Caihua Wan (IOP, CAS) and Prof. Thomas Kämpfe (Fraunhofer IPMS) uses MTJs in a very different way: as tiny physical dice. When the researchers apply voltage pulses to the device, the magnetic state of the "free" layer switches in a stochastic manner. By carefully characterizing this behavior, they show that the switching probability follows a smooth S-shaped curve as a function of the applied voltage.

Crucially, this probability can be tuned very precisely. By adjusting pulse conditions, the MTJ can be made to switch with, for example, 25%, 50% or 80% probability, and to maintain this behavior over long sequences of operations. Using multiple MTJs in parallel, the team engineers a hardware true random number generator (TRNG) whose output can be shaped into a wide range of target probability distributions, including Gaussian, uniform, exponential and user-defined profiles.

To make this approach practical and scalable, the researchers implement a hybrid control strategy in which digital pulse-width modulation replaces fine analog voltage tuning. Together with self-stabilizing feedback techniques, this scheme compensates device drift and variation, enabling robust probability control without complex calibration.

A probabilistic twist on a greedy algorithm

Greedy algorithms for TSP always choose the next city that is closest to the current one. They are fast, but they often get trapped in poor local solutions because they never "risk" trying a less obvious move.

The new probabilistic greedy algorithm keeps the simplicity of the greedy idea but injects controlled randomness generated by the MTJ-based TRNG. At each step, the algorithm assigns a probability to every unvisited city. Cities that are closer get higher probability, but all remaining cities retain a non-zero chance of being chosen. A temperature-like parameter, denoted K_BT, controls how sharply the algorithm prefers shorter distances.

When K_BT is very small, the algorithm behaves almost like a standard greedy method and nearly always selects the nearest city. When K_BT is very large, all cities are chosen with similar probability, resembling a random walk. At intermediate values, the algorithm balances "exploitation" of good local choices with "exploration" of alternative routes.

This step-by-step decision process requires random numbers drawn from a probability distribution that changes at every step, as distances and remaining cities are updated. The MTJ-based TRNG is particularly well suited to this task because it can generate random samples that match arbitrary, dynamically updated distributions directly in hardware, without extra computation.

Hardware demonstrations and algorithmic benchmarks

To test the full hardware–algorithm loop, the team first tackles a standard benchmark known as the Burma14 TSP instance, which includes 14 cities. They use four MTJs connected to a National Instruments PXIe system via a probe card and adapter board, controlled by a Python interface. In this setup, the MTJ array supplies probabilistic samples according to the algorithm's changing distributions, while the control system updates city selection and evaluates route length.

The experiments show that the probabilistic greedy solver consistently finds routes that are closer to the known optimal solution than those produced by a classic greedy algorithm. By scanning the temperature parameter K_BT, the researchers identify an optimal window where the probability of reaching the best or near-best route is maximized and good solutions appear within a modest number of iterations.

Because running very large TSP instances entirely in the lab setup would be time-consuming, the team then uses numerical simulations to explore performance on a 70-city benchmark problem (st70). Here they compare the probabilistic greedy algorithm with several other heuristics, including simulated annealing, genetic algorithms and the standard greedy method.

The results indicate that the probabilistic greedy solver converges faster and more reliably to high-quality routes. A key advantage is that, in each sampling step, it can consider all remaining cities under an arbitrary probability distribution provided by the MTJ-inspired TRNG model, rather than only testing limited local changes such as swapping two cities. This enables the algorithm to explore a more "entangled" search space while still maintaining relatively low time and memory costs.

Toward hardware-accelerated optimization and AI

Beyond demonstrating improved performance on specific TSP benchmarks, the authors analyze how an integrated hardware solver based on MTJ arrays could scale. Their prototype, built from ~100 nm spin-transfer torque MTJs controlled by laboratory instrumentation, already solves a 14-city TSP instance in about 20 milliseconds, with the runtime dominated by measurement electronics rather than the devices themselves.

Extrapolating from published MTJ switching times in the nanosecond range, they estimate that a dedicated FPGA or ASIC implementation could reduce solution times to sub-millisecond levels while cutting energy consumption by several orders of magnitude. The architecture requires only a logarithmic number of MTJs with respect to the number of choices and linear memory for storing conditional probabilities, which is significantly lighter than many existing probabilistic hardware approaches such as Ising machines or Boltzmann machines.

Interestingly, the authors note that their step-by-step sampling process resembles the way large language models generate text token by token from a dynamically updated probability distribution. This conceptual link suggests that spintronic probabilistic hardware might, in the future, support not only classic optimization tasks but also parts of AI inference that rely on structured random sampling.

"Our work shows that hardware true randomness with tunable statistics is not just a curiosity," said the authors. "It can directly improve heuristic search and offers a natural path toward energy-efficient, scalable optimization engines."

The same probabilistic framework can be extended to other NP-hard problems, such as graph coloring and scheduling, by redefining the cost function and adjusting the temperature-like control parameter. Future efforts will focus on FPGA and ASIC implementations and on embedding such spintronic TRNG arrays into parallel and distributed computing architectures.

This work was supported by the National Key Research and Development Program of China, the National Natural Science Foundation of China, and the Chinese Academy of Sciences.

Fig. MTJ-based true random number generator with adjustable probability distribution and the probabilistic greedy algorithm TSP solver. (a) Schematic of the device structure and measurement setup. (b) Resistance switching behavior of the MTJ induced by current pulses, which trigger free layer magnetization switching. (c) MTJ switching probability as a function of applied write voltage. The black solid line represents the fitted sigmoidal curve. (d) Generated random numbers exhibiting a Gaussian distribution. (e) Scatter plot of the best solutions across K_BT=1 to 400 (left) and density distribution plots of solutions within 0, 50, and 100 kilometers of the known best solution (right). Each density plot is based on 100 independent solution runs using the probabilistic greedy algorithm. (f) Relationship between the best path distance and the number of iterations for four selected K_BT values. When K_BT=60, the optimal solution can be achieved within 1000 iterations. (Image by Institute of Physics)

Contact:
Institute of Physics
HAN Xiufeng
Email: xfhan@iphy.ac.cn

Key words:
Spintronics; Magnetic Tunnel Junction; True Random Number Generator; Combinatorial Optimization; Traveling Salesman Problem

Abstract:
Researchers demonstrate a probabilistic optimization strategy that uses magnetic-tunnel-junction-based true random number generators to guide the search process in the traveling salesman problem. By tuning the stochastic switching behavior of MTJs to produce configurable probability distributions, the method balances exploration and exploitation and achieves high-quality solutions more efficiently than conventional heuristic algorithms. The work highlights a promising direction for hardware-accelerated combinatorial optimization using spintronic randomness.