A Period without Direction Is a Time for Improving One’s Basic Research Abilities―Better to Change Your Perspective than Follow the Crowd

Achieving innovative research results by taking pioneering approach and attracting worldwide attention in the leader election problem

—Dr. Tani, please tell us about your current area of research.

I’m involved in the research of quantum computers (Fig. 1). Similar to conventional computers (called “classical computers” in the world of quantum computers), quantum computers consist of hardware and will not run without placing something equivalent to software on that hardware. In my work, I theoretically consider how to create that something corresponding to software (quantum algorithms), that is, how to bring out the performance of that hardware. I started out on this research path about 15 years ago.

Fig. 1. Concept of a quantum computer.

Let me point out here that a key premise in this research is that using a quantum computer to do computations will not necessarily be faster. There are many cases in which the speed of processing by a quantum computer will be about the same as that of a classical computer, depending on the type of computation. In fact, a lack of skill in creating a good quantum algorithm to run on quantum computers could result in even slower processing than classical computers.

With this issue in mind, we have established several key research themes and objectives. To begin with, we must search for problems conducive to high-speed processing on quantum computers. We must then estimate the extent to which computation can be speeded up in such cases, find quantum computer functions that are truly needed for achieving such high-speed processing, and determine how such functions should be merged with computations by classical computers.

The concept of the quantum computer was first proposed in the 1980s, but it took until 1990 or so for research to really take off. During this 30-year period, the research of quantum computers evolved significantly in terms of both hardware and algorithms. Our group as well contributed to this history through various research achievements. One of these that received considerable recognition was distributed quantum algorithms for solving the leader election problem (Fig. 2).

Fig. 2. Overview of distributed quantum algorithm for solving the leader election problem.

The research on quantum algorithms can be broadly divided into two flows. These originate respectively in Peter W. Shor’s quantum algorithm for factoring integers exponentially faster than any existing algorithm and Lov K. Grover’s quantum algorithm for searching for a desired item of data from a huge amount of data (Fig. 3). Research on the application and generalization of each of these algorithms has spanned a period of about 20 years. We developed our distributed quantum algorithm for solving the leader election problem by taking an approach different from these two flows and received praise for it as a pioneering algorithm as a result.

Fig. 3. Flow of quantum algorithm research.

In the leader election problem, a number of computers connected in a network must autonomously elect one of those computers as a single leader. This problem can be used to determine which computer among many is to perform a particular process. For cases in which the uniqueness of computer addresses is not guaranteed due to faults or other reasons, it is known that this problem cannot be solved in a finite amount of time in a network consisting of classical computers. In contrast, we devised an algorithm for efficiently solving the leader election problem in a network consisting of quantum computers and received worldwide recognition for it.

In this algorithm, multiple computers play rock-paper-scissors using the observed values of qubits (0 or 1), and the computer that survives multiple elimination rounds is determined to be the leader. Here, in the computation process, we have developed a technique to make the probability of a draw in rock-paper-scissors zero, with the result that a single leader can be elected in a finite number of rounds (in a finite amount of computation time) (Fig. 4).

Fig. 4. Idea behind solving the leader election problem.

This result was praised for theoretically showing that quantum computers are substantially different from classical computers in terms of ability, but it also has merit from the viewpoint of practical application since it can be used in the automatic setup of a quantum network consisting of quantum computers. Here, automatic setup means that multiple quantum computers need only be physically interconnected to automatically assign node addresses, automatically configure routing paths, and automatically and randomly assign management authority. This result also means that computations on input data distributed throughout the network that were not previously possible with classical computers can now be done.

—You have obtained innovative results during the long history of quantum computer research.

All theoretical researchers aim to shed light on the unknown and determine the direction of future research. I am one of those researchers. With regard to the leader election problem, I feel that I may have done my best work in that research. Thanks to those research results, I was able to give an oral presentation at a top-level international conference on quantum information science soon after the start of serious quantum computer research in Japan and to have papers published in ACM Transactions, a journal of the Association for Computing Machinery (ACM) [2]. In this sense, I believe I accomplished my initial objectives. I was also very pleased to see my research results included in ACM’s SIGACT News and in a textbook (authored by Rodney Van Meter).

Incidentally, in the research field of quantum algorithms, there are not many researchers from the preceding generation. Since quantum algorithm research commenced in the 1990s when researchers of our generation came of age, I think we can safely say that researchers of our generation and beyond have been virtual pioneers.

On stepping onto a train station platform, a solution suddenly struck me like lightning; you can’t obtain results that make an impact without pushing yourself to the max

—How did you derive the algorithm for solving the leader election problem?

When I moved to NTT Communication Science Laboratories in 2003 after working on the research and development (R&D) of network protocols at the NTT Yokosuka R&D Center, I was already of the so-called mid-level generation. Consequently, as I was not an entry-level researcher, I could not imagine myself producing zero research results in my first year or two in my new position. I knew I had to produce some results, and in doing so, I had to find something that no one else in the world was working on and that I could apply my background to. Therefore, I began to look for a theme that I could devote all my energy to. However, there were already a lot of researchers in the field of quantum computer research, and I didn’t want to just follow the crowd as a newcomer. I therefore thought about approaching this research from a completely different perspective, so I started to voraciously read papers in this field.

Moreover, thinking that I wanted to produce major, unprecedented results that would make an impact, I also reviewed textbooks covering the subjects of classical computing as well as quantum computing. As a result, after looking at major problems taken up in textbooks as opposed to minor problems appearing in obscure corners of journal papers, I came across the leader election problem. This is an essential problem that is invariably discussed in textbooks on distributed computing, but at that time, it was a network-related issue that was not being researched much in the field of quantum computers.

My research started to bear fruit in only the fourth month after deciding to take on the leader election problem. I felt very fortunate in this regard. I didn’t have any experience in the field of quantum computers, so it was like filling in the pieces of a puzzle time and time again. Moreover, there was no guarantee that that puzzle would be completed. However, I believed that I could complete the puzzle, so I would perform test calculations intensely for days on end while looking at stacks of notes on my desk. This was an interesting world in which I was doing calculations without the use of a computer to develop a theory on calculations to be performed by a computer!

In the fourth month of doing such calculations and trying to solve this puzzle without knowing when I might complete it, I finally completed the proof of a core lemma. At that moment, I could feel my heart pounding, and I only half believed what I had done. Given my desire to enter the field of quantum computer research and working hard with my whole body and soul to produce some kind of result, I was very happy about this, but on the other hand, it was all too sudden and unbelievable. On that day, I was commuting to work by car, but I cannot remember how in the world I got home.

Several months passed as I continued with my research. I had been thinking about another lemma around that time, and one day on returning from a business trip, I walked down a staircase at a train station and stepped onto a platform. At that very moment, the key to proving that lemma suddenly hit me, as if I had been struck by lightning. How can I explain this? Well, when I’m riding (getting on) a train, my objective of “moving” from one place to another is being fulfilled, so I feel a sense of ease in that I’m not wasting time, which enables me to relax. In fact, whenever I’m moving or about to move by a train or other means, things often pop into my head, and stepping onto the platform at that time was exactly such a situation.

—This theme that you found under pressure led to world-first results! This seems to say that some amount of pressure is good.

Yes, a reasonable amount of pressure can be beneficial! When starting out in their careers, researchers gain experience by solving small problems, but in the future, I think that researchers will aim for major achievements. Lots of pressure can arise in tackling a risky problem, but I think it’s something that a researcher should face even if it takes time.

Although this may sound somewhat negative, theoretical research is strenuous. Rather than progressing little by little over time, research tends to suddenly leap forward at certain points in time. When that step will be climbed is unknown, and whether it will be climbed at all is also unknown. Until that opportunity arrives, a researcher must persevere in a state in which nothing is moving. This is mentally difficult beyond what can be conveyed in words. Of course, I know from experience that other types of difficulties exist in other fields. That is to say, if there is a field in which a researcher can demonstrate his or her abilities, it should be easy to convert that pressure to ability. In my case, the joy of research supersedes any difficulties, so I was able to withstand that pressure.

Once one has produced several research achievements, I feel that one can be optimistic and say without substantiation: “Such a time will come again.” When you are young, however, it’s easy to be pessimistic in the manner of “This is really turning out bad!” In the end, you can only believe in yourself. It sometimes happens that you are getting nowhere after thinking for half a year or even a whole year, so it’s crucial that you set your own deadline without obsessing over results.

—By the way, why did you choose research as a career path?

There was a time before graduating from university when I had three months to submit my graduation thesis but I still had nothing to show in terms of results. I therefore worked frantically to squeeze out something, but on presenting my theory in our research laboratory, a senior of mine pointed out a serious error, so I then had to work like crazy for the remaining month and a half. This was quite an experience in getting out of a difficult situation. At that time, I didn’t know that the “time for climbing the stairs” comes suddenly without knowing when, so that uncertainty made for a very difficult time.

On the other hand, this experience only increased my enjoyment of theoretical research, and it occurred to me that the life of a researcher might not be bad at all. Later, on completing my master’s degree, I arrived at a crossroads where I had to decide between looking for work and continuing my education, and given my frame of mind at that time, I thought that finding work in research would be quite cool. Many of my seniors at that time were involved in research activities while working at companies, so no one thought that employment meant being separated from research. I chose NTT because I had no doubt that I would be given the opportunity to pursue basic research. In actuality, though, a major organizational restructuring took place after I entered the company, causing a major transition in the research field that I was to be involved in. However, looking back at that time in an objective manner, I see that I was initially involved in theoretical research at university, that I then gained experience in application fields including the research of integrated circuits and network protocols after entering NTT, and that I was finally given the opportunity of returning to theoretical research. In hindsight, I think that all of these experiences have helped in some way to produce my current research results.

Find pleasure in your daily research and pursue research that will still be around 100 years from now

—What advice would you give to young researchers?

Although “usefulness” should be considered when finding a research theme even in basic research, I think it is difficult to lead a research life motivated solely on what might be useful. Shouldn’t it also be important to take joy in the act of research itself? Basic research involves basic academic disciplines, and in our field, mathematics and physics in particular. Though we are not doing pure mathematics here, we do use mathematics as a technique. In fact, there are not a few researchers who enjoy the application of mathematics itself. Such pleasure is an extra benefit of research. I believe that feeling such joy in daily research can be a source of happiness for a researcher.

In addition, while going through a period without a clear-cut direction can be painful for a researcher, it’s exactly a time for devoting energy to improving your basic research abilities. It’s important to soundly accumulate those basic elements that will become your strengths in the future. As I mentioned earlier about our field being based on mathematics (in a broad sense), and with the difficulties that I experienced, I would recommend that researchers be thoroughly familiar with undergraduate mathematics at a minimum. I came to understand today that raising the level of my basic abilities is of utmost importance after going through an ongoing learning process throughout my research life. By constantly improving your basic abilities, I believe that something that was quite tough five years earlier will become something that you can do in the present!

It’s also important to occasionally get away from research. I myself enjoy sports (soccer in particular) and driving. Pursuing research at the cost of everything else can lead you to a dead end and leave you mentally exhausted. It’s rewarding to be involved in something completely different!

Also, if you have the opportunity to travel abroad, take it by all means. At the least, I would recommend that you stay for several months by yourself, and I would recommend in particular that you go to a place where postdoctoral researchers gather. I think that seeing the sparkle in their eyes will help to change your attitude toward research. I myself had the opportunity to study at the University of Waterloo in Ontario, Canada for one year starting in 2010. It was a place where top-class researchers in the field of quantum computers would gather, so being able to feel that atmosphere turned out to be a very valuable experience for me. It’s advantageous to be in an environment where you can do research in a relaxed way, but it’s also good to get out to international conferences and receive some stimuli from time to time.

—Dr. Tani, what is your outlook for the future?

The research on quantum computer hardware is advancing if only a little at a time. In these last two or three years, large amounts of research funds have been allocated to quantum computer research throughout the world, so I feel that progress in this area is speeding up. That being said, it will still take some time before an ideal quantum computer can be achieved. Till then, we can expect the creation of quantum computers with limited functions, but even at that level, the solving of important problems will be most welcome. With this level of quantum computers, which we can expect to be implemented sometime in the near future, the question as to what types of problems in particular should be targeted is becoming increasingly significant. Actually, I am now involved in searching for such problems.

In addition, in consideration of the massive amount of technology already existing for classical computers, it would certainly be better if problems that could be solved on classical computers were actually solved on classical computers. This, however, leads to another question: Where in particular should we depend on quantum computers? We are still lacking in the ability to make such decisions. This question is also of interest to me and I am working on finding an answer.

Work that is current with the times is fine, but as a researcher, I want to pursue work that will still be around in the future. In this regard, I would like to take a sweeping view of both quantum and classical computations. Considering work that will still have value not just 5 or 10 years from now but even 100 years down the road, I would like to pursue long-range themes in parallel with those that can be tackled in the short term.

References

[1]	H. Yamaguchi, “Research Frontier of Quantum Computers,” NTT Technical Review, Vol. 10, No. 9, 2012. https://www.ntt-review.jp/archive/ntttechnical.php?contents=ntr201209fa1.html
[2]	S. Tani, H. Kobayashi, and K. Matsumoto, “Exact Quantum Algorithms for the Leader Election Problem,” ACM Transactions on Computation Theory, Vol. 4, No. 1, Article 1, 2012.