Quantum Annealing and Related Optimization Methods

Bikas K. Chakrabarti, Arnab Das

Das, Arnab, Chakrabarti, Bikas

Hiromitsu Kigure, Takeshi Baba, Makoto Taniguchi +1 more

The manufacturing industry encounters numerous optimization problems, one of which is the optimization of storage location assignment (OSLA) problem in logistics. OSLA is a combinatorial optimization problem focused on improving the efficiency of picking operations in logistics centers. We explore quantum annealing (QA) as a potential solution to combinatorial optimization problems and investigate its applicability to the OSLA. The objective function for this optimization is the average travel distance of workers to their assigned destinations. However, this value is derived by solving the Traveling Salesman Problem for multiple orders, which is itself a combinatorial optimization problem. Therefore, it cannot be analytically represented in a quadratic unconstrained binary optimization form. To address this limitation, we employed black-box optimization with annealing (BBO-Annealing), which combines a surrogate model with an annealing algorithm, an approach that has recently gained attention in applied research involving QA. To evaluate the effectiveness of quantum computing, we compared results obtained using simulated annealing (SA) with those obtained using QA. Additionally, to assess the optimization performance of our proposed method, we compared it with a genetic algorithm (GA) that did not utilize a surrogate model of the objective function. QA demonstrated a higher probability of finding the optimal solution (33.3% vs 26.7% with SA). However, the optimization performance of GA surpassed that of the proposed method. Our analysis suggests that the relatively lower performance of our method was primarily attributable to the strong influence of constraints. The optimization performance can be improved by incorporating methods that consider the uncertainty of surrogate model predictions such as the lower confidence bound.

Kristel F. L. Michielsen

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.

E. Arvidsson