講演者：　谷 聖一 氏 （日本大学）

題 名：　量子・結び目・計算

日 時：　２００６年１２月１５日　（金）１８：００〜

場　所：　早稲田大学１４号館７階７１７ＡＢ室　


長いアブストラクト：

　コンピュータを使って何か計算させようとするとき，小さなデータで うまくいったからといって，大きなデータに対して所望の計算結果を得 られるとは限りません．その原因は，特定のデータに対してだけ正しく 動作する方法を用いてしまったということもあるでしょうし，原理的に 正しい計算をするのだがデータのサイズが大きくなるにつれ実行時間が 急激に増加する方法を用いてしまったということもあるでしょう．後者 の場合，より高速な方法を見つけてやれば良いわけですが，本質的に高 速な方法が存在しない，つまり，手に負えない問題もあります．そうな こんなで，高速な方法を設計しよう（アルゴリズム論）としたり，どう いう問題が手に負えないのか考察しよう（計算量理論）としたりする性 向を持つ輩がいます．谷もそのような輩の一人です． 　こういう性向を持つ人の一部は，手に負えない問題に出会うと，確率 的な手法を用いる，近似解で我慢する，高速に解けるインスタンスを見 つけるなどの代償行動に走ります．量子計算などもその一つかもしれま せん．ところで，谷は縁があって，山本慎氏（中央大）や原正雄氏（東 海大）と共同で，結び目理論に現れる計算問題の計算量解析やアルゴリ ズム設計に取り組んでいます（その一部は，以前，この７階セミナーで 原氏が講演しています）． 　ちょっと苦しいですが，なんとかタイトルに含まれている３つのキー ワードが揃いました．10年ほど前から量子計算を位相幾何学的に特徴づ けるという試みがなされています．Freedman, Kitaev, Larsen, Wang [2] は，任意の BQP アルゴリズムの量子計算部分を，その量子アルゴリズ ムに対応する絡み目の Jones 多項式の特定の点の値を近似することで 置き換えられることを示しました．量子計算は，0 と 1 の任意の重ね 合わせ状態を保持できる量子ビットにユニタリ変換を施すことにより計 算を進め，変換後の量子ビットを観測することにより計算結果を得るこ とと見做せます．計算結果を得る確率は，変換後の量子ビットの振幅に より定まります．Freedman らが示したことは，ユニタリ変換に対応す る絡み目 L で，その Jones 多項式 V_L のある点（具体的には 1 の 5乗根）の値 V_L(e^{2pi i/5}) を使うと 0 が観測される確率を近似で きるものを構成できるいうことです．Jones 多項式を決定することは #P-困難であり，Jones 多項式の特定の点における値を評価することも， 一般には #P-困難であることが知られています．#P-困難は，数え上げの 問題に対する計算の難しさの指標で，#P-困難ということは手に負えない ということを意味します．しかし，量子計算を模倣すのに，正確な V_L(e^{2pi i/5}) の値は必要なく，近似値で十分です．さらに， Bordewich, Freedman, Lov\'asz, Welsh [1] は，量子計算を模倣するの に V_L(e^{2\pi i/5}) の符号がわかれば十分であることを示しています． また，Aharonov, Jones, Landau [3] は，V_L(e^{2pi i/k}) を近似する 量子アルゴリズムを提案しています．（[4] はその解説です．） 　今回は，これら一連の進展の中から，谷がある程度内容が理解できた 部分を紹介させてもらいます．よく解らないところもたくさんあり，一 緒に考えてくれる人の募集をかねて話をさせてもらおうと思っています．

[1] M. Bordewich, M. Freedman, L. Lov\'asz and D. Welsh.
Approximate Counting and Quantum Computation.
Combinatorics, Probability and Computing, 2005 Vol.14, pp. 723--736.

[2] M. Freedman, A. Kitaev, M. Larsen and Z. Wang.
Topological quantum computation.
Bulletin of the American Mathematical Society, 40 (2003), 31--38.

[3] D. Aharonov, V. Jones and Z. Landau.
A polynomial quantum algorithm for approximating the Jones polynomial.
Proceedings of the thirty-eighth annual ACM symposium on Theory of
computing, 2006, 427--436.

[4] S. Lomonaco and L. Kauffman.
Topological Quantum Computing and the Jones Polynomial.
quant-ph/0605004 http://arxiv.org/abs/quant-ph/0605004

　　　　世話人
　　　　谷山　公規　　taniyama＋@＋waseda.jp
　　　　石井　仁司　　ishii＋@＋edu.waseda.ac.jp
　　　　大野　修一　　ohno＋@＋nit.ac.jp
　　　　澤田　賢　　　kensan＋@＋waseda.jp
　　　　柴田　良弘　　yshibata＋@＋waseda.jp
　　　　鈴木　晋一　　sssuzuki＋@＋waseda.jp
　　　　羽鳥　理　　　hatori＋@＋math.sc.niigata-u.ac.jp
　　　　広中　由美子　hironaka＋@＋waseda.jp
メイルを送る際は ＋@＋ を @ に置き替えて下さい
注：１４号館は西早稲田（本部）キャンパスにあります。　　 地図


BACK