Solving computationally complex problems with Ising machines

A team led by Prof. Pinaki Mazumder is designing quantum-inspired architectures from silicon to solve difficult problems more efficiently than previously possible.

How much faster could you complete a jigsaw puzzle with only four pieces, compared to the same puzzle with 1000 pieces? It could be the difference of seconds to days. Although the rules are simple and the solution is constant, jigsaw puzzles become exponentially more difficult to solve as the number of pieces increases.

In the same way, some optimization problems are conceptually simple but computationally demanding. For example, the maximum cut problem requires a solver to sort a series of connected dots between two bins in a way that maximizes the number of lines connecting dots in different bins. These so-called “quadratic unconstrained binary optimization (QUBO) problems” quickly become unwieldy for both humans and computers as the number of variables increases.

A team of researchers in Electrical and Computer Engineering (ECE), including Professor Pinaki Mazumder, Research Area Specialist Lead Mikhail Erementchouk, and PhD student Aditya Shukla, are designing quantum-inspired technologies to solve QUBO problems more efficiently than currently possible.

This is the first time that anybody has even tried to solve quantum-inspired algorithms on a VLSI chip.

Professor Pinaki Mazumder

“The computing capabilities of computers are slowing down, while the data required to process industry applications is increasing in an exponential way,” said Mazumder. “The data volume is very high. The digital computers cannot cope with these big, real-time business applications.”

Quantum computing will revolutionize the ability to do these types of problems, but it will likely take another decade for researchers to develop and scale the technology up to the level needed for real-world problems.

Instead, Mazumder and his team are working on custom, “quantum-inspired” architectures called Ising machines that can improve computing performance with the technology available now.

“We are motivated by the core belief that for scalability, besides providing high quality solutions in polynomial time, custom optimizing machines should be characterized by simplicity, homogeneity and parallelizability of operations, and independence from external computing resources,” said Shukla.

An Ising machine can be visualized as a network of points that each have a “spin” state influenced by their nearest neighbors. Common examples of Ising models include sets of electrons in a metal, defects in crystals, and even metronomes. The spins naturally settle to a low-energy state. And if the interaction between the spins is engineered in the right way, that state represents a solution to a problem that may appear to have nothing to do with spins—for example, assigning frequencies for communications in a busy area, controlling traffic lights in a city, or even deciding which stock options to trade.

Often, rather than finding the absolute best solution, these machines will achieve a “heuristic” or solution that is close enough to be both useful and efficient to reach. Testing each unique combination of variables in a large QUBO problem to find this heuristic is computationally inefficient and often impossible. Ising machines come to a solution naturally and in parallel, as opposed to the way that a human would use trial-and-error to solve a difficult problem. 

Most Ising machines are binary, allowing spins to be either “up” or “down.” Mazumder’s team used a “relaxed” version of the problem, abandoning the binary constraint and allowing the results to vary continuously. They designed the heuristic software, the hardware architecture, and ultimately, a 64-node integrated circuit. From there, they improved the heuristic to round the solution to a binary state for further computing.

“This is the first example of an Ising machine showing how to solve in parallel a problem, for which only sequential algorithms were previously known,” said Erementchouk.

Mazumder, Shukla, and Erementchouk then designed a prototypical digital computing machine implementing their improved (V2) heuristic on a CMOS-compatible field-programmable gate array (FPGA) and demonstrated its ability to find proper graph coloring, construct Latin squares, and solve Sudoku puzzles.

At the bottom right, a black and white layout of a circuit, showing 64 connected squares of hardware. A bubble to the upper left highlights the layout of each square.
Layout of the integrated circuit with 64 nodes. Each node’s layout is shown in the bubble, with occupancy by various portions of the node (top) and a 3D visual to differentiate the state capacitors from the lower layers (bottom). Diagrams as published in IEEE Transactions on Computers.

“Our approach is not based on superconducting or other types of quantum technology; we are approaching from another side and using CMOS technology to solve our problem,” said Mazumder. “We are using an alternative approach that we know will be scalable.”

Mazumder’s work improves on current quantum-inspired architectures and Ising machines that require ultralow temperatures to operate, run in connection with cloud computers, and have an exponential increase in run time with larger problems. His group’s solution, dubbed the relaxation-based dynamical Ising machine (RDIM), scales polynomially and solves large optimization problems in real time without cloud access or any special environmental conditions.

This research emphasizes the often-overlooked advantages of thinking outside the box of quantum computing and represents a promising path forward for next-generation computing. Mazumder encourages other researchers to pursue this niche and scale the technology up for industry use—as of now, none of the big U.S. companies that develop cryogenic quantum computers are competing in this global emerging technology market.

“This is the first time that anybody has even tried to solve quantum-inspired algorithms on a VLSI chip,” said Mazumder, “so we developed the basic approach and designed the chip. The main intellectual value of this work is the approach that you take to solve these problems—if industry leaders are interested, they can scale it to solve very large problems.”

For example, the RDIM architecture has potential applications to a wide range of commercial applications, including traffic optimization, robot routing and control, material development, drug discovery, and image processing. Integrating this type of quantum-inspired architecture into a more expansive view of quantum technologies in academic and commercial systems is essential for the short-term future of advanced computing, Mazumder asserts.

“If we can solve a problem using silicon technology, which is scalable, why wouldn’t we make a parallel path forward, in addition to the current research focus on new materials and quantum computers which may take a decade to scale before solving real-world problems?” he asked.


Papers of Professor Mazumder’s team on Ising machines

[1] M. Erementchouk, A. Shukla, and P. Mazumder, “On computational capabilities of Ising machines based on nonlinear oscillators,” Physica D: Nonlinear Phenomena, vol. 437, p. 133334, Sep. 2022, doi: 10.1016/j.physd.2022.133334.

[2] A. Shukla, M. Erementchouk, and P. Mazumder, “Custom CMOS Ising Machine Based on Relaxed Burer-Monteiro-Zhang Heuristic,” IEEE Transactions on Computers, vol. 72, no. 10, pp. 2835–2846, Oct. 2023, doi: 10.1109/TC.2023.3272278.

[3] A. Shukla, M. Erementchouk, and P. Mazumder, “Scalable almost-linear dynamical Ising machines,” Natural Computing, Apr. 2024, doi: 10.1007/s11047-024-09983-4.

[4] M. Erementchouk, A. Shukla, and P. Mazumder, “Self-contained relaxation-based dynamical Ising machines,” May 10, 2023, arXiv: arXiv:2305.06414. doi: 10.48550/arXiv.2305.06414, under review in Natural Computing.

[5] A. Shukla, M. Erementchouk, and P. Mazumder, “Non-binary dynamical Ising machines for combinatorial optimization,” Dec. 11, 2024, arXiv: arXiv:2412.08481. doi: 10.48550/arXiv.2412.08481, under review in Physica D: Nonlinear Phenomena.

[6] A. Shukla, M. Erementchouk, and P. Mazumder, “Scalable self-rounding dynamical Ising machine for combinatorial optimization on FPGA,” under review in IEEE Transactions on Computers.