- Shu Tanaka, Assistant Professor (November, 2015)
Inauguration of Joint Research with Industry
In November 2015, Waseda University and Recruit Communications Co., Ltd. inaugurated a joint research initiative to develop a data analysis method that uses quantum annealing. This is an attempt to use quantum annealing to optimize marketing effectiveness. Once realized, it will mark the start of industrial applications of quantum annealing. In this joint research, I am working on developing the theory which will serve as the core of the technology. Now, what is quantum annealing, and what will it make possible?
Finding the Best from a Huge Set of Choices
In our daily lives, it is not uncommon for us to face situations where we want to know what the best choice is. For example, when you go somewhere, you may want to know the cheapest or fastest route, or when you work, you may consider the shortest way to do it. Finding the best answer from a huge set of choices in situations like these is called the “combinatorial optimization problem.” We see these kinds of problems not only in our daily lives, but in various other situations as well. For example, combinatorial optimization problems are hidden in important industrial tasks, such as goods delivery scheduling, work procedures in a factory, and the design of integrated circuits. If we can develop a method to quickly solve combinatorial optimization problems, it will address the industrial needs to improve efficiency and reduce costs.
It is in fact very difficult to find answers to combinatorial optimization problems. Let’s look at questions with two possible answers as an example (Figure 1). Suppose that you want to answer all the questions correctly, or to find a set of answers with the optimum score from all possible combinations of candidates. When it is one question, the number of possible combinations is only two. Even when there are two questions, it is not difficult to find all the correct answers because the number of possible combinations is four. Now, what if the number of questions were further increased to 50? Then, the number of possible combinations becomes 250(approximately 10 trillion). In this case, using a state-of-the-art supercomputer to calculate and find all the correct answers from all possible combinations takes one-tenth of a second. You may think that this is not so difficult, but if we doubled the number of questions to 100, it would take 10 million years for a supercomputer to calculate. As you can see, finding the best from a huge set of choices is very difficult problem. Actually, the scale of combinatorial optimization problems we face is just like this, or even much larger. This drastic increase of the number of candidates with the growing scale of a combinatorial optimization problem is called “combinatorial explosion.” The difficulty of combinatorial optimization problems comes from this combinatorial explosion.
Figure 1: Increase in the number of possible combinations associated with an increasing number of questions with two possible answers, and the time required for a supercomputer to find answers with the optimum score from all possible combinations (Courtesy of Assistant Professor Shu Tanaka)
Information Processing Method Simulating Physical Phenomena
The practice of applying the ideas of theoretical physics in information processing has long been known. One of these applications is a method called “simulated annealing.” Annealing is a process used to produce metal alloys where materials are heated to a high temperature and then cooled slowly. When metal is heated to a high temperature, strong atomic motion is induced by thermal fluctuation, and the atoms are dispersed. After that, if it is cooled slowly, the atoms settle into the most stable state (the optimum state) and a strong alloy is formed. In fact, combinatorial optimization problems can be replaced by a sort of physics model, which is called the “Ising model.” With this replacement, the solution to combinatorial optimization problems corresponds to the optimum state of the Ising model. There have been over 30 years of active attempts to solve combinatorial optimization problems by simulating this principle on computers. This is “simulated annealing.”
“Quantum Annealing,” an Innovative Information Processing Method Originating in Japan
The simulated annealing is a calculation method to solve combinatorial optimization problems spontaneously by slowly decreasing the temperature after creating a random state with thermal fluctuations. Here, “fluctuations” is the key word. As a matter of fact, another notable fluctuation exists in nature: quantum fluctuation. Quantum annealing was proposed as a method to solve combinatorial optimization problems spontaneously by introducing quantum fluctuations and then slowly reducing them. In 1998, pioneering research on the subject was led by Professor Hidetoshi Nishimori at the Tokyo Institute of Technology, and Dr. Tadashi Kadowaki, who was then a Ph.D. student. Since then, various studies have suggested that the quantum annealing may allow us to reach better solutions in a shorter period of time than the simulated annealing.
Figure 2 shows this concept using questions with two possible answers. When huge quantum fluctuation is applied, all possible answers are superpositioned. “Superpositioned condition” means that while the answer to each question may be A, at the same time, it may also be B. Quantum fluctuation shows this degree of superposition. It is the mechanism to obtain solutions by slowly reducing the degree of superposition.
Figure 2: Illustration of obtaining the solution with the quantum annealing (Courtesy of Assistant Professor Shu Tanaka)
Quantum Annealing Research Entering a New Stage
The quantum annealing is a calculation method that is expected to solve combinatorial optimization problems at a high speed. I am planning to apply the quantum annealing to the clustering (Figure 3). “Clustering” means classifying a huge set of data into groups according to inherent meanings. Merely storing data is useless, but classifying it by meaning is important. I expect the quantum annealing to lead to better data classification in a shorter period of time.
My motivation to study quantum annealing dates back to when I was a member of the research group of Professor Hidetoshi Nishimori (Tokyo Institute of Technology), which involved in research about applying statistical mechanics to information science. Statistical mechanics is a field of physics that handles the movement of each atom or molecule in statistical manner in order to understand macroscopic natural phenomena. It was very new for me to apply statistical mechanics to information science, because I had long thought that physics was a study to explain only natural phenomena. When I was a member of Professor Nishimori’s group, I had no knowledge of the quantum annealing. However, near the end of my Ph. D program, in Professor Seiji Miyashita’s group (The University of Tokyo), I became fully involved in the study of the quantum annealing with Professor Miyashita, Professor Hiroshi Nakagawa (The University of Tokyo), Dr. Kenichi Kurihara, who was then an information science graduate student at Tokyo Institute of Technology, and Dr. Issei Sato, who was also then an information science graduate student at the University of Tokyo.
Several years later, in 2011, a Canadian company released a dedicated device for quantum annealing called “D-Wave,” which was billed as the world’s first commercial quantum computer. This is the device that actually realizes the quantum annealing as a physical phenomenon. The quantum annealing has drawn much attention thanks to the release of this device. But the birth of the quantum annealing device does not mean the end of the study on the quantum annealing. I suppose that there are still a lot of challenges in the quantum annealing. They can be summarized into three areas: finding killer applications for quantum annealing, examining types of problems in which capacity of the quantum annealing can be fully brought out, and developing information processing devices based on the Ising model, such as the quantum annealing. I have been continuing my research efforts to address these enormous challenges step by step. One example of these efforts is the joint research with industry mentioned at the beginning of this article. I am also working on several books for the wider recognition of quantum annealing.
Figure 3: Clustering by using quantum annealing (Courtesy of Assistant Professor Shu Tanaka)
Interview and Composition: Akiko Ikeda
In cooperation with: Waseda University Graduate School of Political Science J-School
