Exponential Acceleration of Quantum Annealing by Individual Control of the Transverse Field

Quantum annealing is a quantum-mechanical framework to solve combinatorial optimization problems. Certain important problems in the modern society, such as the optimization of traffic flows and the bug detection in large-scale computer programs, can be formulated as combinatorial optimization problems. Thus, the development of efficient solvers of combinatorial optimization problems has enormous practical significance. Hidetoshi Nishimori, professor at Tokyo Tech, Yuki Susa, a research fellow in the Nishimori research team, together with two students Yu Yamashiro and Masayuki Yamamoto, have shown that a qubit-wise ingenious control of the transverse field is very effective for a speedup of quantum annealing for some problems which are difficult to solve under the conventional uniform control of the field.

Figure 1. Uniformly controlled field and qubit-wise controlled field

Problems of social importance such as the optimization of traffic flows, machine learning, and the bug detection of computer programs can often be formulated as combinatorial optimization problems. Quantum annealing is a metaheuristic for combinatorial optimization problems, but, unfortunately, it is not always very effective. A simple and typical example is the model with all-to-all connections, in which all qubits interact with each other. In this artificial model, it is known that the time necessary to reach the optimal solution grows exponentially as the number of qubits increases. It has nevertheless been shown for this problem that the time for solution can be significantly shortened by the addition of special terms which represent strong quantum effects. However, the implementation of such terms as practical circuits in the machine is hindered by serious technical difficulties. The research group at Tokyo Institute of Technology has proposed a method by which one can drastically shorten the computation time without the additional special term.

To perform quantum annealing, it is necessary to control the strength of a parameter called the transverse field. In the conventional formulation of quantum annealing, the transverse field is applied uniformly to the entire system as in Fig. (a). In contrast, under the new method, the transverse field is controlled individually at each qubit, see Fig. (b). By this simple approach, the computation becomes significantly more efficient.

The present method has been shown to be effective for a speedup even for the problem in which the above-mentioned special term does not work to reduce the computation time. This result has been published in the February 2018 issue of the Journal of the Physical Society of Japan.

This method is relatively easy to implement in the practical device. Indeed, the latest model of the annealing machine, built and sold by the Canadian startup D-Wave Systems, realizes a feature corresponding to the present method though in a relatively rudimentary form. The present result is expected to influence the direction of the design of the next-generation quantum annealing machines. Though the present study concerns the special case of the all-to-all connected model, one may expect that theories will be developed for more practically important problems in the near future. If successful, applications of quantum annealing will observe significant advancement. This is a very stimulating research field because basic researches are directly connected with industrial applications.

Reference

Authors :	Yuki Susa, Yu Yamashiro, Masayuki Yamamoto and Hidetoshi Nishimori
Title of original paper :	Exponential Speedup of Quantum Annealing by Inhomogeneous Driving of the Transverse Field
Journal :	Journal of the Physical Society of Japan, 87, 023002 (2018).
DOI :	10.7566/JPSJ.87.023002

• Hidetoshi Nishimori joins IEEE group to define quantum computing terminology | Tokyo Tech News
• Hidetoshi Nishimori - Applying quantum annealing to computers | Research Stories | Research
• Research Group of Hidetoshi Nishimori
• Researcher Profile | Tokyo Tech STAR Search - Hidetoshi Nishimori
• Department of Physics, School of Science
• Latest Research News