Tabu-Enhanced Simulated Bifurcation for combinatorial optimization
Xian-Zhe Tao, Qing-Guo Zeng, Zu-Jia Huang, Bo-Wei Zuo, Yong-Qing Liu, Jiapei Zhuang, H. Okawa, Man‐Hong Yung · Communications Physics · 2026
Simulated Bifurcation (SB) algorithms, inspired by quantum annealing, can efficiently solve large-scale combinatorial optimization problems on classical hardware, often outperforming traditional approaches such as simulated annealing. However, their tendency to be trapped in local optima limits global solution quality. In this work, we introduce Tabu-Enhanced Simulated Bifurcation (TESB), an improved SB variant that incorporates a Tabu Search-inspired mechanism. By leveraging a dynamic penalty guided by early search history, TESB can naturally avoid revisiting suboptimal regions. On Max-Cut benchmarks, TESB achieves up to a three-order-of-magnitude reduction in Time-to-Solution compared to standard SB. When applied to particle track reconstruction in high-energy physics, TESB identifies lower-energy configurations on problems exceeding 100,000 spin variables, demonstrating enhanced scalability and performance across a wide range of combinatorial tasks. Combinatorial optimization is a challenging yet crucial class of problems, and Simulated Bifurcation (SB) is a promising approximate solver developed in recent years. The authors enhance SB with ideas from Tabu Search to improve its performance, demonstrating clear gains on Max-Cut and particle track reconstruction problems.