Tohoku Univ. Technology：Sparse-Compatible Algorithm for Simulated Quantum Annealing (SQA): T25-011

Highly Efficient Parallel Computing Leveraging Real-World Physical Constraints (Sparsity)

To simulate quantum annealing on classical computers, Simulated Quantum Annealing (SQA) based on the Ising model has gained attention. The inventors have developed a parallel algorithm that enables multi-level parallel processing of SQA with a fully connected Ising model, implemented on a Field Programmable Gate Array (FPGA) (related work [1]). However, most real-world optimization problems possess a "sparse" structure, where only specific spins interact. Consequently, algorithms assuming full connectivity faced challenges of inefficiency, as they allocated hardware resources to calculate interactions that were not actually required. This invention supports sparse coupling models and proposes an algorithm that allows for faster analysis of classical spin systems based on the Ising model. This makes it possible to execute SQA at practical speeds using FPGA acceleration, even for large-scale problems that were previously unmanageable with fully connected models.

others