(イベント) NP完全問題の量子アニーリングにおける相転移現象 (6/1)
講演者 / Speaker
高橋 惇 （東京大学 大学院総合文化研究科 広域科学専攻）
講演タイトル / Title
NP完全問題の量子アニーリングにおける相転移現象
日 時 / Date & Time
2017年6月1日（木）16:30〜18:00
会 場 / Venue
概 要 / Outline
最適化問題を解くアルゴリズムは情報科学の分野における主要な研究対象だが、物理的なアプローチやプロトコルを用いて最適化問題の解を求める手法が境界領域として近年活発になっている。特に、Kadowaki-Nishimori (1998) や Farhi et al. (2000) に端を発する量子アニーリングは、(2017年5月現在)大規模な実装化に成功している唯一の量子計算機であり、さらに物理的な量であるエネルギーギャップとアルゴリズムの計算時間を結びつけるものとして基礎的にも興味深く、盛んに研究されている。
一方で、量子アニーリングや量子計算機一般を用いても全ての問題が効率良く解けるわけではなく、特に「NP完全問題」と呼ばれる問題群は効率良く解くことが不可能であると計算理論の分野で信じられている。そこで、NP完全問題のような「解けるはずのない問題」に量子アニーリングを適用した際に、計算を阻害する物理現象の解明を試みた。その結果、従来考えられていたスピングラス転移と異なる転移が存在し、その未知の相内で一次転移が誘発され、量子アニーリングの障害になっていることが数値的に示唆された[1]。
本講演では、量子アニーリングの原理や、NP完全問題がなぜ一般に「解けるはずがない」のかを概観し、後半では研究結果を紹介しつつ量子アニーリングの物理的障害について議論します。
[1] Jun Takahashi and Koji Hukushima arXiv:1612.08554
コーディネーター / Coordinator
田中 宗（早稲田大学 高等研究所 准教授（任期付））
対 象 / Prospected Audience
学部生、大学院生、教職員、学外の方、一般の方
主 催 / Organizer
科学研究費助成事業 基盤研究(B)「量子アニーリングが拓く機械学習と計算技術の新時代」（代表：大関真之）
共 催 / Co-organizer
申込み / Registration
入場無料、直接会場へお越し下さい
