2006年度今井研演習Ⅲ課題説明会

2007年度
今井研究室紹介
２００７年６月２９日
今井研究室の研究テーマ
『アルゴリズム』の研究
今井研究室の研究テーマ
未踏域への挑戦
現実社会への応用
今井研究室の研究テーマ
現実社会での応用
未踏域への挑戦
量子
生体認証
ゲーム探索
暗号理論
計算幾何
計算代数
計算量理論
グラフ理論
離散・連続最適化
組合せ論
博士論文(1)



計算幾何
 アレンジメント再構成の組合せ論的複雑度評価（青木保一，1993）
 リーマン計算幾何：凸包，ボロノイ図とデローネ型三角形分割
（大西建輔，1998）
 特徴多様体上のクラスタリング問題について（稲葉真理，1999）
 整数計画法による三角形分割の最適化（田島玲，2000）
 三角形分割の組合せ論（竹内史比古，2001）
 多面体的複体のシェリング向き付け：
シェラビリティー判定と離散最適化の組合せ構造（森山園子，2006）
 有向マトロイドの実現を与える方法および特徴のある有向マトロイド
（中山裕貴，2007）
計算代数
 単模およびLawrence型整数計画問題に対する計算代数的解析
（石関隆幸，2003）
量子計算
 計算量的観点における量子計算モデルの計算能力（小林弘忠，2002）
 資源制約下における量子計算モデルの計算能力（ルガルフランソワ，2006）
 エンタングルメントコストの解析とホレボ容量の計算（下野寿之，2006）
 Bell不等式とカット多面体：量子情報科学と組合せ最適化の結合
（伊藤剛，2007）
博士論文(2)




ゲームツリー探索
 AND/OR木探索アルゴリズムDf-pnの提案とその応用（長井歩，2002）
ゲノム・文字列処理
 文書検索と圧縮の統合-接尾辞ソート、ブロックソート法、接尾辞配列（定兼邦彦，2000）
 部分文字列の性質に基づく計算機援用大規模生物実験設計
（土井晃一郎，2001）
 生物配列情報の比較と検索のための高速なアルゴリズムの研究
（渋谷哲朗，2002）
グラフ理論
 Tutte多項式の計算アルゴリズムとその応用（関根京子，1997）
 リンクベースのWeb上情報発見手法の新しいフレームワーク
（浅野泰仁，2003）
ネットワーク
 ネットワーク通信において通信品質を保証するアルゴリズム
（古賀久志，2002）
最近三年間の修士論文





計算幾何

最小包含球問題から得られるCube グラフの向きづけ（西鳥羽二郎，2007）
計算代数

代数幾何学的な多変数多項式の既約証明アルゴリズム及び周辺の問題
（ベック和穂エリック，2006）
計算量理論

ASPのNP（FNP）以外への拡張（瀬田剛広，2005）

Ｌ対Ｐ問題の折り返し対アクセス問題への関連付けとそれらの組み合わせ構造
（上野賢哉，2007）
量子計算

デコヒーレンスエラーに対する量子数え上げアルゴリズムの理論的解析
（長谷川淳，2005）

Schrodingerの車：１次元交通流セルオートマトンの量子化（山田崇，2005）

可解群に対する多項式時間量子アルゴリズム（乾義文，2007）
交通流解析

車両軌跡データの分析による交通情報の把握とその応用（柴田輝之，2006）
研究室の活動

セミナー


週１回持ち回りで研究内容を発表
輪講

決まったテーマで論文、本を読む
今井研の活動は内部に留まらない

研究室内に留まらない活動

外部との交流も積極的に




共同研究カナダ McGill大学の David Avis 教授
スイス ETH大学の Komei Fukuda 教授
国際会議、研究会
論文誌への投稿
外部の研究施設

ERATO
日経BPムック
「変革する大学
東京大学理学部」
より
研究室環境





研究室
 311号室、314号室（図書室の隣）
個人用端末、机
 PCを購入予定
計算サーバ
プリンタ(カラー2台)とコピー機
発表用のノートPCとプロジェクタ
314号室
図書館前
311号室
今井研の方針
研究について
自分で考える
こと
独りよがりでいいわけではない

研究を独力で行うために


外の世界と交流する


研究の流行盛衰を把握し良いテーマを設定する
研究会に参加したり
世界の大学の人と共著を書いたり
発表を行う能力を身につける

自分の研究成果を知ってもらうために
研究紹介(離散数学)
宮田(M1)、松本(M1)、森山(助教)
研究対象の例(有向マトロイド)
超平面配置、ベクトル配置、有向グラフ、多面体
抽象化
有向マトロイド
有向マトロイド計画
線形計画問題の抽象化
・最小添字規則 [’77 Bland]
・その他のpivotting規則
[’82 Fukuda], [’85 Todd], etc…
線形計画問題の双対性の拡張
最適化、計算幾何、計算代数
実現可能性問題
幾何計算のロバスト性
擬超平面配置と超平面
配置の本質的な差
Semialgebraic setの解析
有向マトロイドは最適化、計算幾何、計算代数などさまざ
まな重要な分野と深いつながりを持つ
有向マトロイドと実現可能性問題
P1
P5
P2
抽象化
χ(123)=sign(det(v1,v2,v3))= χ(124)=sign(det(v1,v2,v4))= -
P4
P3
？？？
χ(125)=sign(det(v1,v2,v5))= 0
χ(234)=sign(det(v2,v3,v4))= +
v4
v1
v5
実現可能性問題
・・・
v2
v3
Chirotope
O
点配置
有向マトロイド
実現可能性問題：
与えられた有向マトロイドに対応する点配置が存在するか？
実はNP-hard
実現可能な十分条件で実現可能なものの一部を見つける
実現不可能な十分条件で実現不可能なものの一部を見つける
実現可能性問題へのアプローチ
[’01 Finschi]による有向マトロイド列挙アルゴリズムの開発
(関連研究)
逆探索によるマトロイドの列挙
[’07 Matsumoto, Moriyama, Imai]
計算機を用いた実現可能性問題へのアプローチが可能に
各手法の強さを実際に計算機で検証、比較
[’05 Nakayama, Moriyama, Fukuda, Okamoto]
それを踏まえた新たな手法の開発
実現可能性判定：
多項式計画の適用 [’07 Nakayama, Moriyama, Fukuda]
実現不可能性判定：
non-HK* [’04 Fukuda, Moriyama, Okamoto]
半正定値計画の適用 [’07 Miyata, Moriyama, Imai]
実現可能性判定の手法ごとの比較
要素数8、ランク4の場合
realizable
????
代数的手法
Solvability sequence
[’86 Bokowski, Sturmfels]
168751
最適化
多項式計画
[’07 Nakayama, Moriyama, Fukuda]
+4432
Remaining case
について実験。
今もまだ実験中
のようです。
実現不可能性判定の各手法の比較
要素数8、ランク4の場合
non-realizable
???
双二次最終多項式 [’90 Bokowski, Richter]
3968
non-Euclideaness
幾何的手法
[’82 Fukuda]
3462
non-HK* [’04 Fukuda, Moriyama, Okamoto]
1382
半正定値計画
440 [’07 Miyata, Moriyama, Imai]
最適化
代数、幾何、最適化などさまざまな方向からのアプローチ
現在自分が取り組んでいること
双二次最終多項式：
Grassmann-Plucker関係式の線形計画緩和
半正定値計画は一般に線形計画より強い
Grassmann-Plucker関係式の半正定値計画緩和
より強い手法が得られる？ → 緩和法が違うため、そうはいかなかった
半正定値計画→多項式計画へ
(より強力に。しかし計算量は増える)
計算量を減らすため、、、
・Grassmann-Plucker Idealの極小生成集合の計算
・有向マトロイドの対称性に関する考察
有向マトロイドの実現可能性問題を通して、semialgebraic setの解析など計算代数へ
の貢献も目指す。
今井研・研究室紹介
（計算量理論・暗号理論）
上野・高橋・永岡・小島
今井研で行われている研究の概観
暗号理論
量子情報理論
対話証明系という考え方
計算量理論
アルゴリズムの可能性と限界の解明
P versus NP
めちゃくちゃ
難しい
論理回路のサイズの下限の証明
緩和
（もう少しだけ
簡単な問題へ）
論理式のサイズの下限の証明
論理回路の深さの下限の証明
Karchmer-Wigderson 通信ゲーム
実は、
並列計算時間
と関係が・・・
論理関数 f を表現する論理式のサイズ（または論理回路の深さ）の下限を求めたい
通信ビット数の下限
Karchmer-Wigderson 通信ゲーム
Alice
Bob
通信ゲームの目的：
xとyが異なるインデックスを探す
f(x)=1となるような
x ∈{0,1}n を受け取る
f(y)=0となるような
y ∈{0,1}n を受け取る
計算理論 (Theory of Computation) が面白い別の理由
単に、コンピュータの中身だけを対象にする学問ではない！
物質科学
生物学
脳科学
進化学
DNA
・・・
背景
経済学
ゲーム理論
社会科学
ネットワーク科学
複雑系
あらゆる系の時間発展は
計算過程として捉えることができる
機械論的世界観
宇宙は、初期状態が与えられたら物理法則から
その時間発展が一意に定まる
自然は、時計仕掛けの精密機械である。
古典力学は、決定論的な因果関係である。
ルネ・デカルト
（１５９６－１６５０）
今井研で行われている研究の概観
暗号理論
量子情報理論
対話証明系という考え方
計算量理論
EPR paradox and Bell inequalities
• Einstein, Podolsky, Rosen (1935)
– quantum entanglement vs. relativity theory
• Bell inequality (1964)
– Entanglement/Nonlocalit⇒violation
• CHSH inequality
(Clauser, Horne, Shimony, Holt 1969)
– applicable to a bipartite system
• Aspect et al. (1982)
– Experimental verification of violation of
CHSH inequality
• Tsirelson (1980): max. violation value
量子情報処理の力の源(の1つ)!!
entanglement
instantly
measure
(local) faster than light
state
change
EPR paradox and Bell inequalities
• Einstein, Podolsky, Rosen (1935)
– quantum entanglement vs. relativity theory
• Bell inequality (1964)
– Entanglement/Nonlocalit⇒violation
• CHSH inequality
デカルトの時代から
(Clauser, Horne, Shimony, Holt 1969)
約４００年続く
– applicable to a bipartite system
機械論的宇宙観の
• Aspect et al. (1982)破壊（アンチテーゼ）
– Experimental verification of violation of
CHSH inequality
• Tsirelson (1980): max. violation value
量子情報処理の力の源(の1つ)!!
entanglement
instantly
measure
(local) faster than light
state
change
A 2-Prover 1-Round Interactive Proof System
[Feige, Lovasz 1992]
Alice
2 Provers
• 事前戦略：回答を協力して練ってよい
• 質問開始後：通信不可(no-signaling)
事前戦略
古典：shared randomness
量子：entanglement
答 a{0,1}
質問 s{0,1}
答 b{0,1}
質問 t {0,1}
2つの質問の内の
1つをランダムに聞く
Victor (Verifier)
Bob
計算理論的世界観へ
コンピュータやネットワークだけじゃなくって、
世の中のありとあらゆる対象を計算理論の土台・技法によって解析。
そして、基礎理論から応用基盤技術へ・・・
今井研で行われている研究の概観
暗号理論
量子情報理論
対話証明系という考え方
計算量理論
ゼロ知識証明[GMR85]
Verifierが秘密情報に関する知識を得ら
れないように対話証明を行う枠組み
様々な暗号理論への応用 : 認証技術[FS87]
Proverの主張
の正当性を検
証
秘密情報の保
持を主張
質問と返答
(対話)
Verifier
Prover
[GMR85] S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of
interactive proof systems. SIAM Journal of Computing.
[FS87] A. Fiat and A. Shamir. How to prove yourself : practical solutions to
identification and signature problems. In Advances in Crypto ’86.
生体認証
パスワードなどの代わりに、指紋や静脈
パターンなどの生体情報を利用する認証
技術
本人認証
host
user
◎利便性が高い
×情報漏洩のリスクが高い
量子計算・量子暗号
長谷川淳（博士3年），尾張正樹（特任助教）
加藤公一（博士3年），浅田益仁（修士2年）
鈴木真吾（修士2年），高橋敏明（修士2年）
徳田優（修士1年）
量子とは・・・
量子効果が出現
ムーアの法則からも・・・
古典（現在）の世界
ビット（1か0）
1 0
量子の世界
量子ビット（1と0の間も取れる）
1
1
イメージ（電圧）
イメージ（粒子）
１つの演算で・・・
同時に計算可能（量子並列性）
1つの計算しかできない
1 0
0
1
量子で何ができるの（計算編）？
入力 : 合成数 c = a×b
出力 : 素数 a, b
Shorのアルゴリズム[‘95]
素因数分解
現代暗号（RSAなど）
が解かれてしまう
多項式時間アルゴリズム
（古典だと準指数時間）
入力：要素 x1 ,, x2n
関数 f
出力 : x s.t. f(x) = 1
Groverのアルゴリズム[‘96]
非ソートデータの検索
指数の平方根時間アルゴリズム
（古典だと指数時間）
多くの問題（NP完全など）
が指数の平方根時間で
解ける
量子で何ができるの（暗号編）？
古典（現在）の暗号
量子の暗号
暗号の安全性は・・・
計算量に基づく
量子計算で
解かれる
無条件安全
（量子力学＋情報理論）
無限の計算能力を
もってしても，破れない！
量子暗号の仕組み
秘密鍵配送（共有）プロトコル[BB ’84]
送信者
（計算量に依らない）
受信者
量子通信路（光ファイバ）
盗聴
情報を得ると（盗聴検出可能）
量子状態が変わる
情報の変化の度合いから
盗聴情報量を推測できる！
盗聴者
盗聴された情報量だけ
秘密鍵を減らして安全性確保!!
自分の研究テーマ
理想から現実へ（実用化に向けて）
より厳密な議論が
必要・・・
本当に安全？
（安全性の保証が容易）
理想の世界
•無限の長さの情報（符号長）が扱える
•完全な装置や通信路
秘密鍵配送実験（20km伝送）
現実の世界
•有限の長さの情報
•不完全なデバイス
•統計揺らぎが含まれる
新たな理論＋実験
ERATO-SORSTとNECによる
共同研究
（盗聴情報量が2-9ビット以下を保証）
現実の世界で安全な秘密鍵の
伝送に成功（伝送速度200bps）
数年後には数Mbpsに
最近の研究室のテーマ（量子）
量子の分野は，今井研の他の分野とも密接に関係
（群論，計算量）
量子アルゴリズム・量子回路
隠れ部分群問題
量子ウォーク
量子回路設計
（符号理論）
量子誤り訂正・雑音
量子誤り訂正符号
ノイズに強い量子回路
（情報理論，計算幾何，情報幾何）
（暗号理論）
量子情報理論
量子暗号
秘密鍵配送
デジタル署名
量子通信路容量・量子エントロピー
量子情報幾何
Bell不等式の列挙・破れの発見
グラフの量子彩色数

Download Report