Study of Optimization Problems by Quantum Annealing(量子アニーリングによる最適化問題の研究)

門脇正史

We introduce quantum fluctuations into the simulated annealing process of optimization problems, aiming at faster convergence to the optimal state.Quantum fluctuations cause transitions between states and thus play the same role as thermal fluctuations in the conventional approach.The idea is tested by the two models, the transverse Ising model and the traveling salesman problem.Adding the transverse field to the Ising model is a simple way to introduce quantum fluctuations.The strength of the transverse field is controlled as a function of time similarly to the temperature in the conventional method.The goal is to find the ground state of the diagonal part of the Hamiltonian with high accuracy as quickly as possible.We also consider the traveling salesman problem.This model can be described by the Ising spin, so that we also apply the same technique to the transverse Ising model.We solve the time-dependent Schrödinger equation numerically for small size systems with various types of exchange interactions of the Ising model.Comparison with the results of the corresponding classical (thermal) method reveals that the quantum method leads to the ground state with much larger probability in almost all cases if we use the same annealing schedule of the control parameters.We check the case of large-size systems by using the quantum Monte Carlo method.The simulation supports the results of the small-size systems, while the dynamics of the Schrödinger equation and the quantum Monte Carlo method are not the same.We find that the simulated annealing by quantum fluctuations has a better performance than the conventional method for the ground state search of the Ising-spin systems.The calculation of the traveling salesman problem is also performed as A.3 Case of Γ(t) = c/ √ t . . . . . . . . . . . . . . . . . . . . . . . .

Arnab Das, Bikas K. Chakrabarti

Sovanmonynuth Heng, Dongmin Kim, Tae-Kyung Kim +1 more

A combinatorial optimization problem (COP) is the problem of finding the optimal solution in a finite set. When the size of the feasible solution set is large, the complexity of the problem increases, and it is not easy to solve in a reasonable time with the current classical computer technology. Quantum annealing (QA) is a method that replaces classical simulated annealing (SA) methods that do not solve these cases. Therefore, several attempts have been made to solve this problem using a special-purpose quantum annealer to which the QA method is applied. In this survey, we analyze recent studies that solve real-scale COPs using quantum annealers. Through this, we discuss how to reduce the size of the COP to be input to overcome the hardware limitations of the existing quantum annealer. Additionally, we demonstrated the applicability of quantum annealer to COP on a practical scale by comparing and analyzing the results of the classical simulated annealing (SA) and QA method from each study.

Sei Suzuki

Das, Arnab, Chakrabarti, Bikas

Jincheng Zhang

This paper investigates the application of the Quantum Annealing (QA) algorithm to solve complex optimization problems. The core claim is that simulating a complex optimization problem's local search process through the QA's annealing process can effectively locate global optimal solutions. The mechanism involves mapping the solution space of an optimization problem onto the annealing path of QA, controlling the annealing rate and path to guide the solution towards the optimal point. This research leverages QA's inherent ability to mimic physical annealing, aiming to enhance optimization efficiency and accuracy. We present a framework for formulating and applying QA to various complex problems, highlighting its potential advantages over traditional optimization methods. This work contributes to the growing field of quantum computing by demonstrating a practical approach to tackling challenging optimization tasks. The results suggest that QA can be a viable alternative for achieving superior performance in specific optimization scenarios.