Japanese researchers advance combinatorial problem solving
Some tasks cannot be solved easily on classical computers. Quantum mechanics offers one approach, but an Ising machine tackles the problem differently
Researchers from the Department of Electrical Engineering at Tokyo University of Science in Japan have developed what “a novel approach” to combinatorial optimisation problems (COPs).
COPs are computationally difficult problems to solve, such as shift scheduling, traffic routing and drug development, which often means they cannot be solved in a realistic timeframe.
While there has been plenty of discussion on the progress being made in quantum computing, which holds out the promise of solving such problems by taking advantage of the unique nature of quantum mechanics, there is another approach being investigated called an Ising machine.
Named after physicists Ernst Ising and Wilhelm Lenz, an Ising machine is custom hardware designed to solve COPs, where data used in the problem is presented as magnetic spins and constraints are modelled as interactions between spins. Solving a COP requires finding the spin state that minimises the energy of the system.
There are two types of Ising models: the sparsely coupled model and the fully coupled model. Sparsely coupled models offer high scalability by allowing more spins but require COPs to be transformed to fit the model. Fully coupled models enable any COP to be mapped directly without transformation, but they offer limited capacity in terms of number of spins and lower precision, as measured by interaction bit width.
According to the researchers, while previous studies have implemented fully Ising models using a scalable structure that can increase the capacity using application-specific integrated circuits (ASICs), their interaction bit-width is fixed, making certain COPs difficult to solve.
The research team from Japan, led by professor Takayuki Kawahara, developed an “innovative” dual scalable annealing processing system (DSAPS), which can “simultaneously scale both capacity and precision using the same scalable structure”.
Annealing processors are specialised hardware built to solve COPs. The team at Tokyo University of Science demonstrated that the DSAPS system enabled multiple large scale integrated circuits (LSIs) to be controlled using a single field programmable gate array chip (FPGA).
The research, said the study, marks a significant step forward for the development of scalable, high-precision, fully coupled Ising machines, with promising applications in various fields
Kawahara said: “This system will prove crucial in developing scalable APs for solving complex real-world COPs.”
Earlier this year, researchers at the University of Gothenburg demonstrated a 50-spin Ising machine using a technique known as surface acoustic wave delay line built using off-the-shelf microwave components.
At the time, the researchers stated that the technique they used demonstrates an approach to building energy-efficient and high-performance platforms for commercially feasible combinatorial optimisation solvers.
There is plenty of research investigating different ways to harness Ising machines. But, unlike the von Neumann architecture that forms the basis of digital computers, there are a number of approaches being investigated, which is also the case in quantum computing, meaning that there is no one clear winner. However, what seems to be common is that the focus for Ising machines is on energy efficiency and building these systems using established chip manufacturing processes.
