Stochastic Simulated Quantum Annealing for Fast Solution of Combinatorial Optimization Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929433627066368 |
|---|---|
| author | Onizawa, Naoya Sasaki, Ryoma Shin, Duckgyu Gross, Warren J. Hanyu, Takahiro |
| author_facet | Onizawa, Naoya Sasaki, Ryoma Shin, Duckgyu Gross, Warren J. Hanyu, Takahiro |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_12454 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Stochastic Simulated Quantum Annealing for Fast Solution of Combinatorial Optimization Problems Onizawa, Naoya Sasaki, Ryoma Shin, Duckgyu Gross, Warren J. Hanyu, Takahiro Quantum Physics Emerging Technologies 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. |
| title | Stochastic Simulated Quantum Annealing for Fast Solution of Combinatorial Optimization Problems |
| topic | Quantum Physics Emerging Technologies |
| url | https://arxiv.org/abs/2302.12454 |