Koopman analysis of combinatorial optimization problems with replica exchange Monte Carlo method

Abstract

Combinatorial optimization problems play crucial roles in real-world applications, and many studies from a physics perspective have contributed to specialized hardware for high-speed computation. However, some combinatorial optimization problems are easy to solve, and others are not. Hence, the qualification of the difficulty in problem-solving will be beneficial. In this paper, we employ the Koopman analysis for multiple time-series data from the replica exchange Monte Carlo method. After proposing a quantity that aggregates the information of the multiple time-series data, we performed numerical experiments. The results indicate a negative correlation between the proposed quantity and the ability of the solution search.

9 pages, 6 figures

References in corpus (9)

• Ising formulations of many NP problems
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• A Data-Driven Approximation of the Koopman Operator: Extending Dynamic Mode Decomposition
• Linear predictors for nonlinear dynamical systems: Koopman operator meets model predictive control
• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• Architectural considerations in the design of a superconducting quantum annealing processor
• Residual Energies after Slow Quantum Annealing
• Quadratic unconstrained binary optimization formulation for rectified-linear-unit-type functions
• Characterization of Locality in Spin States and Forced Moves for Optimizations