NTT technical review

A Computing System for Supporting Application Development Using Ising Machines

Kazuhiro Miyahara, Junji Teramoto

Published Nov 1, 2023• 1 citation

Abstract

One of the problems that conventional computers, such as those based on central processing units, cannot solve is the combinatorial optimization problem, the solution to which is a pattern from among a huge number of combinations of patterns that satisfies a certain condition.Operating on the basis of a new principle, an Ising machine is a computer that specializes in solving this problem.However, there are many challenges to using an Ising machine, such as converting real-world problems into a format that the Ising machine can handle.Research and development of a software development kit and computing system that overcome these challenges are introduced in this article.

DOI: 10.53829/ntr202311fa2

Related papers

Theory of Ising Machines and a Common Software Platform for Ising Machines

Shu Tanaka, Yoshiki Matsuda, Nozomu Togawa

Ising machines are a new type of non-Neumann computer that specializes in solving combinatorial optimization problems efficiently. The input form of Ising machines is the energy function of the Ising model or quadratic unconstrained binary optimization form, and Ising machines operate to search for a condition to minimize the energy function. We describe the theory of Ising machines and the present status of the Ising machines, software for Ising machines, and applications using Ising machines.

Asia and South Pacific Design Automation Conference (ASP-DAC)Jan 1, 202017 citations

古典計算機とイジングマシンを併⽤した組合せ最適化問題ハイブリッド求解システム

Keisuke Fukada, 佳佑深⽥

A combinatorial optimization problem is a problem finding a combination of variables that optimizes an objective function while satisfying its given constraints.For solving the problem, Ising machines have gained attention as a prominent architecture.However, due to limited computational resources, using only Ising machines may not be able to obtain quasi-optimal solutions.This dissertation proposes two state-of-the-art methods that hybridly utilize an Ising machine and a classical computer.These methods are applicable to various combinatorial optimization problems and can effectively achieve quasi-optimal solutions.Experimental results demonstrated that the proposed methods outperform existing approaches and achieve optimal solutions in several instances.

Jan 1, 20240 citations

Activities toward New-principle Computers

Shiro Saito, Hideki Gotoh

Non-von Neumann-type computers, such as quantum computers and Ising machines that operate on principles different from those of present-day computers, are attracting attention.They are particularly powerful when applied to specific types of problems such as combinatorial optimization problems, quantum chemical calculations, and prime factorization, and since solutions to problems such as these can have a significant impact on society, research of new-principle computers is moving forward at a vigorous pace.The following Feature Articles in this issue introduce theoretical and experimental activities regarding new-principle computers at NTT laboratories while describing recent advances in this field.

NTT technical reviewMay 1, 20212 citations

Research on Annealing Processors for Large-Scale Combinatorial Optimization Problems

佳生山本

This research is concerned with an annealing processor for efficiently solving a combinatorial optimization problem.\nIn order to realize a smart society, optimization of people and thingssuch as transportation networks, power networks, human resource allocationand routes is indispensable. Many of these problems are called combinatorial optimization problems and are known as very important problems in modern society. However, it is known that the combinatorial optimization problem is NP-hard and it is difficult to efficiently solve it with a conventional Neumann computer.\nIn recent years, the miniaturization of the process of manufacturing computer chips is approaching the physical limit. Therefore, especially in the solution by the full search, the improvement in speed due to the calculation speed of the computer cannot be expected. From such a background, dedicated hardware capable of solving a combination optimization problem at high speed and with low power consumption has been attracting attention.\nThe annealing processor is a general-purpose combination optimization solver that utilizes the property that the ground state of the optimization problem expressed by using the Ising model and the optimal solution of the combination optimization problem match. The Ising model is a ferromagnetic model in statistical physics expressed by spins having an upward and downward state, spin-spin interactions occurring between the spins, and an external magnetic field acting on each spin. The Ising model can express a combinatorial optimization problem by expressing a control target and a cost using these parameters. The annealing processor updates the spin state while slowly lowering the temperature parameters based on simulated annealing,which is an optimization method learned from natural phenomena generally called annealing. Eventually, the spin will reach the ground state with a high probability and obtain the optimal solution.\nAnnealing processors are classified into two types, the nearest neighbor type and the fully connected type, depending on the shape of the Ising model simulated on the hardware. In the nearest neighbor type, the coupling between spins is limited to only between adjacent spins, and in the full coupling type, coupling exists between arbitrary spins. The nearest neighbor type realizes high parallel processing by reducing the data spin required by simulated annealing by reducing the proximity spin. In addition, since data transfer is limited to adjacent spins, the scalability is high. However, since the spin-to-spin interaction is sparse, there is a problem that the class of combinatorial optimization problems that can be dealt with is limited, or that the problem requires deformation processing to match the Ising model of hardware. The fully connected type can solve any class of problems as long as the number of spins permits, however it requires connections between arbitrary spins.Therefore, scalability is low. Because there there is a dependency on all spins,the number of spins that can be updated at one time is always limited to only one regardless of the total number of spins. Therefore, it takes time to converge to the ground state.\nIn this research, we propose a method of increasing the number of spins for this annealing processor by using (1) a spatially-expanded time-division processing mechanism architecture based on a loosely-coupled type, (2) An algorithm for applying a fully coupled Ising network to a more complex Ising network using the nearest neighbor Ising network and an annealing method that can be updated in parallel, (3)We conducted a study on the architecture of a fully coupled annealing processor for parallel updating annealing.\nAs described above, the research described in this paper contributes to the improvement of the efficiency of the annealing processor for solving the large-scale combinatorial optimization problem from both the fundamental algorithm and the hardware architecture. I hope that this research will solve the combinatorial optimization problem that is expected to increase in demand in the future and contribute to the development of human society.

Mar 25, 20201 citation

Recent Progress of Ising Machines and Related Technology

Shu Tanaka, Yoshiki Matsuda

Ising machines are hardware that is expected to perform combinatorial optimization problems with high speed and high accuracy. In recent years, in the field of Ising machines, various studies have been conducted in each layer of hardware development, software development, and application search by both the academic side and industrial side. This manuscript explains how to use the Ising machine and introduces the current state of research and development in the field of Ising machines.

Vacuum and Surface ScienceMar 9, 20200 citations

LASOLV(TM) Computing System: Hybrid Platform for Efficient Combinatorial Optimization

Junya Arai, Satoshi Yagi, Hiroyuki Uchiyama +4 more

LASOLV TM is a computing machine developed by NTT based on photonics technologies.While we can efficiently solve combinatorial optimization problems by using LASOLV, there are technical challenges in its application to real-world problems.For example, we need to mathematically convert problems to a specific format for solving them using LASOLV.Moreover, LASOLV requires cooperation with conventional digital computers to solve complex problems.In this article, we introduce LASOLV Computing System, which is a computing platform that helps users overcome these challenges.

NTT technical reviewJan 1, 20206 citations