Waseda Institute for Advanced Study (WIAS)早稲田大学 高等研究所

News

ニュース

(イベント) NP完全問題の量子アニーリングにおける相転移現象 (6/1)

(イベント) NP完全問題の量子アニーリングにおける相転移現象 (6/1)

講演者  /  Speaker

高橋 惇 (東京大学 大学院総合文化研究科 広域科学専攻)

講演タイトル / Title

NP完全問題の量子アニーリングにおける相転移現象

日 時 /  Date & Time

2017年6月1日(木)16:30〜18:00

会 場 /  Venue

早稲田大学 早稲田キャンパス 7号館 212号室 PDFファイルを開きます

概 要 / 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

入場無料、直接会場へお越し下さい

Page Top
WASEDA University

早稲田大学オフィシャルサイト(https://www.waseda.jp/inst/wias/)は、以下のWebブラウザでご覧いただくことを推奨いたします。

推奨環境以外でのご利用や、推奨環境であっても設定によっては、ご利用できない場合や正しく表示されない場合がございます。より快適にご利用いただくため、お使いのブラウザを最新版に更新してご覧ください。

このままご覧いただく方は、「このまま進む」ボタンをクリックし、次ページに進んでください。

このまま進む

対応ブラウザについて

閉じる