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

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.

Authors

Institutions

Publication Details

Journal
Nature Communications
Published
2025-12-04
DOI
https://doi.org/10.1038/s41467-025-66864-9
Citations
1
Primary Topic
Quantum Computing Algorithms and Architecture
Type
article
Field-Weighted Citation Impact
2.48

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

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

Shiqiang Liu, Xiufeng Han, Caihua Wan, Meike Hindenberg et al.
1 citations
Nature Communications
Quantum Computing Algorithms and Architecture
2.48
article

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

Shiqiang Liu, Xiufeng Han, Caihua Wan, Meike Hindenberg, Alptekin Vardar, Raik Hoffmann, Yihui Sun, Thomas Kämpfe, Guoqiang Yu, Shikun He, Zejie Zheng, Yingqian Xu, Qiang Dai, Shilong Xiong, Ran Zhang, Xiaohan Li, Junlu Gong, Dehao Kong
article en
1 citations

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.

Nature CommunicationsVol. 17(1)
Chinese Academy of Sciences (CN), Fraunhofer Institute for Photonic Microsystems (DE), Songshan Lake Materials Laboratory (CN), FZU ‒ Institute of Physics of the Academy of Sciences of the Czech Republic (CZ), Fraunhofer Institute for Surface Engineering and Thin Films (DE), Institute of Physics (CN), Zhejiang Medicine (China) (CN), National Laboratory for Superconductivity (CN), University of Chinese Academy of Sciences (CN), Technische Universität Braunschweig (DE)
National Natural Science Foundation of China, Chinese Academy of Sciences, Youth Innovation Promotion Association of the Chinese Academy of Sciences, National Key Research and Development Program of China, Youth Innovation Promotion Association
Openalex Percentile: Top 8%
Quantum Computing Algorithms and Architecture
2.48
DOIOpen Access PDFOpenAlex
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.