What Is Digital Annealer, and How Does It Solve Combinatorial Optimization Problems with the Annealing Method?

This article explains what combinatorial optimization problems are, how Digital Annealer can quickly solve such problems, how its programs are coded, and how it differs from other annealing solutions. Reported from Fujitsu Forum 2018 seminar.

Going Beyond the Limits of Moore's Law? A Completely New Computing Architecture

Classical computer technology has progressed in accordance with Moore's Law, but this progress has already reached its limit. To solve this problem, expectations are centered on next-generation computing technologies, such as quantum computers and neuromorphic computers. However, it is said that it will take more time before such technologies can be put into practical use.

To fill this gap, Fujitsu Laboratories Limited has developed Digital Annealer, which uses a digital circuit design inspired by quantum phenomena. Digital Annealer is a new computer architecture that focuses on rapidly solving combinatorial optimization problems. It can solve difficult problems within several seconds that take classical computers a considerable amount of time to process. Problems that were previously processed by a nightly batch job, as well as other problems that were impossible to solve with classical computers, can be solved in near real-time.

Combinatorial optimization problems are used to find the best combination from among multiple choices by evaluating the results of the possible combinations. With a large quantity of combinations, it takes an enormous amount of time for classical computers to solve these problems with their brute-force approach.

One of the most well-known examples of this type of problem is the traveling salesman problem: "When a salesperson must visit several cities and then return to the original city, which order of visits minimizes the salesperson's total traveling distance?" If the number of cities is 5, there are 120 combinations. However, if the number of cities is30, the number of combinations jumps to 10 quadrillon×10 quadrillon.

Here is another example. Suppose you have received a gift voucher worth 100 dollars. The voucher can be used for a dinner for two people under the condition that you cannot receive change. You want to maximize the voucher value. So, what should you order? If the dinner has 5 courses, and for each course you can select from 4 choices, there are 1,024 (4 x 4 x 4 x 4 x 4) combinations per person. For two people, there are 1,024 x 1,024 combinations. Next, if each person can select 1 or 2 choices for each course, the number of combinations becomes very large.

In the real world, there are various combinatorial optimization problems related to financial investment portfolios, drug discovery, logistics, and others. Digital Annealer meets the social needs specific to combinatorial optimization problems where various types of combinations are dealt with.

Principles of Digital Annealer as Well as Software Development Based on the Formulation and Creation of Evaluation Formulas

The name Digital Annealer is derived from the physical phenomenon in metal processing known as "annealing." Annealing is a process of heating steel and cooling it slowly to allow it to stabilize. It may be easier to imagine how transparent ice is made by boiling water and then cooling it slowly.

In combinatorial optimization problems, annealing changes the parameters and obtains the most stable solution as the optimal answer at the end of the anneal. Digital Annealer derives the most stable solution by using a formula and then changing the parameters.

The conventional brute-force approach of classical computing requires an enormous amount of computational time. If a person takes a guess, a rough solution may be derived. However, whether it is truly the optimal solution depends on his or her level of experience; the person may miss the optimal solution. Since Digital Annealer sees the whole picture but prioritizes its guess, the possibility of missing the optimal solution is extremely low.

Developing application software for Digital Annealer consists of several steps. First, determine the issue to solve. It is best to choose a problem that was previously impossible to solve due to the enormous number of combinations involved in complicated decision-making, or a problem that takes a considerable number of man-hours to solve.

Next, find out how the issue is currently being handled and set a goal to make improvements to the extent that a business advantage can be obtained compared to the current state. This completes the problem preparation phase.

Then, consider whether the prepared issue can be solved by the combinatorial optimization technique. Basically, identify the options and then apply them to a problem that can be solved by combining such options. Next, list up the constraints and determine the evaluation method. This enables the evaluation method to be formulated as a mathematical expression. In Digital Annealer, writing such a mathematical expression corresponds to coding.

For example, when formulating the "multi-course dinner of your choice" problem, all options (menu items) are expressed as 1-bit variables. Then, the constraints are expressed in the form of a relational expression of variables. Since the constraints are incorporated into the evaluation formula, the smaller this quadratic equation, the better the value. These constraints are weighted and added to the evaluation formula. Coding, then, means to form a mathematical expression for this purpose. When the mathematical expression is given to Digital Annealer, it finds the combination of variables that create the smallest evaluation formula.

Inside Digital Annealer, all variables are changed randomly. Doing so improves or worsens the evaluation formula. You cannot obtain the optimal solution if you change the variables only to make the evaluation better. Therefore, you must first allow the variables to change in a way that makes the evaluation worse, and then lower the probability of making it worse so as to eventually find the optimal value. In this way, it becomes possible to obtain the optimal solution quickly while changing all the variables.

Digital Annealer Can Solve Difficult Problems at a Practical Level

Now, let us compare Digital Annealer to other annealing systems in terms of features and how it is provided from the viewpoint of practical use. First, we will consider the implementation technology, or the physical principle that works within the circuit. Since Digital Annealer is made up of digital circuits, it can be operated without specialized equipment. Another type of annealing system from "A Inc." uses quantum effects enabled by a superconducting circuit, which means that it must be cooled to near absolute zero. By contrast, the annealing system from "B Inc." employs the principle of optical parametric oscillation and uses a looped 1-km optical fiber. Light is oscillated in the fiber about 1,000 times to stabilize it and consequently find a solution; because of this, B Inc.'s system is inevitably large.

Next, we will examine the bit count and connection count. The bit count is roughly the number of options that can be handled, while the connection count indicates how many combinations of options are available. Digital Annealer has a fully connected 1,024-bit structure. A Inc.'s system uses 2,048 bits, but it can only connect up to 6 bits at a time because it employs superconducting circuits. If more than 6 bits are needed, A Inc.'s system can connect and additional 5 bits to each of the connected 6 bits by using them as dummies to make a 30-bit connection. However, using a dummy reduces the number of bits available for evaluation, resulting in the equivalent of a fully connected 64-bit structure.

By contrast, Digital Annealer has a fully connected 1,024-bit structure. This means that Digital Annealer can find the optimal route for 32 cities in the aforementioned traveling salesman problem. With A Inc.'s fully connected 64-bit structure, the optimal route for only 8 cities can be found. With regard to evaluation accuracy, or how many bits can be used to express the aforementioned evaluation formula, Digital Annealer can express a 16-bit, 65,536-gradation formula. However, A Inc.'s system can express only a 5-bit, 32-gradation formula. In the traveling salesman problem, A Inc.'s system can represent only 32 different distances between cities. B Inc.'s system provides only 3 gradations—they can evaluate with only 1, 0, or -1—so at present, B Inc.'s system cannot be applied to the traveling salesman problem.
Thus, Digital Annealer is the best option to tackle the challenges posed by difficult problems in the real world.

Digital Annealer Services and Future Milestones

After the release of Digital Annealer on May 15, 2018, Fujitsu launched both a cloud service and a technical service for Digital Annealer.
As part of this cloud service, Fujitsu provides Digital Annealer on which middleware to operate evaluation formulas has been installed. This is done in collaboration with 1QBit from Canada, the top vendor in the area of quantum computing software. With the cloud service, you can obtain a solution merely by entering an evaluation formula. Our technical service supports customers in solving issues throughout all phases of formulation, proof of concept, application construction, and maintenance based on our knowledge and 1QBit's expertise.

As for milestones in Digital Annealer research and development, we plan to release the second generation scaled up to 8,192 bits and with accuracy of up to 64 bits within fiscal 2018. With the second generation of Digital Annealer, it will be possible to change whether to prioritize scale or accuracy depending on the problem to which the system will be applied. In addition, we aim to achieve 1 million bits in large-scale parallel processing in fiscal 2019.