A compact digital compute-in-memory Ising annealer with probabilistic SRAM bit in 28 nm for travelling salesman problem

Why smarter routes and chips matter

Every day, delivery trucks, airplanes, and data packets must decide which path to take so that everything arrives on time with minimal cost. This type of puzzle, known as the Traveling Salesman Problem, quickly becomes overwhelming for even powerful computers as the number of stops grows. The paper behind this summary introduces a new kind of specialized chip that tackles such route-planning problems far more efficiently, using ideas borrowed from magnetic materials and built directly into standard computer memory.

A classic puzzle of visiting every stop once

The Traveling Salesman Problem asks a simple question: given a list of cities and the distances between them, what is the shortest tour that visits each city exactly once and returns to the start? The catch is that the number of possible tours explodes as cities are added, so checking every option is impossible in practice. Instead, modern approaches search for very good, if not perfect, routes. One promising approach imitates how a network of tiny magnets, called an Ising model, can settle into a low-energy state that represents a good solution. By carefully letting this network "wiggle" through random changes that gradually calm down, the system escapes bad local choices and finds better routes.

Turning a memory chip into a problem solver

Rather than running this process in ordinary processors, the authors build it into the memory hardware itself, a strategy called compute-in-memory. They design a compact chip in a 28-nanometer technology where each tiny memory cell stores both distance information and participates directly in the calculations. Cleverly, the chip uses the natural manufacturing imperfections of its memory cells as a built-in source of randomness, eliminating the need for bulky random-number generators. By briefly disturbing the stored values with a controlled voltage "nudge," some bits flip in a probabilistic way, providing the gentle randomness needed for the annealing process without extra circuitry.

Breaking big maps into small neighborhoods

One of the main obstacles to using Ising-style solvers on large route-planning tasks is the sheer amount of data required: a fully detailed representation of a 96-city tour would normally need a vast web of connections and memory. To avoid this, the researchers group nearby cities into small clusters and then arrange those clusters in several levels of a hierarchy. At the highest level, the chip solves how clusters should be ordered; at the next level, it refines the order of cities within each cluster; and so on. This stepwise approach slashes the amount of memory and connections needed, cutting the hardware complexity from something that grows with the fourth power of city count down to something that only grows with the square, and then compressing the stored distances even further by packing only the truly needed ones tightly together.

How the chip updates many choices at once

Inside the chip, groups of three cities form basic building blocks that are handled in parallel. The memory array is organized so that within each cluster, the circuit can rapidly compute the change in overall tour length if sections of the tour are swapped. Because some clusters do not interact directly, the system can update all "odd" clusters in one step and all "even" clusters in the next, speeding up the search while still behaving as if changes were made one at a time. During each round, the chip uses its noisy memory cells to decide whether to accept a worse move with some probability—high at the beginning to explore, and lower later to settle down—mimicking the cooling of a metal and steering the route toward shorter and shorter distances.

From laboratory chip to large-scale routes

The prototype chip contains a modest 6 kilobits of this special memory yet can already solve 96-city Traveling Salesman instances in about 620 microseconds while using less than a microjoule of energy. Compared with previous hardware designed for the same task, it achieves improvements of up to hundreds of times in how much memory it needs per unit of problem size. Simulations also show that by placing many such memory blocks side by side, the same design could scale to problems with thousands of cities while keeping hardware growth nearly linear. For a lay reader, the key takeaway is that by reshaping a familiar memory chip into an active problem solver—and by turning unavoidable manufacturing quirks into a useful feature—this work points toward small, fast, and energy-thrifty hardware that can help plan complex routes and schedules in real time.

Citation: Kong, Y., Lu, A., Liu, H. et al. A compact digital compute-in-memory Ising annealer with probabilistic SRAM bit in 28 nm for travelling salesman problem. npj Unconv. Comput. 3, 15 (2026). https://doi.org/10.1038/s44335-026-00060-w

Keywords: travelling salesman problem, Ising annealer, compute-in-memory, SRAM hardware, combinatorial optimization