Stochastic Simulated Quantum Annealing for Fast Solution of Combinatorial Optimization Problems

In this paper, we introduce stochastic simulated quantum annealing (SSQA) for large-scale combinatorial optimization problems. SSQA is designed based on stochastic computing and quantum Monte Carlo, which can simulate quantum annealing (QA) by using multiple replicas of spins (probabilistic bits) in...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-06
Main Authors: Onizawa, Naoya, Sasaki, Ryoma, Shin, Duckgyu, Gross, Warren J, Hanyu, Takahiro
Format: Article
Language:English
Subjects:
Algorithms
Combinatorial analysis
Computation
Isomorphism
Optimization
Simulated annealing
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we introduce stochastic simulated quantum annealing (SSQA) for large-scale combinatorial optimization problems. SSQA is designed based on stochastic computing and quantum Monte Carlo, which can simulate quantum annealing (QA) by using multiple replicas of spins (probabilistic bits) in classical computing. The use of stochastic computing leads to an efficient parallel spin-state update algorithm, enabling quick search for a solution around the global minimum energy. Therefore, SSQA realizes quantum-like annealing for large-scale problems and can handle fully connected models in combinatorial optimization, unlike QA. The proposed method is evaluated in MATLAB on graph isomorphism problems, which are typical combinatorial optimization problems. The proposed method achieves a convergence speed an order of magnitude faster than a conventional stochastic simulaated annealing method. Additionally, it can handle a 100-times larger problem size compared to QA and a 25-times larger problem size compared to a traditional SA method, respectively, for similar convergence probabilities.
ISSN:2331-8422
DOI:10.48550/arxiv.2302.12454