With a list of cities and the distances between each pair of cities, how do you decide the shortest route to visit each city just once and return to the starting point? This well-known problem is called the “travel vendor problem” and is an example of a combinatorial optimization problem. Solving these problems using conventional computers can take a long time, and special devices called “quantum annealers” have been created for this purpose.
Quantum annealers are designed to detect the lowest energy state (or “ground state”) known as the “Ising model.” Such models are abstract representations of a quantum mechanical system that incorporates interactive spins that are also influenced by external magnetic fields. In the late 90s, scientists discovered that combinatorial optimization problems could be compounded as Ising models, which could physically apply themselves in quantum annealers. To solve the problem of combinatorial optimization, one needs to monitor the condition of the ground reached in the associated quantum annealer after a short time.
One of the biggest challenges in this process is the transformation of the “logical” Ising model into a physically implementable Ising model suitable for quantum erosion. At times, the numerical values of the spin interactions or the external magnetic fields require several pulses to represent them (bit width) too large for a physical system. This severely limits the flexibility and suitability of quantum annealers to real-world problems. Fortunately, in a recent study published in IEEE functions on computers, Japanese scientists have addressed this issue. Based solely on mathematical theory, they developed a way in which a logical Ising model can be transformed into a uniform model with a bit width that you want to make it “appropriate” as the physical performance you want.
Their approach involves adding supporting spins to the Ising module for problem interactions or magnetic fields in such a way that the ground state (solution) of the model is transformed into the same as the original model and at the same time requiring a lower width. The method is relatively simple and completely sure to create an identical Ising model with the same solution as the original one. “Our strategy is the first in the world to effectively and theoretically address the problem of bit width reduction in the spinning interactions and magnetic field coefficients in Ising models, “said Professor Nozomu Togawa of Waseda University, Japan, who led the study.
The scientists also tested their method in several experiments, which further proved its validity. Professor Togawa has high expectations, and concludes by saying, “The approach developed in this study will expand the relevance of quantum annealers and make them much more attractive to those dealing with not only Ising physical models but all sorts of combinatorial optimization problems. Such problems are common in cryptography, logistics, and artificial intelligence, among many other fields. ”
###
Information
Authors: Daisuke Oku (1), Masashi Tawada (1), Shu Tanaka (2,3), and Nozomu Togawa (1)
Original Paper Title: How to Reduce Ising Model Width by Adding Auxiliary Spins
Iris: IEEE Trans. Computers
DOI: 10.1109 / TC.2020.3045112
Relationship:
(1) Department of Computer Science and Communication Engineering, Waseda University
(2) Green Computer Systems Research Group, Waseda University
(3) Foresight Research for Embryonic Science and Technology
About Waseda University
Located in the heart of Tokyo, Waseda University is a leading private research university that has recently been dedicated to academic excellence, innovative research, and civic engagement at local and global levels since 1882. It is Japan’s number one university in international activities, including the number of international students, with the widest range of fully taught degree programs in English. To learn more about Waseda University, visit https: /
Disclaimer: AAAS and EurekAlert! they are not responsible for the accuracy of press releases posted to EurekAlert! by sending institutions or for using any information through the EurekAlert system.