早稲田大学 教育・総合科学学術院 教授
谷 誠一郎 (たに　せいいちろう） ORCID logo

当研究室(修士・博士課程) へ進学をお考えの方へ

教育タブに諸注意がありますので必ず確認してください．

担当講義

→教育のタブへ

研究専門分野

理論計算機科学(Theoretical Computer Science, TCS)を研究分野としています．現在は特に，量子アルゴリズムと量子計算量理論に関する研究に取り組んでいます．
（以下は，概略です．詳細は，研究内容のタブを見てください）．

理論計算機科学は，「計算」を数学的な定義することから始まり，「何が計算可能なのか」，さらに「計算をどの程度効率よく行えるのか」という問題を探求してきた学問分野です．これらの研究を通じて，情報処理や通信に関する技術の数理的基盤が築かれてきました．TCSの未解決問題としてP対NP問題はよく知られていますが，その研究対象ははるかに広大です．例えば，暗号の安全性の理論的基盤や，効率的な通信ネットワークや通信プロトコルの設計，電子回路の最小化・省電力化など，現代の情報化社会をささえる多くの技術の背後には理論計算機科学があります．

コンピュータ技術は日進月歩で発展していますが，その基本原理はまったく変わっていません．そのため，TCSの研究において前提とされてきた計算の数理モデルも，ながらく普遍的なものとして扱われてきました．しかし，約40年前に，量子力学の原理に基づく新しい計算モデルとして，量子コンピュータが提案され，TCSの研究でも新たな計算の枠組みが導入されました．近年では，理論研究の分野にとどまらず，世界中の政府機関・大学・企業が，量子コンピュータの実機開発にしのぎを削っています．

では，なぜ量子コンピュータがこれほど注目されているのでしょうか．

それは，現在普及しているコンピュータ（以下、古典コンピュータ）の延長線上では達成し得ない計算能力を，量子コンピュータは実現する可能性をもつと期待されているからです．しかし，実際のところ，量子コンピュータが完成したとしても，あらゆるの問題を高速に解けるわけではありません．したがって，どんな問題であれば，古典コンピュータよりも高速に解けるのか，という問いが重要になります．この問いに対する答えを求めて，量子コンピュータによる計算を数学的に定式化し，その計算能力を理論的に解明する研究が進められてきました．

理論計算機科学を構成する主要な分野として，アルゴリズム理論と計算量理論があります(両者は相互に関係が深く，明確な境界があるわけではありません)．以下では，この二つの観点から量子計算研究について簡単に説明してみます．

量子アルゴリズム

ターゲットとする問題に対して，量子コンピュータを用いたアルゴリズム（＝量子アルゴリズム）を考案し，その問題を高速に解くことを数学的に保証することは，上記の「問い」に対する王道的アプローチといえます．少し視点を変えて，問題が「暗号を解読すること」であった場合はどうなるでしょうか．この場合，高速な量子アルゴリズムは暗号への攻撃手法という位置付けになります．例えば，P. Shorにより1994年に発表された素因数分解を行う量子アルゴリズムは，現在使用されているRSA暗号に対する強力な攻撃手法となります．これは一見すると悪いことのように思えますが，暗号への強力な攻撃手法は，暗号の安全性解析を行うための大事なツールとなり，暗号をより安全に改良していくために欠かせません．

高速な量子アルゴリズムを考案するためには，量子特有のテクニックはもちろん必要ですが，多くの場合，古典コンピュータのTCSで培われた高度なアルゴリズム技術の知識も必要とします．また，古典コンピュータ上でのアルゴリズム（＝古典アルゴリズム）よりも，考案した量子アルゴリズムが高速であることを示すためには，古典アルゴリズムの限界を示す必要があります．この意味で，量子アルゴリズムの研究は，古典アルゴリズムの研究と深い関係を持っていると言えます．

量子計算量理論

具体的な問題ごとに高速に計算できるかどうかを示すことは，最終的には必要ですが，その前段階として，同様の性質を持つ問題群に対して，解くために必要な時間やメモリ量に関する共通の性質を明らかにするというのが計算量理論のアプローチです．これによって，問題に対する対処の仕方に関して，おおまかな方針が立てられるという利点があります．例えば，応用上重要な問題が，NP困難というクラスに属することが示されると，それを高速に解くことが極めて困難であることの状況証拠になります．そのため，厳密に解くことはあきらめ，近似解法やヒューリスティックを用いる方針に転換することができます．また，高速に解くことが困難とされる問題群に属する問題を基礎として暗号を構成することができれば，解読が困難であることの理論的根拠を与えることができ，数学的に説得力のある安全性を担保できます．

私の研究分野に関して

学生時代から理論計算機科学（TCS）の研究に取り組み，その後，約10年を経た頃から現在に至るまで，主に量子計算に関するTCSの分野(量子アルゴリズム・量子計算量理論)で研究を行っています．とは言え，上述の通り，量子TCSと古典TCSは非常に深い関係があり，実質的には古典のTCSも併せて研究していると言えるかもしれません．一方で，量子TCSの分野は，量子情報理論や線形代数・抽象代数・関数解析など，他の数学分野とも深い関係があります．さらに，近年では，理論物理学との関係も指摘されています．このように，量子TCSは，様々な数理科学分野との豊かなつながりがあるため，学術的な興味が尽きることのない奥深い分野です．また，言うまでもなく，社会的要請のある課題に対する理論的側面からの貢献も期待されています．

苦労して生み出した成果がテクノロジーの進化によって陳腐化することなく，長い年月を経ても輝き続ける可能性があることが，理論研究の大きなの魅力の一つだと考えています．