FUJITSU LABS. Project:
Title: Resolving real-world issues by “Digital Annealer”
Sponsor: Fujitsu Laboratories Ltd.
Fujitsu Laboratories was established in 1968 as an organization independent from Fujitsu for
conducting the world's top-level technological development in a free atmosphere for researchers.
Fujitsu is the leading Japanese information and communication technology (ICT) company, offering
a full range of technology products, solutions and services. We have produced a lot of innovative
results through IT and have been leading the world by providing new values to the people, societyand businesses. Fujitsu is the world's 7th largest IT services provider and No.1 in Japan.
Industry Mentors:
Masato Wakamura, Ph.D., Fujitsu Laboratories Ltd. Expert,
Makoto Nakamura, Ph.D., Fujitsu Laboratories Ltd.
Introduction:
Digital Annealer (DA) http://www.fujitsu.com/global/digitalannealer/ is a new technology to solve
large-scale combinatorial optimization problems instantly. It uses a digital circuit design inspired byquantum phenomena and can solve problems that are tough for classical computers to deal with.
Many real-world social issues such as environmental problems, can be regarded as combinatorial
optimization problems. The objective of this project is to solve a serious societal issue using DA.
Technical Background:
Quantum computing technologies are categorized into two types. One is quantum gate computer,and the other is Ising machine [1, 2]. Quantum gate computers are for universal computing,whereas Ising machines are specialized in searching for solutions of combinatorial optimization
problems.
Moreover, there are two types of Ising machines. One is the quantum annealing machine and theother is the simulated annealing machine. The quantum annealing machine searches solutions byusing quantum bits which are made of quantum devices such as a superconducting circuit. The
simulated annealing machine uses a digital circuit. DA is a type of simulated annealing machineswith a new digital circuit architecture that is designed to solve combinatorial optimization problemsefficiently. The number of bits (node) of an annealing machine is closely related to the number ofcombination parameters. Annealing machines with large number of bits (nodes) can solve largescale combinatorial optimization problems.
Many of the world’s social issues can be treated as combinatorial optimization problems that cannot
be easily solved by conventional computers when the problem size increases. The applicable fields
are chemistry, finance, transportation etc. DA uses the MCMC (Markov chain Monte Carlo) method[3] and the SA (Simulated Annealing) method [4, 5] to solve an Ising model [6-9] to which a
combinatorial optimization problem is converted. This conversion technique is very important tosolve problems at high speed.
The general procedure to solve problems by DA is shown as follows.
1) Problem description2) Formulation to combinatorial optimization problem
3) Re-formulation to Ising model4) Conversion into QUBO (Quadratic unconstrained binary optimization)5) Calculation of optimal solution by DAFujitsu has launched a DA cloud service in May 2018. The first generation has 1024 bits, all ofwhich are fully connected with 16-bit precision. Although some problems can be handled within thisbit size, many of the real-world problems need a larger bit scale. We have developed the second
generation service of DA using DAU (Digital Annealer Unit) which has an 8K bit scale. By making
both hardware and software enhancements, DA can deal with problems on a scale of 100K bits.
Expectations:
The main aim of this project is to find concrete formulations and efficient algorithms fitted to DA
and ultimately find optimal solutions for the combinatorial optimization problems. Students willobtain an experience of thinking about solving social issues in the real world, and observe thatmany of real-world problems are regarded as combinatorial optimization problems. The projectfocuses on flow optimization problems among a wide variety of combinatorial optimization problems.
Examples of flow optimization problems are as follows:
1) Route optimization for avoiding traffic congestion:
Reduce overall travel time by assigning different routes throughout the city or the entire
factory.
2) Optimization of work flow line in a factory to improve productivity:
Up to a 45% reduction in moving distances in a warehouse was achieved by Fujitsu IT
Products http://www.fujitsu.com/global/digitalannealer/case-studies/201804-fjit/Students can select one of these examples and try to find new formulations, or find a new societal
problem. Students are expected to look into the problem scale that can be calculated with DA andthe combination scales of real problems. It is also expected that the students try to devise a methodof obtaining an accurate calculation result. Fujitsu will provide user accounts and computational
environments of the new DA machine to the member of this project during the period of GRIPSSendai 2019.
Software Packages and Special Requirements:Programming (mandatory: Python, optional: C)
Recommended Reading and References:[1] P. W. Shor, "Algorithms for Quantum Computation: Discrete Logarithms and Factoring,"

Proceedings, 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM,
November 20–22, 1994, IEEE Computer Society Press, pp. 124–134.
[2] P. Bunyk, et al., "Architectural Considerations in the Design of a Superconducting Quantum
Annealing Processor, " IEEE Trans. Applied Superconductivity, VOL. 24, NO. 4, 2014.
[3] N. Metropolis, et al., "Equation of State Calculations by Fast Computing Machines," J. Chem.
Phys. 21, 1087 (1953).
[4] S. Kirkpatrick, et al., "Optimization by Simulated Annealing," Science vol. 220, No.4598, pp.671–680 (1983).
[5] S. Geman and D. Geman, "Stochastic Relaxation, Gibbs Distributions, and the Bayesian
Restoration of Images," IEEE Trans. on Pattern Analysis and Machine Intelligence, PAMI-6,
pp.721-741, 1984.
[6] Hopfield, J.J.: Neural networks and physical systems with emergent collective computationalabilities. Proc. Natl. Acad. Sci. 79, 2254–2558 (1982).
[7] Aarts, Emile H.L., Korst, Jan H.M.: Boltzmann machines and their applications. In: Bakker, J.W.,
Nijman, A.J., Treleaven, P.C. (eds.) PARLE 1987. LNCS, vol. 258, pp. 34–50. Springer,Heidelberg (1987).
[8] Skubiszewski, M.: An exact hardware implementation of the Boltzmann machine. In:
Proceedings of the Fourth IEEE Symposium on Parallel and Distributed Processing, pp. 107–110 (1992).
[9] Yamaoka, M., et al.: 20 k-spin Ising Chip for Combinational Optimization Problem with CMOS
Annealing. ISSCC 2015 digest of technical papers, pp. 1–3, February 2015.