Characterization of Locality in Spin States and Forced Moves for Optimizations
arXiv:2312.02544 · doi:10.7566/JPSJ.93.044802
Abstract
Ising formulations are widely utilized to solve combinatorial optimization problems, and a variety of quantum or semiconductor-based hardware has recently been made available. In combinatorial optimization problems, the existence of local minima in energy landscapes is problematic to use to seek the global minimum. We note that the aim of the optimization is not to obtain exact samplings from the Boltzmann distribution, and there is thus no need to satisfy detailed balance conditions. In light of this fact, we develop an algorithm to get out of the local minima efficiently while it does not yield the exact samplings. For this purpose, we utilize a feature that characterizes locality in the current state, which is easy to obtain with a type of specialized hardware. Furthermore, as the proposed algorithm is based on a rejection-free algorithm, the computational cost is low. In this work, after presenting the details of the proposed algorithm, we report the results of numerical experiments that demonstrate the effectiveness of the proposed feature and algorithm.
arXiv comment8 pages, 3 figures
References in corpus (8)
- Ising formulations of many NP problems
- Exchange Monte Carlo Method and Application to Spin Glass Simulations
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
- Architectural considerations in the design of a superconducting quantum annealing processor
- Quantum Annealing for Combinatorial Clustering
- Jump Markov Chains and Rejection-Free Metropolis Algorithms