Rejection-Free Monte Carlo Simulation of QUBO and Lechner–Hauke–Zoller Optimization Problems
Many studies have attempted to develop simple and efficient methods for solving global optimization problems. Simulated annealing (SA) has been recognized as a powerful tool for performing this task. In this study, we implemented a rejection-free Monte Carlo (RFMC) algorithm, which is a kernel of re...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2022-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9852216/ |
| _version_ | 1826938532092968960 |
|---|---|
| author | Yoshihiro Nambu |
| author_facet | Yoshihiro Nambu |
| author_sort | Yoshihiro Nambu |
| collection | DOAJ |
| description | Many studies have attempted to develop simple and efficient methods for solving global optimization problems. Simulated annealing (SA) has been recognized as a powerful tool for performing this task. In this study, we implemented a rejection-free Monte Carlo (RFMC) algorithm, which is a kernel of rejection-free SA (RFSA). We showed its validity and advantage in obtaining globally optimal solution for quadratic unconstrained binary optimization (QUBO) and spin-glass problem embedded in the Lechner–Hauke–Zoller (LHZ) architecture. Landscapes of success probabilities of finding the globally optimal solution as well as feasible solutions were evaluated as a function of a set of hyper-parameters used to characterize the weights of cost and penalty functions. We demonstrated that the efficiency of RFMC was greatly enhanced compared to that of standard MC. Furthermore, we found that the landscapes for QUBO and those for LHZ problem show considerably different views. When we focus on a specific class of problems, the smaller the problem size, the more scattered is the success probability. We also show that the success probabilities can be further improved by avoiding inefficiencies due to cycling of state transitions using short-term memory mechanisms. We suggest a reasonable strategy to tune hyper-parameters and find the correct global solution using RFSA. |
| first_indexed | 2024-04-11T21:22:29Z |
| format | Article |
| id | doaj.art-afcd70dd435f4295ad25e8b54a1f7cc3 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2025-02-17T18:58:29Z |
| publishDate | 2022-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-afcd70dd435f4295ad25e8b54a1f7cc32024-12-11T00:01:37ZengIEEEIEEE Access2169-35362022-01-0110842798430110.1109/ACCESS.2022.31971769852216Rejection-Free Monte Carlo Simulation of QUBO and Lechner–Hauke–Zoller Optimization ProblemsYoshihiro Nambu0https://orcid.org/0000-0002-1197-8341NEC-AIST Quantum Technology Cooperative Research Laboratory, National Institute of Advanced Industrial Science and Technology, Tsukuba, Ibaraki, JapanMany studies have attempted to develop simple and efficient methods for solving global optimization problems. Simulated annealing (SA) has been recognized as a powerful tool for performing this task. In this study, we implemented a rejection-free Monte Carlo (RFMC) algorithm, which is a kernel of rejection-free SA (RFSA). We showed its validity and advantage in obtaining globally optimal solution for quadratic unconstrained binary optimization (QUBO) and spin-glass problem embedded in the Lechner–Hauke–Zoller (LHZ) architecture. Landscapes of success probabilities of finding the globally optimal solution as well as feasible solutions were evaluated as a function of a set of hyper-parameters used to characterize the weights of cost and penalty functions. We demonstrated that the efficiency of RFMC was greatly enhanced compared to that of standard MC. Furthermore, we found that the landscapes for QUBO and those for LHZ problem show considerably different views. When we focus on a specific class of problems, the smaller the problem size, the more scattered is the success probability. We also show that the success probabilities can be further improved by avoiding inefficiencies due to cycling of state transitions using short-term memory mechanisms. We suggest a reasonable strategy to tune hyper-parameters and find the correct global solution using RFSA.https://ieeexplore.ieee.org/document/9852216/Monte Carlosimulationannealingcombinatorial optimizationquadratic unconstrained binary optimizationIsing model |
| spellingShingle | Yoshihiro Nambu Rejection-Free Monte Carlo Simulation of QUBO and Lechner–Hauke–Zoller Optimization Problems IEEE Access Monte Carlo simulation annealing combinatorial optimization quadratic unconstrained binary optimization Ising model |
| title | Rejection-Free Monte Carlo Simulation of QUBO and Lechner–Hauke–Zoller Optimization Problems |
| title_full | Rejection-Free Monte Carlo Simulation of QUBO and Lechner–Hauke–Zoller Optimization Problems |
| title_fullStr | Rejection-Free Monte Carlo Simulation of QUBO and Lechner–Hauke–Zoller Optimization Problems |
| title_full_unstemmed | Rejection-Free Monte Carlo Simulation of QUBO and Lechner–Hauke–Zoller Optimization Problems |
| title_short | Rejection-Free Monte Carlo Simulation of QUBO and Lechner–Hauke–Zoller Optimization Problems |
| title_sort | rejection free monte carlo simulation of qubo and lechner x2013 hauke x2013 zoller optimization problems |
| topic | Monte Carlo simulation annealing combinatorial optimization quadratic unconstrained binary optimization Ising model |
| url | https://ieeexplore.ieee.org/document/9852216/ |
| work_keys_str_mv | AT yoshihironambu rejectionfreemontecarlosimulationofquboandlechnerx2013haukex2013zolleroptimizationproblems |