研究内容
量子計算量理論が主な研究対象です．量子計算は量子力学を計算原理に用いる（古典力学を計算原理とする）従来の計算とは異なる計算機構ですが，量子計算を計算量理論の観点から研究するのが，量子計算量理論です．量子計算を研究する研究室は日本にもたくさんありますが多くは物理的な研究で，量子計算量理論を主な研究対象としているのは国内では案外珍しいかも（？）です．また，周辺領域である量子情報，計算量理論なども研究しています．
最近の主要な研究トピック
量子NP
NPは（YESであることを）効率的に検証可能なYES/NO問題の全体で今日の情報科学における基本的なキーワードの１つです．NPは証明者と呼ばれる無限の計算能力を持つ人から検証者と呼ばれる現実的な能力（いわゆる多項式時間限定）しか持たない人に証拠（あるいは証明）と呼ばれる情報が送られたとき，検証者が計算問題の入力がYESならYESであることを納得できて受理，一方で入力がNOならどんな証拠らしき情報が送られてきてもYESであるとだまされず拒否と判定できるような一方向通信による検証システムとみなせます．ここで検証者が送る情報を量子情報に，検証者の能力を多項式時間限定の量子計算機に変更したのが量子NPです（専門的にはQMAと呼ばれます）．量子NPに関する成果に例えば以下があります．
量子NPの重要な未解決問題に「計算誤りの片側誤り化」があります．量子計算では計算や検証が確率的に行われるため，計算誤りを認めるのが普通ですが，量子NPにおいて入力がYESの場合に限り間違って判定しない（片側誤り）という制約のもとでも量子NPの計算能力は不変なのか？という問題は，10年以上未解決のままです．上記論文では「もし証明者と検証者が入力によらない高々一定量の量子状態（実際にはEPR対とよばれる量子状態）を事前に共有していれば計算誤りは片側誤りにできる」ということを示し，未解決問題に対する進展を与えました．(コンピュテーション研究会での発表スライドはこちら)
量子対話型証明
量子対話型証明は量子NPの一般化です．量子NPが通信プロトコルとしては証明者から検証者への一方向通信のプロトコルなのに対して，量子対話型証明は証明者と検証者の双方向通信（対話）を認めた検証システムです．量子対話型証明に関する成果には例えば以下があります．
新しいタイプの量子対話型証明として，一般化量子Arthur-Merlin証明を提案しました．これは検証者(Arthur)がEPR対と呼ばれる量子的に相関した量子ビットの対をたくさん生成して，各々の片割れを証明者(Merlin)に送るという制約を検証者から証明者への量子通信に課したものです．とくにこのタイプの量子対話型証明で通信が２回であるような場合の検証可能な計算問題のクラスについて，自然な完全問題を持つなど基本的な計算量的性質を明らかにしました．(国際会議CCC2015での発表スライドはこちら)
量子アルゴリズム
量子アルゴリズムとは文字通り量子計算機をもとにしたアルゴリズムです．量子アルゴリズムに関する成果には例えば以下があります．
偽コイン発見問題に対する量子アルゴリズムを構築しました．偽コイン発見問題とは，N枚のコインの中にk枚の偽コインがあるが表面上区別がつかないときに何回天秤を使えばk枚の偽コインすべてを発見できるかというものです．従来のアルゴリズムでは情報理論的限界によりklog(N/k)のオーダの回数は天秤を使う必要があるのですが，「量子天秤」（というと変に聞こえるかもですが実際には質問計算量という概念を使って数理モデル化します）を使った量子アルゴリズムではNによらずkの４乗根のオーダでk枚の偽コインすべてを発見できることがわかりました．(国際会議ISAAC2010の発表スライドはこちら)
他の成果については論文リストのアブストラクトなどを参照してください．また情報知にある説明もご覧ください．
過去に書いた解説や資料の一部