- Semiconductor Technology Now

Expert Interview

# Building a CMOS Annealing Machine to Solve Combinatorial Optimization Problems

April 28, 2018

There are a few mathematical problems that conventional von Neumann computers^{*1} are ill-equipped to handle. Combinatorial optimization is a case in point. A typical example would be the traveling salesman problem, which involves finding the shortest route that a traveling salesman can take while visiting every single destination city. Quantum computers are good at solving this type of problem, but they require a large-scale refrigeration system to cool atoms to near absolute zero (-273 degrees Celsius) to ensure quantum states can be observed without being affected by lattice vibrations^{*2}. Is there any way to solve combinatorial optimization problems without using a massive refrigeration system? Hitachi’s R&D group came up with an inspired solution in the form of a CMOS device chip^{*3}. Telescope Magazine interviewed the developer of the “CMOS annealing chip” to explore the potential of this innovation.

#### Telescope Magazine: What led you to develop the novel CMOS annealing machine?

Masanao Yamaoka: With the goal of achieving a smart society, we’ve been focusing on advancing computing technology that utilizes cyberspace known as the cloud. However, remotely accessing the cloud system is often impractical, especially where instant response and real time processing are required. To overcome this obstacle, IoT devices and connecting devices on the cloud edge (such as network gateways, routers, local mobile base stations, etc.) must also be equipped with reasonable computing power. Which means that technologies that utilize both the cloud core and the edge have to be developed, as well as the means for optimizing such a system. In an urban traffic control system, for example, resolving traffic congestion requires balancing the traffic volume and the cost of mobility. By using such input parameters as the traffic conditions and the destination of each car, the optimal traffic signal operations can be determined. In fact, efficient solution of an optimization problem like this is essential in achieving a smart society.

The “traveling salesman problem” is an often-quoted example of combinatorial optimization. Given a fixed number of cities to visit, what is the most efficient route for a salesman to visit them all before coming back (Figure 1)? It’s fairly easy to solve when only a small number of cities are involved, but the calculation becomes increasingly difficult as the number of cities gets larger.

Other types of combinatorial optimization problem include minimizing the cost of supply chain logistics, and optimization of power generation volume and transmission routes to stabilize the supply of electricity. Also, a venture capital firm may want to employ this technique to choose which ventures to invest in and in what order.

The general consensus is that the long reign of Moore’s Law in the semiconductor industry is finally coming to an end, and the conventional computer architecture also appears to be reaching its limits. I felt a new approach was needed to solve this problem, and decided to develop a computer that was totally different from conventional ones.

To sum it up, I realized that combinatorial optimization problems were about to become critical, and so I chose to tackle those problems by developing a new computing method based on an unconventional architecture.

#### Telescope Magazine: That reminds me of Rebooting Computing, an American initiative to develop post-von Neumann computing models.

Masanao Yamaoka: That’s exactly the kind of thing that we are after. At the IEEE International Conference on Rebooting Computing (ICRC) held in the U.S. last November, we gave a presentation on the technology based on simulated quantum annealing (Reference 1). Our approach is in line with the efforts that are going on in the U.S. Our concept of post-von Neumann computing includes diverse architectures, such as quantum computers and AI.

#### Footnotes

- *1
- Von Neumann computer: The prevailing computer architecture of the day. It consists of a central processing unit (CPU), memory unit, and data buses. The CPU fetches instructions and data from the memory unit to control the system and perform operations.

- *2
- Lattice vibrations: At temperatures above absolute zero, molecules of all matters oscillate with thermal energy. In crystal lattice structures found in semiconductors and other matters, latticed atoms oscillate in a synchronized way, which is called a lattice vibration. The quantum state of atoms cannot be observed unless the lattice vibration is stopped.

- *3
- CMOS (complementary metal-oxide-semiconductor): A basic technology for constructing today’s large-scale integrated circuits. A CMOS device blocks electrical current when it’s in a stationary state (on or off), and only passes electricity when the state changes from on to off or off to on. At high clock speeds, the state changes very frequently and a significant amount of electricity flows through the device.