Waseda Institute for Advanced Study (WIAS)Waseda University

News

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

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

講演者  /  Speaker

Jun TAKAHASHI (Department of General Systems Studies, Graduate School of Arts and Sciences, The University of Tokyo)

講演タイトル / Title

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

日 時 /  Date & Time

Thursday, 1 June 2017, 16:30 – 18:00

会 場 /  Venue

Room.212, Building #7, Waseda University 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

Shu TANAKA(Aassociate Professor, Waseda Institute for Advanced Study, Waseda University)

対 象 /  Prospected Audience

Faculty and staff members of a university, grad students, the general publics

主 催 / Organizer

Grant-in-Aid for Scientific Research (B)「量子アニーリングが拓く機械学習と計算技術の新時代」(Masayuki OHZEKI)

共 催 / Co-organizer

Waseda Institute for Advanced Study,Waseda University

申込み /  Registration

Free of charge. Please come to the event venue directly.

Dates
  • 0601

    THU
    2017

Tags
Posted

Tue, 16 May 2017

Page Top
WASEDA University

Sorry!
The Waseda University official website
<<https://www.waseda.jp/inst/wias/en/>> doesn't support your system.

Please update to the newest version of your browser and try again.

Continue

Suporrted Browser

Close