> home > Physics Focus
 
Exponential Acceleration of Quantum Annealing by Individual Control of the Transverse Field
Hidetoshi Nishimori and Yuki S
File 1 : Vol28_No2_Physics Focus-2.pdf (0 byte)

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

HIDETOSHI NISHIMORI AND YUKI SUSA
TOKYO INSTITUTE OF TECHNOLOGY

Quantum annealing is a quantum-mechanical framework to solve combinatorial optimization problems. Certain important problems in modern society can be formulated as combinatorial optimization problems; thus, the development of efficient solvers of combinatorial optimization problems has enormous practical significance. In the present paper, the authors have shown that the qubit-wise control of the transverse field is very effective for a speedup of quantum annealing for some problems that are difficult to solve under the conventional uniform control of the field.

Problems of social importance, such as the optimization of traffic flow, machine learning, and bug detection in 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 to reach the solution can be significantly shortened by the addition of special terms that represent strong quantum effects. However, the implementation of such terms as practical circuits in a machine is hindered by serious technical difficulties. A research group at Tokyo Institute of Technology has proposed a method by which one could 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 seen in Fig. (a). In contrast, under the new method, the transverse field is controlled individually at each qubit, as seen in Fig. (b). Using this simple approach, computation becomes significantly more efficient.



The new method has been shown to be effective for a speedup even when 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 [1].

This method is relatively easy to implement in a 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 new method, though in a relatively rudimentary form. This method is expected to influence the direction of the design of 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 a significant advancement. This is a very stimulating research field because basic research directly connects to industrial applications.

References

[1] Yuki Susa, Yu Yamashiro, Masayuki Yamamoto and Hidetoshi Nishimori, J. Phys. Soc. Jpn, 87, 023002 (2018).

Published in the February 2018 issue of the Journal of the Physical Society of Japan as an Editor's Choice article.

 

Hidetoshi Nishimori is a professor of physics at Tokyo Institute of Technology. He earned his D. Sci. from the University of Tokyo, and then spent three years in the United States as a postdoctoral fellow at Carnegie-Mellon University and Rutgers University. He then returned to Japan as a research associate at Tokyo Institute of Technology, where he is now a professor of quantum annealing and statistical physics of disordered systems.

Yuki Susa is a postdoctoral research fellow in the Nishimori group at Tokyo Institute of Technology (Tokyo Tech). In 2016 he received his D. Sci. from Tokyo Tech for the study of optimal probe and statistical testing in weak-value amplification. Currently he is working on a theory to improve the efficiency of quantum annealing.