Tabu-Enhanced Simulated Bifurcation for combinatorial optimization

Why smarter searching matters

From routing delivery trucks to matching particles in a collider, many of today’s toughest computing tasks boil down to one challenge: finding the best choice in a staggering number of possibilities. These so‑called combinatorial problems power logistics, finance, biology, and engineering, but they are so complex that even supercomputers can struggle. This article introduces a new algorithmic twist, called Tabu‑Enhanced Simulated Bifurcation (TESB), that helps computers avoid getting stuck in dead ends and reach better answers much faster.

Hard choices in a landscape of possibilities

Researchers often picture combinatorial problems as a rugged landscape full of hills and valleys. Each point in this landscape represents a possible solution, and the height corresponds to its “energy” or cost; low valleys are good solutions, and the deepest valley is the best. Many real‑world tasks, like cutting a network into two well‑separated parts (the Max‑Cut problem) or reconstructing particle tracks in a detector, can be translated into such an energy landscape using a mathematical model known as the Ising model. The catch is that these landscapes have astronomically many valleys, so a search procedure can easily settle into a merely decent hollow and never discover that a much deeper one exists elsewhere.

From quantum ideas to classical speed

Simulated Bifurcation (SB) is a relatively new, physics‑inspired approach to exploring these rugged landscapes. Instead of hopping from one discrete solution to another, SB imagines a system of particles moving in a smooth version of the landscape, governed by equations similar to those in classical mechanics. As a control parameter is slowly changed, the system “bifurcates” and the particles’ positions tip toward low‑energy valleys that encode good solutions. SB has already shown strong performance on large problems and runs efficiently on graphics processors, but it shares a weakness with many search methods: it can become trapped in local minima, especially on irregular, densely connected problems where some regions of the landscape are much more tangled than others.

Adding memory to avoid old traps

The key idea behind TESB is to give SB a kind of short‑term memory, inspired by a well‑known strategy in optimization called tabu search. In tabu search, the algorithm keeps a list of recently explored bad solutions and temporarily forbids moves that would return to them. TESB translates this concept into the energy landscape picture. First, a “warming up” stage uses the original SB algorithm to quickly generate many approximate solutions. These correspond to local valleys where the system tends to get stuck. Then TESB modifies the landscape by adding a gentle penalty around those regions, effectively raising the floor of those valleys. During the subsequent “checking” stage, the system evolves again in this reshaped landscape, now encouraged to bypass the old traps and roam toward deeper, previously unexplored valleys.

Keeping the search lively with small nudges

A practical challenge is how to use this memory without overdoing it. If TESB penalized every past valley equally and permanently, it could flatten the landscape so much that useful guidance disappears. To avoid this, the method borrows another idea from modern machine learning: mini‑batches. At each step in the checking phase, TESB randomly selects only a small subset of the stored suboptimal solutions to contribute to the penalty. This keeps the landscape shifting just enough to push the system away from well‑trodden areas, while preserving overall structure and diversity in the search. Numerical tests show that this strategy lets TESB continue improving long after the original SB dynamics have effectively stalled.

Putting the method to the test

The authors benchmarked TESB on standard Max‑Cut test graphs and on demanding problems from high‑energy physics, where reconstructing the paths of charged particles is both vital and computationally intense. On the Max‑Cut benchmarks, TESB often reaches optimal or near‑optimal cuts far more reliably than the original SB variants. Measured by “time to solution” — how long it takes, on average, to obtain a target‑quality answer — TESB can be up to a thousand times faster on the most challenging instances. In particle track reconstruction tasks involving more than one hundred thousand variables, TESB consistently finds configurations with lower energy (meaning better fits to the data) while using less compute time than the baseline methods, highlighting its scalability to real‑world, very large systems.

What this means going forward

In plain terms, TESB turns a fast but sometimes short‑sighted searcher into a more strategic explorer that remembers where it has been and learns to avoid bad neighborhoods. By reshaping the energy landscape around past missteps rather than starting over from scratch, it greatly increases the chance of reaching high‑quality solutions in a reasonable time. This blend of physics‑inspired dynamics with classical tabu ideas suggests a broader path forward: many unconventional optimization engines, whether classical or quantum‑inspired, could gain a similar boost by incorporating smart, history‑aware penalties. For applications that depend on solving ever larger and tougher combinatorial puzzles, TESB offers a promising new tool to push past previous performance limits.

Citation: Tao, XZ., Zeng, QG., Huang, ZJ. et al. Tabu-Enhanced Simulated Bifurcation for combinatorial optimization. Commun Phys 9, 100 (2026). https://doi.org/10.1038/s42005-026-02538-2

Keywords: combinatorial optimization, simulated bifurcation, tabu search, Max-Cut, particle track reconstruction