Multi-spin flips and a pathway to efficient ising machines

In a rapidly developing world, industries are always trying to optimize their operations and resources. Combinatorial optimization using an Ising machine helps solve certain operational problems, like mapping the most efficient route for a multi-city tour or optimizing delivery of resources. Ising machines operate by mapping the solution space to a spin configuration space and solving the associated spin problem instead. These machines have a wide range of applications in both academia and industry, tackling problems in machine learning, material design, portfolio optimization, logistics, and drug discovery. For larger problems, however, it is still difficult to obtain the optimal solution in a feasible amount of time.

Now, while Ising machines can be optimized by integrating multi-spin flips into their hardware, this is a challenging task because it essentially means completely overhauling the software of traditional Ising machines by changing their basic operation. But a team of researchers from the Department of Computer Science and Communications Engineering, Waseda University—consisting of Assistant Professor Tatsuhiko Shirai and Professor Nozomu Togawa—has provided a novel solution to this long-standing problem.

In their paper, which was published in IEEE Transactions on Computers on 27 May 2022, they engineered a feasible multi-spin flip algorithm by deforming the Hamiltonian (which is an energy function of the Ising model). “We have developed a hybrid algorithm that takes an infeasible multi-spin flip and expresses it in the form of a feasible single-spin flip instead. This algorithm is proposed along with our merge process, in which the original Hamiltonian of a difficult combinatorial problem is deformed into a new Hamiltonian, a problem that the hardware of a traditional Ising machine can easily solve,” explains Tatsuhiko Shirai.

The newly-developed hybrid Ising processes are fully compatible with current methods and hardware, reducing the challenges to their widespread application. “We applied the hybrid merge process to several common examples of difficult combinatorial optimization problems. Our algorithm shows superior performance in all instances. It reduces residual energy and reaches more optimal results in shorter time—it really is a win-win,” states Nozomu Togawa.

Their work will allow industries to solve new complex optimization problems and help tackle climate change-related issues such as increased energy demand, food shortage, and the realization of sustainable development goals (SDGs). “For example, we could use this to optimize shipping and delivery planning problems in industries to increase their efficiency while reducing carbon dioxide emissions,” Tatsuhiko Shirai adds.

This new technology directly increases the number of applications where the Ising machine can be feasibly used to produce solutions. As a result, the Ising machine method can be increasingly used across machine learning and optimization science. The team’s technology not only improves the performance of existing Ising machines, but also provides a blueprint to the development of new Ising machine architectures in the near future. With the merge algorithm driving Ising machines further into new uncharted territories, the future of optimization, and thus sustainability practices, looks bright.

***

Reference

DOI: https://doi.org/10.1109/TC.2022.3178325

Authors: Tatsuhiko Shirai and Nozomu Togawa

Affiliations: Department of Computer Science and Communications Engineering, Waseda University

About Waseda University

Located in the heart of Tokyo, Waseda University is a leading private research university that has long been dedicated to academic excellence, innovative research, and civic engagement at both the local and global levels since 1882. The University ranks number one in Japan in international activities, including the number of international students, with the broadest range of degree programs fully taught in English. To learn more about Waseda University, visit https://www.waseda.jp/top/en