FPGAリソースを考慮した量子アニーリングのトロッタ間並列処理手法

• Item type: Symposium(1)
• 公開日: 2021-08-25
• タイトル: FPGAリソースを考慮した量子アニーリングのトロッタ間並列処理手法
• タイトル / 言語: en
• タイトル: Parallel Processing method for Quantum Annealing between Trotters Awared FPGA Resource
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 高性能システム
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 早稲田大学
• 著者所属: 早稲田大学
• 著者所属(英): en
• 著者所属(英): Waseda University
• 著者所属(英): en
• 著者所属(英): Waseda University
• 著者名: 下舞, 創平; 木村, 晋二
• 著者名(英): Sohei, Shimomai; Shinji, Kimura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 種々の組合せ最適化問題の解法に用いられる量子アニーリングの高速化は重要な課題である．ここでは，量子モンテカルロ法に基づく疑似量子アニーリング（SQA，Simulated Quantum Annealing）の FPGA を用いた並列化エミュレーションにおいて，FPGA のリソースを考慮した並列化手法を示す．FPGA のリソースで実現可能な並列数に応じて，スピン変数のトグル処理をトロッタ単位で並列数分の処理単位に分割する．各処理単位のスピンのトグル処理は独立に行われる．メルセンヌツイスタ法による乱数計算と，隣接するトロッタの情報を組み込むことによってスピン間の相互依存関係を克服し，直列処理の場合と同等の精度でハードウェアのリソースに合わせた並列処理を可能とした．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Quantum annealing is a new algorithm to solve combinatorial optimization problems where the original problem is converted to the energy minimization of Ising model or the equivalent QUBO (Quadratic Unconstrained Binary Optimization). Speeding up quantum annealing is important to obtain the solutions of combinatorial optimization problems in short time. In this manuscript, an acceleration method of simulated quantum annealing (SQA) based on the quantum Monte Carlo method is presented for FPGA platforms. The method takes into account the resources of the FPGA. Toggles of spin variables are parallelized trotter by trotter depending on the usable FPGA resource. By using the Mersenne twistor method to compute random numbers and by incorporating information about neighboring trotters, proposed parallel processing can obtain the same accuracy as in the case of serial processing. The proposed method gains more than 20 times speed-up compared with a serial execution of hardware on 32 trotter case.
• 書誌情報: DAシンポジウム2021論文集; 巻 2021, p. 85-91, 発行日 2021-08-25
• 出版者 / 言語: ja
• 出版者: 情報処理学会