量子アニーリングエミュレータのためのデータ構造

• Item type: Symposium(1)
• 公開日: 2019-08-21
• タイトル: 量子アニーリングエミュレータのためのデータ構造
• タイトル / 言語: en
• タイトル: Data Structure for Quantum Annealing Emulator
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: イジングモデル
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 早稲田大学
• 著者所属: 早稲田大学
• 著者所属: 早稲田大学
• 著者所属(英): en
• 著者所属(英): Waseda University
• 著者所属(英): en
• 著者所属(英): Waseda University
• 著者所属(英): en
• 著者所属(英): Waseda University
• 著者名: 植田, 圭; 戸川, 望; 木村, 晋二
• 著者名(英): Kei, Ueda; Nozomu, Togawa; Shinji, Kimura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 組み合わせ最適化問題の高速な解法として，近年量子アニーリングが注目を集めている．量子アニーリングでは，スピンとそれらの間の相互作用を考慮するイジングモデルを用い，最適化問題を系全体のエネルギーが最小となる場合に最適となるように表現する．量子アニーリングでは量子モンテカルロ法が用いられるが，演算回数が膨大なものとなり，エミュレータによる高速化が必要である．しかし，エミュレーションで使用できるメモリが限られているので，データ量を削減できるデータ構造の検討を行い，量子アニーリングの入力となる相関係数の行列を，値の連続性を用いて，疎行列となる場合に効率よく表す手法を提案する．具体的には，値の表にデータを二つずつ検索して登録する手法で，データ圧縮を行った．提案手法を32地点の巡回セールスマン問題に適用することで，データ量を約1/10に削減することができた．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Recently, quantum annealing has attracted attention as an efficient algorithm for combinatorial optimization problems. In quantum annealing, an optimization problem is expressed by using the ising model, which is a set of correlated quantums and its total energy is minimum corresponding to the optimal solution. This manuscript introduces a compressed data structure to emulate the quantum annealing. To specify an ising model or an equivalent QUBO(Quadratic Unconstrained Binary Optimization) model, all coefficients between a pair of quantums and the self energy of each quantum need to be described. The data size becomes large and its reduction is important for the emulation since the usable memory size is limited. We propose a method to efficiently represent a sparse matrix of the correlation coefficients by using the continuity of the values. A value table are introduced and data are compressed by the search and registration method of two consecutive data in the value table. The proposed method is applied to input data of traveling salesman problems at 32 points and can reduce the amount of data to about 1/10.
• 書誌情報: DAシンポジウム2019論文集; 巻 2019, p. 39-44, 発行日 2019-08-21
• 出版者 / 言語: ja
• 出版者: 情報処理学会