2009年度演習Ⅲスライド.pptVIP

* * * * * * 量子とは？ ビット(0 or 1)の世界 量子ビット()の世界 0 イメージ：電子スピン “0”と”1”が確率1/2ずつで存在 リソースの違い 0 1 エンタングルメント（量子相関） （情報処理能力の向上） 1 1 操作 変化なし 変化あり 操作 相関なし 相関あり 変化あり 相関あり 量子を使うと何ができるの？ 量子効果よる高速化の障害！！ コンピュータの高速化の限界 素因数分解アルゴリズム exponential gap! 最良の古典アルゴリズム 準指数時間アルゴリズム Shorのアルゴリズム [Shor 94] 多項式時間で解ける！ 暗号理論 RSA暗号 素因数分解の難しさに 安全性をおいている （計算量理論的安全性） BB84プロトコル[BB 84] 量子力学の不完全性定理 に安全性をおいている (情報理論的安全性) 現代の計算機 量子計算機 問題点 量子効果を積極的に利用する 現代の計算機では解けない問題を解く！ 解決策 安全でない！ 量子情報科学の観点から 古典エントロピー （Shannon entropy） 量子エントロピー （von Neumann entropy） 0 1 0 1 雑音ありの通信路 （確率 p でビット反転） 確率 1-p 1-p p p どのくらい情報を送れるか？ 量子効果（エンタングルメント） によって情報量は増えるのか？ 量子操作と古典?量子通信路 容量との関係性は？ 量子の情報処理 能力が知りたい 演習3の課題 シャノンの古典情報理論、量子力学(エンタングルメント、非局所性など)の初歩を学び、量子情報理論の論文購読を行い、その発展を自分で考えて新しい評価、プロトコルを作成。 エンタングルメントを用いた/用いない量子通信路における古典/量子情報伝達 量子通信路における秘密鍵?エンタングルメントの生成 新しい情報科学分野へようこそ 離散数学?計算幾何 夫(M2), 奥田(M2), 宮田(D1), 田沼(D1), 森山(特任講師) 離散数学って、何をするものなの x y z 対象: ばらばらなものたちの組み合わせや、関係性 目的：本質的に持つ構造をとらえること 紙と鉛筆もあり、計算機は手段としても、応用のためにも非常に重要！ 抽象性が高く、基礎であるがゆえに幅広い分野の研究と関連 計算幾何 計算量理論 ゲーム理論 最適化 離散数学の問題の一例 グラフ上の最小重み二部マッチング と のマッチングで、ペアになったものの 間の距離の合計が最小になるもの 工学的な応用上でも、重要な問題 ここがミソ！ 一般のグラフにおけるアルゴリズム 離散数学講義でやったように、普通にやればO(n3) timeできる アルゴリズムの大まかな流れ 下の1, 2をO(n)回繰り返すというのを、O(n)回 注目している青い点からもっとも「近い」赤い点を探す – O(n) time 探し当てた点への距離の正負に応じて、マッチングや点の重みを改善する もっと、規則正しいようなグラフ上では？？ a c b P. M. Vaidya, SIAM J. Comput., 18, 1201-1225 (1989) L1距離のもつ、いい構造を明らかにして、利用している 直交格子グラフ 幾何的な性質を使うと、1.がO(1)でわかるようなデータ構造で、 点の追加?削除がO((log n)3) timeでできるようなものを作れる トータルで、O(n2(log n)3) timeになる ← O((log n)n-3)の高速化！ aからbまでの最短距離 = aからcまでの最短距離+ cからbまでの最短距離 他のグラフについても、同じようにできないか 私がいまやっていること 演習IIIでやること 演習3の進め方何はともあれ 論文を購読して発表してもらいます。(英語、英語、英語????と大変でしょうが、残念ながら卒論も英語なので。) 最終週辺りで余力があればプロジェクトを自分で決めて簡単に研究してみましょう。(せっかく今井研の演習３にきてもらうので。いい経験に なりますよ！！もしかしたら卒論のテーマになるかも？) Appendix : 今井研の宣伝(夫の独断) 部屋が綺麗！！　先輩方が親切だ！！　突発的な飲み会が多い！！学年の垣根がなく仲が良い！！　なにより先生が面白く、情熱的で素敵だ！！(もう今井研にくる以外の選択肢はないですね。) 具体的に、どういうことをしている論文を読むの？ 計算機を使ってバリバリ数え上げるのも、紙と鉛筆で理論的に攻めるのも、どっちもアリ 前のスライドまではアルゴリズムの設計の話をしていたけど、他もアリ 最適化問題に挑戦 もっと、数学的な幾何構造に計算機を使ってアタック