私が最近注目している研究テーマは
この境界領域に関する研究は非常に新しく，世界的にもまだほとんど研究が進んでいません．しかし，近年めざましい結果がいくつか発表されており， これから研究がさらに活発になっていく研究分野だと考えています．
さらにその内容に関連してNP完全とPの間に位置すると考えられる「微妙」な問題(素因数分解問題，離散対数問題，グラフ同型性判定問題，格子最短ベクトル問題など)の計算量理論的，暗号的性質の解明にも非常に興味を持っています．
以下，簡単に (非専門家 or 学生向けに) 私の研究テーマについて説明します．
(2005.3.31追記：まだ量子計算の説明しか書いていません．また続きは書いていくつもりです．)
最近，科学系のニュースでもチラホラ話題になっていますが，量子コンピュータという言葉を耳にした方は多いと思いますが，そんな得体の知れないコンピュータなんて見たこともない，と思われているかも知れません．それはそのはずで，量子計算の研究をしている私ですら見たことがありません．というのは，量子コンピュータは今まさに実現に向かって活発に研究されている未来型コンピュータなのです．
ではなぜそのようなコンピュータが話題になっているのでしょうか？ 現在のコンピュータの計算原理は20世紀前半にすでにイギリスの数学者であったチューリング(Alan Turing)により確立され，複雑化こそすれ今日までその原理は全く変わってないのです．ところが，その原理を根本的に変える計算概念がイギリスの物理学者ドイッチ(David Deutcsh)により20年ほど前に確立されました．それが量子計算であり，量子計算の原理で動作するコンピュータが量子コンピュータなのです．
量子コンピュータは現在のコンピュータと異なり，量子力学の原理を利用します．細かい話を始めるとキリがないので詳しい内容は他の解説書にお譲りするとして， 量子コンピュータの有り難味を一言で言うと
「今までムチャクチャ計算するのに時間がかかっていた問題が一瞬で計算できる！」
これに尽きます．特に，今からおよそ10年前に当時AT&Tベル研究所のショア(Peter Shor)が今まで非常に計算時間がかかると思われていた素因数分解問題（つまり入力として自然数が与えられたとき，素数の積に分解する問題）が量子コンピュータを用いると一瞬で解けるアルゴリズムを理論的に示しました．その素因数分解アルゴリズムはショアのアルゴリズムと呼ばれています．彼はその業績によりコンピュータサイエンスで最も栄誉のある賞のいくつかを受賞しています（1998年ネヴァンリンナ賞，1999年ゲーデル賞）．
素因数分解問題はその難しさと暗号的性質の良さから暗号プロトコルを設計するために頻繁に用いられています．実際，インターネットで最も利用されているRSA暗号は素因数分解問題の難しさをベースに設計されていますが，量子コンピュータを使えば，そのような暗号が一瞬で解読されてしまうわけです．（幸か不幸かそこまで実用的な量子コンピュータは未だ完成していません．）
ただ，残念な事に，どんな問題でも量子コンピュータにかかれば一瞬で解けるのかというそういうわけではありません．むしろ逆に，量子コンピュータで一瞬で解ける問題を見つけるのは非常に難しいことなのです．量子コンピュータはその計算原理の違いのせいで，アルゴリズムを設計する（≒量子コンピュータのためのプログラムを作成する）のが非常に困難になってしまっています．
もしあなたが量子計算の研究に挑戦して，計算が非常に難しい問題に対する量子コンピュータのための新しいアルゴリズムを作ることができれば「×××のアルゴリズム」という名前で研究者の間で呼ばれることは間違いありません．（×××には勿論あなたの名前を入れて下さい．）
実際に，量子計算の本質が非常に奥深く，既存のコンピュータのための理論と異なる議論を要求するため，その計算パワーをどうすれば活かせるのかがまだまだ良く分かっていない状況にあると言えます． ではこのような状況で何の研究をするのか？量子コンピュータのための新しいアルゴリズムを設計するといった難しい研究課題がホイホイ解決できるわけがありません．（逆に言えば，アルゴリズム一発で有名人になれるという可能性も秘めているわけですが・・・） 従って
「量子コンピュータで一瞬で解ける問題はどのような構造を持っているのか？」ということを調べることによって基礎理論を充実させるのが良いアルゴリズムを設計するための早道だと思われます．
しかもこのようなアプローチは量子コンピュータを用いても容易には解読できないような暗号を設計する上でも有効です．このような研究で量子コンピュータでも解けない問題がどのようなものかについても理解が進むからです．
というわけで，現在の量子計算には基礎理論の充実が必要不可欠であり， その研究を現在行っています．
河内亮周のトップページへ戻る．