Sparse-Compatible Algorithm for Simulated Quantum Annealing (SQA)

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

Overview

　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.

Product Application

Applicable to diverse "combinatorial optimization" challenges:
□Logistics : Optimizing task assignment and sequencing for thousands of AGVs to maximize throughput.
□Mobility : Dynamic traffic optimization and cooperative routing to fundamentally resolve urban congestion.
□DX & Finance : Rapidly deriving optimal solutions for workforce scheduling, finance, and drug discovery from massive candidate sets.

Related Works

[1] JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015

IP Data

IP No.　 ： JP2025-023971
Inventor ： Waidyasooriya Hasitha Muthumala, Masanori Hariyama
keyword ： Simulated Quantum Annealing, Ising model, sparse, sparse coupling model, FPGA, AGV, Quantum computer