| 講演抄録／キーワード |
| 講演名 |
2019-11-18 13:50
［ポスター講演］単純グラフ最小カット問題における量子アニーリングの励起状態活用
○寺西寛人・永山翔太（メルカリ） |
| 抄録 |
（和） |
量子アニーリングはイジングモデルの基底状態を求める量子アルゴリズムであり, 実機へのアクセスがク ラウド提供されていることもあり注目を集めている. しかしながら, ノイズの影響などにより基底状態が検出されにく い場合がある. また最小カット問題からイジングモデルへの既存の変換では自明解を排除するための制約が, 解ける問 題サイズに対して大きなボトルネックとなっている. そこで本稿では最小カット問題に対して励起状態と自明な基底 状態の差分に最適解を埋め込むイジングモデルの構成方法を考案した.本提案の構成方法を用いると最適解は励起状 態に, 自明解は基底状態に割り当てられ, 且つ上記の制約は撤廃される. これによってリソース効率を向上し, また今 回行った実験では十分に最適解を得ることができた. 本稿によりエラーを前提とした量子アニーリングの活用の可能 性が示された. |
| （英） |
Quantum Annealing, a quantum algorithm which finds the ground states of ising model, is provided in a cloud and attracts much attentions. But noise etc. effects make observation of the ground states hard. The existing reduction from minimum cut problem to ising model has constraints to exclude trivial solutions and it is a big bottleneck of sacaling . Here, we suggested configuration of ising model in which we map the optimal solutions of minimum cut problem to difference between its ground state and excited states. Our configuration removes the constraints of the ”normal” ising model of minimum cut problem so that it improves the resource efficieency. We succeeded to obtain the optimal solutions with high probability in our experiments. Our research implies potentials of quantum annealing utilizing its errors. |
| キーワード |
（和） |
最小カット問題 / 量子アニーリング / ヒューリスティック / / / / / |
| （英） |
minimum cut / quantum annealing / heuristic / / / / / |
| 文献情報 |
信学技報 |
| 資料番号 |
|
| 発行日 |
|
| ISSN |
|
| PDFダウンロード |
|
| 研究会情報 |
| 研究会 |
QIT |
| 開催期間 |
2019-11-18 - 2019-11-19 |
| 開催地（和） |
学習院大学 |
| 開催地（英） |
Gakushuin University |
| テーマ（和） |
量子情報, 一般 |
| テーマ（英） |
Quantum Information |
| 講演論文情報の詳細 |
| 申込み研究会 |
QIT |
| 会議コード |
2019-11-QIT |
| 本文の言語 |
日本語 |
| タイトル（和） |
単純グラフ最小カット問題における量子アニーリングの励起状態活用 |
| サブタイトル（和） |
|
| タイトル（英） |
Quantum Annealing for Minimum Cut of a Simple Graph |
| サブタイトル（英） |
|
| キーワード(1)（和/英） |
最小カット問題 / minimum cut |
| キーワード(2)（和/英） |
量子アニーリング / quantum annealing |
| キーワード(3)（和/英） |
ヒューリスティック / heuristic |
| キーワード(4)（和/英） |
/ |
| キーワード(5)（和/英） |
/ |
| キーワード(6)（和/英） |
/ |
| キーワード(7)（和/英） |
/ |
| キーワード(8)（和/英） |
/ |
| 第1著者 氏名（和/英/ヨミ） |
寺西 寛人 / Kanto Teranishi / テラニシ カント |
| 第1著者 所属（和/英） |
メルカリR4D (略称： メルカリ)
mercari R4D (略称： Mercari) |
| 第2著者 氏名（和/英/ヨミ） |
永山 翔太 / Shota Nagayama / ナガヤマ ショウタ |
| 第2著者 所属（和/英） |
メルカリR4D (略称： メルカリ)
mercari R4D (略称： Mercari) |
| 第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 13:50:00 |
| 発表時間 |
120分 |
| 申込先研究会 |
QIT |
| 資料番号 |
|
| 巻番号（vol） |
vol. |
| 号番号（no） |
|
| ページ範囲 |
|
| ページ数 |
|
| 発行日 |
|
|