Research

Hidetoshi Nishimori - Applying quantum annealing to computers

Issue 13

ProfessorHidetoshi Nishimori

Department of Physics Graduate School of Science and Engineering

An innovative theory for designing computers capable of
possibly performing a tremendous amount of computation

"Quantum mechanics is an incredibly difficult concept to understand," Professor Hidetoshi Nishimori says when explaining the mechanism of quantum computers, which have been attracting attention for their potential to greatly surpass the speed of existing computers. "This is perhaps best summed up by a quote attributed to Richard Feynman[1], one of the founders of quantum electrodynamics and winner of the Nobel Prize in Physics: 'If you think you understand quantum mechanics, you don't understand quantum mechanics,'" Nishimori points out.

In the visible world, water in rivers and oceans is a substance affected by environmental factors such as current and wind, which generate states such as waves. In the quantum world of sub-atomic particles, on the other hand, substance cannot be distinguished from state. Matter exhibits both characteristics of particles and waves, i.e. substance and state. Furthermore, the laws of Newtonian physics do not apply. Quantum mechanics, the mysterious physics based on these characteristics, is now applied to the design of quantum computers.

Computers can be thought of as an aggregate of switches with only two states, "0 or 1," or "on or off." Individual switches are counted in units of bits. While bits on current digital computers can only be "0 or 1," a single qubit on quantum computers can be both "0 and 1" at the same time.

Professor Department of Physics Graduate School of Science and Engineering Hidetoshi Nishimori

Now, what can we do with this? Digital computers require 2N calculations to encode data into binary digits (bits), which means that the greater N is, the more time is required for calculations. Quantum computers, however, perform multiple calculations in superposition states instead of performing individual calculations. This allows them to quickly process extremely large amounts of numbers simultaneously, giving them a decisive advantage over conventional computers.

"Quantum mechanics," Nishimori continues, "has been applied to current computers in, for example, semiconductor products such as memory and CPU. The problem is that its application is limited to hardware. But now quantum computers incorporate quantum mechanics into software and algorithms."

Optimization greatly improves efficiency

There are two models of quantum computers. One is called the circuit model. Although extensive research has been conducted on this model, we still have a long way to go before a practical device for real-life use can be realized because the model is susceptible to noise, and tens of millions of qubits and precise control are required for its commercialization.

The other is the quantum annealing model proposed by Nishimori and his student, Tadashi Kadowaki, in 1998. Quantum annealing is designed to solve combinatorial optimization problems, and is different from the traditional approach in that it does not involve algorithms or programs in the usual sense. Quantum annealing has been widely recognized as a model that has enabled the realization of quantum computers with commercial value.

An example traveling salesman problem
An example traveling salesman problem

To better understand combinatorial optimization problems, let's take a look at the traveling salesman problem (TSP). TSP seeks the shortest possible route that a salesman can take to visit each city on a given map exactly once before returning to the origin. Applying quantum annealing to TSP, we can express TSP in a quantum mechanical formula to find a solution using parallel computations. The quantum annealing model is resilient to noise, and its broad real-life applications include the scheduling of transportation and enhanced efficiency in image recognition for medical diagnosis. In addition, it requires thousands, rather than tens of millions of qubits, which makes wide commercial dissemination in the near future a real possibility.

"Combinatorial optimization is remarkable in that it is also useful in machine learning—a discipline that focuses on the development of computers with the ability to learn through example inputs and respond accurately to language and images."

Finding similarities between neural networks
in the human brain and spin glass problems

Although Nishimori leads the research in quantum computing, he was not very interested in physics as a high-school student because he thought it puts emphasis on memorization of given formulas rather than logical reasoning. He couldn't enjoy it like his favorite subject, mathematics. However, Nishimori eventually majored in physics.

"Professor Masuo Suzuki, who taught statistical mechanics, talked so enthusiastically about his research topics during his lectures that I was thoroughly fascinated."

Professor Department of Physics Graduate School of Science and Engineering Hidetoshi Nishimori

Nishimori's attraction to statistical mechanics came both from the exciting topics it presented and from the enthusiasm exuded by Professor Suzuki. He was exposed to spin glass problems, a hot topic of discussion at the time. This eventually brought him to the formulation of quantum annealing theory in the 1990s. When he noticed similarities between spin glass theory and the theory of neural networks introduced by American physicist John Hopfield in 1982, he saw an opportunity to introduce quantum effects into the formula and a door to an innovative field opened.

"There are rare moments when everything you have learned suddenly comes together in your mind. When I looked at what roles quantum effects play in neural networks, I saw clear similarities to thermal, non-classical effects."

There were many researchers working on annealing but no one had looked at it in combination with quantum mechanics. Nishimori did, and that eventually led to his success.

Can quantum annealing machines solve
combinatorial optimization problems efficiently in the future?

Courtesy of D-Wave Systems, Inc.
Courtesy of D-Wave Systems, Inc.

There has recently been significant progress in research and development in the field of quantum computers. In 2013, Google and NASA purchased the D-Wave Two, the world's first commercialized quantum computer, from D-Wave Systems, Inc. in Canada. In September 2014, Google announced it would start development of related hardware. It is globally recognized that the fundamental idea behind these quantum computers was based on the theory established by Nishimori and Kadowaki.

"Improvements in the efficiency of the methods to solve combinatorial optimization problems have big impacts on society. The D-Wave Two computer system uses 512 qubits. In theory, it contains 2512 states simultaneously. If development proceeds as planned, in a few years, quantum annealing machines will be able to solve some combinatorial optimization problems that cannot be solved by existing supercomputers."

Nishimori concludes with a message to Tokyo Tech students.

"It is of course important to solve problems with known methods, but it is sometimes important to try very different, unconventional approaches. Always keep your eyes open and try to find different perspectives. This will lead you to a breakthrough."

Explanations of Technical Terms

1. Richard Phillips Feynman (1918-1988)

Richard Phillips Feynman was an American theoretical physicist. In 1965, for his contributions to the development of quantum electrodynamics, Feynman received the Nobel Prize in Physics along with Julian Schwinger and Shinichiro Tomonaga.

Professor Department of Physics Graduate School of Science and Engineering Hidetoshi Nishimori

Hidetoshi Nishimori

Profile

  • 2011Dean of the Graduate School of Science and Engineering
    Dean of the School of Science, Tokyo Institute of Technology (until 2015)
  • 1996Professor, School of Science, Tokyo Institute of Technology (until present)
  • 1990Associate Professor, School of Science, Tokyo Institute of Technology
  • 1984Assistant Professor, School of Science, Tokyo Institute of Technology
  • 1982Research Associate, Rutgers University, USA
  • 1982Doctor of Science, Department of Physics, Graduate School of Science, University of Tokyo
  • 1981Research Associate, Carnegie Mellon University, USA
  • 1977Bachelor of Science, Department of Physics, Faculty of Science, University of Tokyo

SPECIAL TOPICS

The Special Topics component of the Tokyo Tech Website shines a spotlight on recent developments in research and education, achievements of its community members, and special events and news from the Institute.

Past features can be viewed in the Special Topics Gallery.

Published: April 2015

Contact

Public Relations Division, Tokyo Institute of Technology

Email pr@jim.titech.ac.jp