Dynamical process of a bit-width reduced Ising model with simulated annealing
arXiv:2304.12796 · doi:10.1109/ACCESS.2023.3310875
Abstract
Ising machines have attracted attention as efficient solvers for combinatorial optimization problems, which are formulated as ground-state (lowest-energy) search problems of the Ising model. Due to the limited bit-width of coefficients on Ising machines, the Ising model must be transformed into a bit-width reduced (BWR) Ising model. According to previous research, the bit-width reduction method, which adds auxiliary spins, ensures that the ground state of the BWR Ising model is theoretically the same as the Ising model before bit-width reduction (original Ising model). However, while the dynamical process is closely related to solution accuracy, how the BWR Ising model progresses towards the ground state remains to be elucidated. Therefore, we compared the dynamical processes of these models using simulated annealing (SA). Our findings reveal significant differences in the dynamical process across models. Analysis from the viewpoint of statistical mechanics found that the BWR Ising model has two characteristic properties: an effective temperature and a slow relaxation. These properties alter the temperature schedule and spin flip probability in the BWR Ising model, leading to differences in the dynamical process. Therefore, to obtain the same dynamical process as the original Ising model, we proposed SA parameters for the BWR Ising model. We demonstrated the proposed SA parameters using a square lattice Ising model, in which all coefficients were set uniformly to the same positive values or randomly. Our experimental evaluations demonstrated that the dynamical process of the BWR and original Ising model became closer.
arXiv comment15 pages, 17 figures
References in corpus (25)
- Ising formulations of many NP problems
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
- Quantum Boltzmann Machine
- Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
- A practical heuristic for finding graph minors
- Expanding the horizon of automated metamaterials discovery via quantum annealing
- Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
- Searching for quantum speedup in quasistatic quantum annealers
- Optimized simulated annealing for Ising spin glasses
- Nonnegative/binary matrix factorization with a D-Wave quantum annealer
- Improving solutions by embedding larger subproblems in a D-Wave quantum annealer
- 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
- Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
- Toward Practical-Scale Quantum Annealing Machine for Prime Factoring
- Towards optimization of photonic-crystal surface-emitting lasers via quantum annealing
- Hybrid Quantum Annealing via Molecular Dynamics
- Boosting quantum annealer performance via sample persistence
- Guiding Principle for Minor-Embedding in Simulated-Annealing-Based Ising Machines
- Hybrid Optimization Method Using Simulated-Annealing-Based Ising Machine and Quantum Annealer
- Black-box optimization for integer-variable problems using Ising machines and factorization machines
- Non-monotonic Dynamics in Frustrated Ising Model with Time-Dependent Transverse Field
- Mechanism of Slow Relaxation due to Screening Effect in a Frustrated System
- Non-monotonic Relaxation in Systems with Reentrant Type Interaction
- ISAAQ: Ising Machine Assisted Quantum Compiler
- Proposal of a Checking Parameter in the Simulated Annealing Method Applied to the Spin Glass Model