Combinatorial optimization problems are often part of the problems in various fields. However, due to the huge number of combinations, conventional computers cannot solve the problems within a practical time. Therefore, quantum computers that can solve combinatorial optimization problems at high speed are attracting attention. However, the current quantum computers are too small in scale to solve complex practical problems and are not stable to use in business. It is supposed that at least some years are needed to solve these issues and to be applicable to various kinds of actual problems in the real world.

Taking account of such a situation, the award-recipients have developed an innovative computer architecture “Digital Annealer” that specialized in solving combinatorial optimization problems using quantum-phenomenon-inspired methods implemented onto current stable digital circuits [1-5].

The Digital Annealer solves combinatorial optimization problems at a high speed, where the problem could not be solved by conventional computers within a practical time. The Digital Annealer is composed of a conventional computer and specialized digital circuits that perform “annealing” inspired by quantum phenomena. There is a quantum phenomenon where state-0 and state-1 exist simultaneously, called “superposition”. The Digital Annealer emulates this phenomenon by fluctuation between “0” and “1” using randomly generated numbers. The solution search is performed while inverting the bits in the direction in which the evaluation value (energy) decreases. However, the one-direction-transition may be trapped in the local minimum where the evaluation value does not improve any more. In the Digital Annealer, escapes from the local minimum are achieved by allowing a probabilistic transition in the opposite direction (value increase). The high-speed solving of The Digital Annealer is realized by the parallel operation of such stochastic transitions that like quantum computers (Fig.1). The technique to escape from the local minimum described above contributes to speeding-up the solving operation (Fig. 2).

The Digital Annealer consists of the dedicated hardware (conventional computer and dedicated circuits) and the control software. The first generation of The Digital Annealer started as a cloud service in May 2018. At this time, the number of variables (each variable is 1-bit-wide) were 1,024 when the formulation was examined. Here, the formulation means the translation of an actual problem onto a mathematical problem. The second generation launched in Dec. 2018. At that time, the number of variables had been extended to 8,192. This second-generation Digital Annealer and associated technologies achieve the solving of various kinds of actual combinatorial optimization problems.

Practical use cases:

Case 1: Financial (https://www.fujitsu.com/us/about/resources/case-studies/cs-2020apr-melco.html)

Fujitsu Limited and MELCO Investments Inc. have successfully generated low-risk-optimized stock portfolios. Conventionally, to obtain an optimal portfolio consisting of several hundred stocks is impossible because of the enormous computational volume. The Digital Annealer performs such calculations within about 10 minutes. This performance has made the Digital Annealer applicable in the actual asset management business.

Case 2: Logistics (https://www.fujitsu.com/global/about/resources/news/press-releases/2020/0910-02.html)

Fujitsu Limited and Toyota Systems Corporation have successfully demonstrated the optimization of supply chain and logistics network operations essential to support automobile production in a joint trial. The problem is purchasing parts from more than several hundred suppliers, going through some number of relay warehouses, and delivery to dozens of factories. The candidate routes are about 3 million. Conventionally, this route optimization required 2 months with 30 people. On the other hand, The Digital Annealer successfully solved this problem in only 30 minutes.

Case 3: Drug discovery (https://www.fujitsu.com/global/about/resources/news/press-releases/2020/1013-01.html)

Fujitsu Limited and PeptiDream Inc. have succeeded in identifying, based on in-silico exploration, stable conformations of a cyclic peptide drug candidate within a 12-hour period. This represents a milestone achieved by utilizing high-performance computing and the Digital Annealer. This technology advancement has the potential to shorten the amount of time needed to identify candidate compounds in the drug discovery process and reduce the need for certain time-consuming "wet" lab experiments.

As described above, the award-recipients have established a new computer architecture called “The Digital Annealer”, and have solved various real problems using this technology and have contributed to the commercialization of this technology.

In summary, the advances led by the award recipients are remarkably distinguished and highly worthy of the Achievement Award.

References

1. S. Matsubara, M. Takatsu, T. Miyazawa, T. Shibasaki, Y. Watanabe, K. Takemoto, and H. Tamura, “Digital Annealer for High-Speed Solving of Combinatorial Optimization Problems and Its Applications,” The 25th Asia and South Pacific Design Automation Conference, No.9C-2, pp.667-672, Beijing, China, Jan. 2020.
2. S, Matsubara, H. Tamura, M. Takatsu, D. Yoo, B. Vatankhahghadim, H. Yamasaki, T.Miyazawa, S. Tsukamoto, Y. Watanabe, K. Takemoto, and A. Sheikholeslami, “Ising-Model Optimizer with Parallel-Trial Bit Sieve Engine,” Conference on Complex, Intelligent, and Software Intensive Systems (CISIS) 2017, pp.432-438.
3. H. Tamura, S. Matsubara, T. Ahmed, M. Takatsu, D. Yoo, B. Vatankhahghadim, H. Yamasaki, T. Miyazawa, S. Tsukamoto, Y. Watanabe, K. Takemoto, Y. Koyanagi and A. Sheikholeslami, “An Architecture for Parallel-Trial Hardware Accelerator for Ising-Model MCMC Simulations,” Adiabatic Quantum Computing Conference 2017.
4. H. Tamura, T. Miyazawa, J. Koyama, N. Yoneoka, S. Matsubara, M. Takatsu, Y. Liu, T. Shibasaki, S. Tsukamoto, Y. Watanabe, K. Takemoto, Y. Koyanagi, T. Horie, T. Urushidani, T. Ozaki, M. Sumida, A. Sheikholeslami and K. Hukushima, “Digital Annealer: An Accelerator for Markov-Chain Monte Carlo Stochastic Search with Multi-Replica Processing,” Adiabatic Quantum Computing Conference 2018.
5. T. Miyazawa, N. Yoneoka, S. Matsubara, Y. Liu, T. Shibasaki, K. Takemoto, Y. Koyanagi, H. Tamura, T. Ozaki, T. Urushidani, M. Aramon and H. G. Katzgraber, “Stochastic search using Digital Annealer technology,” Adiabatic Quantum Computing Conference 2018.