| 講演抄録／キーワード |
| 講演名 |
2019-11-18 11:00
［招待講演］シミュレーテッド分岐アルゴリズム ～ 古典断熱過程に基づく組合せ最適化 ～
○後藤隼人（東芝） |
| 抄録 |
（和） |
最近我々は、分岐現象を示す古典ハミルトン力学系の数値シミュレーションに基づく組合せ最適化アルゴリズムを提案した。我々はこれを「シミュレーテッド分岐（Simulated Bifurcation, SB）アルゴリズム」と呼び、これを利用したイジングマシンを「シミュレーテッド分岐マシン（SB Machine, SBM）」と呼ぶ。スピンを1 つ1 つ反転するかどうかを決定する逐次処理に基づくシミュレーテッドアニーリング（Simualted Annealing, SA）と異なり、SBではすべての位置・すべての運動量をそれぞれ同時に更新できるため、高い並列性を有する。このSB の高い並列性を生かすことで、既存のデジタル計算機を用いて高速で大規模なイジングマシンを実現することができる。実際、2000スピン・全結合イジング問題に対し、シングルFPGA で実装されたSBM は光パラメトリック発振器ネットワークを用いたコヒーレントイジングマシンよりも約10 倍高速であり、10 万スピン・全結合問題に対しては、GPU クラスタで実装されたSBM は最適化されたSA をシングルCPU コアで実行した場合の約1000 倍高速である。このSBM は古典イジングマシンではあるが、その本質的なアイデアは我々が「量子分岐マシン(Quantum bifurcation Machine, QbM）」と呼んでいる量子コンピュータから発見されたため、量子計算との関連が深い。本講演では、QbM の紹介から始め、SB アルゴリズムを導出し、その後、SBM の原理や性能について説明する。 |
| （英） |
We have recently proposed a heuristic algorithm for combinatorial optimization, which is based on the numerical simulation of classical Hamiltonian systems exhibiting bifurcations. We call it “Simulated Bifurcation (SB) algorithm,” and refer to Ising machines based on SB as SB machines (SBMs). Unlike simulated annealing (SA), which is based on sequential update determining whether a spin should be flipped or not, in SB all the positions and all the momenta, respectively, can be updated in parallel, and therefore SB possesses high parallelizability. Harnessing this advantage of SB, we can realize ultrafast and ultralarge Ising machines using conventional digital computers. In fact, we have realized an SBM using a single FPGA for an all-to-all connected 2000-spin Ising problem, which is about ten times faster than a state-of-the-art coherent Ising machine using optical parametric oscillators. We have also realized an all-to-all connected 100000-spin SBM using a GPU cluster, which is about 1000 times faster than optimized SA software performed using a single CPU core. While the SBMs are classical Ising machines, they originate from our proposed quantum computer named “Quantum bifurcation Machine (QbM),” and therefore the SB is related to quantum omputating. Here we present the principle and performance of our SBMs after introducing the QbM and deriving the SB algorithm. |
| キーワード |
（和） |
組合せ最適化 / イジングマシン / 量子計算 / 断熱定理 / 分岐現象 / / / |
| （英） |
combinatorial optimization / Ising machine / quantum computation / adiabatic theorem / bifurcation / / / |
| 文献情報 |
信学技報 |
| 資料番号 |
|
| 発行日 |
|
| ISSN |
|
| PDFダウンロード |
|
| 研究会情報 |
| 研究会 |
QIT |
| 開催期間 |
2019-11-18 - 2019-11-19 |
| 開催地（和） |
学習院大学 |
| 開催地（英） |
Gakushuin University |
| テーマ（和） |
量子情報, 一般 |
| テーマ（英） |
Quantum Information |
| 講演論文情報の詳細 |
| 申込み研究会 |
QIT |
| 会議コード |
2019-11-QIT |
| 本文の言語 |
日本語 |
| タイトル（和） |
シミュレーテッド分岐アルゴリズム |
| サブタイトル（和） |
古典断熱過程に基づく組合せ最適化 |
| タイトル（英） |
Simulated bifurcation algorithm |
| サブタイトル（英） |
Combinatorial optimization based on classical adiabatic evolution |
| キーワード(1)（和/英） |
組合せ最適化 / combinatorial optimization |
| キーワード(2)（和/英） |
イジングマシン / Ising machine |
| キーワード(3)（和/英） |
量子計算 / quantum computation |
| キーワード(4)（和/英） |
断熱定理 / adiabatic theorem |
| キーワード(5)（和/英） |
分岐現象 / bifurcation |
| キーワード(6)（和/英） |
/ |
| キーワード(7)（和/英） |
/ |
| キーワード(8)（和/英） |
/ |
| 第1著者 氏名（和/英/ヨミ） |
後藤 隼人 / Hayato Goto / ゴトウ ハヤト |
| 第1著者 所属（和/英） |
(株)東芝 (略称： 東芝)
Toshiba Corporation (略称： Toshiba) |
| 第2著者 氏名（和/英/ヨミ） |
/ / |
| 第2著者 所属（和/英） |
(略称： )
(略称： ) |
| 第3著者 氏名（和/英/ヨミ） |
/ / |
| 第3著者 所属（和/英） |
(略称： )
(略称： ) |
| 第4著者 氏名（和/英/ヨミ） |
/ / |
| 第4著者 所属（和/英） |
(略称： )
(略称： ) |
| 第5著者 氏名（和/英/ヨミ） |
/ / |
| 第5著者 所属（和/英） |
(略称： )
(略称： ) |
| 第6著者 氏名（和/英/ヨミ） |
/ / |
| 第6著者 所属（和/英） |
(略称： )
(略称： ) |
| 第7著者 氏名（和/英/ヨミ） |
/ / |
| 第7著者 所属（和/英） |
(略称： )
(略称： ) |
| 第8著者 氏名（和/英/ヨミ） |
/ / |
| 第8著者 所属（和/英） |
(略称： )
(略称： ) |
| 第9著者 氏名（和/英/ヨミ） |
/ / |
| 第9著者 所属（和/英） |
(略称： )
(略称： ) |
| 第10著者 氏名（和/英/ヨミ） |
/ / |
| 第10著者 所属（和/英） |
(略称： )
(略称： ) |
| 第11著者 氏名（和/英/ヨミ） |
/ / |
| 第11著者 所属（和/英） |
(略称： )
(略称： ) |
| 第12著者 氏名（和/英/ヨミ） |
/ / |
| 第12著者 所属（和/英） |
(略称： )
(略称： ) |
| 第13著者 氏名（和/英/ヨミ） |
/ / |
| 第13著者 所属（和/英） |
(略称： )
(略称： ) |
| 第14著者 氏名（和/英/ヨミ） |
/ / |
| 第14著者 所属（和/英） |
(略称： )
(略称： ) |
| 第15著者 氏名（和/英/ヨミ） |
/ / |
| 第15著者 所属（和/英） |
(略称： )
(略称： ) |
| 第16著者 氏名（和/英/ヨミ） |
/ / |
| 第16著者 所属（和/英） |
(略称： )
(略称： ) |
| 第17著者 氏名（和/英/ヨミ） |
/ / |
| 第17著者 所属（和/英） |
(略称： )
(略称： ) |
| 第18著者 氏名（和/英/ヨミ） |
/ / |
| 第18著者 所属（和/英） |
(略称： )
(略称： ) |
| 第19著者 氏名（和/英/ヨミ） |
/ / |
| 第19著者 所属（和/英） |
(略称： )
(略称： ) |
| 第20著者 氏名（和/英/ヨミ） |
/ / |
| 第20著者 所属（和/英） |
(略称： )
(略称： ) |
| 講演者 |
第1著者 |
| 発表日時 |
2019-11-18 11:00:00 |
| 発表時間 |
50分 |
| 申込先研究会 |
QIT |
| 資料番号 |
|
| 巻番号（vol） |
vol. |
| 号番号（no） |
|
| ページ範囲 |
|
| ページ数 |
|
| 発行日 |
|
|