TOP > 研究活動 > 研究者総覧「情報知」 > 計算機数理科学専攻 > 情報数理モデル論講座 > 西村 治道

研究者総覧「情報知」

計算機数理科学専攻

氏 名
西村 治道(にしむら はるみち)
講座等
情報数理モデル論講座
職 名
准教授
学 位
博士(学術)
研究分野
量子計算,計算量理論

研究内容

量子情報処理の計算理論的側面に関する研究
【研究の概要】

  
量子力学を情報処理に用いる研究分野(量子情報科学)において,従来の(古典力学を基礎原理とする)情報処理技術を超えて何が可能で限界はどこにあるのか,さらには量子情報処理の源となる量子力学の基本的原理(重ね合わせの原理やエンタングルメント)がどの程度有用に作用しているのかについて,主に計算理論の観点から研究している.

【研究テーマ】

量子計算モデル


量子コンピュータの能力を理論的に明らかにするうえで不可欠な量子計算モデルは,古典の計算理論同様にその計算尺度や目的に応じて様々なものが提案されている.しかしながら,量子計算モデルの場合,計算のユニタリ的制約や量子的操作を定義するパラメータの連続性など,従来の計算理論にはない問題がモデル化に際して生じることがある.このような量子特有の問題に対して妥当なモデル化を究明することで,量子アルゴリズムや量子計算量理論の土台構築を行っている.

また,計算構造を内包する量子通信といえる量子ネットワーク符号のモデルを導入し,その可能性と限界を研究している.ネットワーク符号とは,ネットワーク上で通信を行う際に中継点での情報の加工(符号化)を認めることで,より効率的な通信を可能にするという新しい通信パラダイムである.ネットワーク符号による通信の効率化は,古典通信に比して(技術的にも金銭的にも)高価な量子通信においては,ますます重要な課題であると考えられる.具体的な研究成果を1つ挙げると,補助リソースとして古典通信が利用できる場合におけるマルチプルユニキャスト型ネットワーク上での量子ネットワーク符号の構築を行った.

量子アルゴリズム

整数の素因数分解問題を多項式時間で解くShorの量子アルゴリズムに代表されるように,量子計算は古典計算には困難とされる計算の効率化が可能である.どのような問題についてどの程度の高速化が可能であるかに興味を持っていて,質問計算量や通信計算量などいくつかの量子計算モデルに対する量子アルゴリズムの開発を行っている.最近の研究では,偽コイン発見問題というよく知られた組み合わせ的問題に対して,ShorGroverなどこれまでの量子アルゴリズムとは全く異なる高速化(古典アルゴリズムの限界に対する4乗の高速化)を持つ量子アルゴリズムを構築した.


量子計算量理論

量子情報処理で効率的に実行可能なタスクの範囲を明らかにすることは,得られた量子アルゴリズムの最適性や計算量的暗号の量子計算に対する安全性の観点から重要な課題である.量子計算量理論では,様々なタスクに応じて問題の計算量クラス(量子計算量クラス)が導入されているが,量子コンピュータにより多項式時間で計算可能な問題のクラス(Pの量子版)だけでなく,量子コンピュータにより多項式時間で検証可能な問題のクラス(NPの量子版)や,量子通信を用いた対話による検証(量子対話型証明)が可能なクラスについて,その包含関係や基本的性質などを研究している.また,量子コンピュータでも困難とされる問題を利用した公開鍵暗号など暗号への応用にも興味を持っている. 

経歴

  • 2001年名古屋大学大学院人間情報学研究科博士課程修了
  • 2006年大阪府立大学理学系研究科講師
  • 2012年名古屋大学大学院情報科学研究科准教授

所属学会

  • 日本数学会

主要論文・著書

  1. H. Nishimura, M. Ozawa, Computational complexity of uniform quantum circuit families and quantum Turing machines, Theoretical Computer Science 276(1-2), pp.147-181 (2002).
  2. M. Hayashi, K. Iwama, H. Nishimura, R. Raymond, S. Yamashita, Quantum network coding, in Proceedings of 24th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2007), Lecture Notes in Computer Science 4393, pp.610-621 (2007).
  3. H. Kobayashi, F. Le Gall, H. Nishimura, M. Roetteler, General scheme for perfect quantum network coding with free classical communication, in Proceedings of 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), Lecture Notes in Computer Science 5555, pp. 622-633 (2009).
  4. K. Iwama, H. Nishimura, R. Raymond, J. Teruyama, Quantum counterfeit coin problems, Theoretical Computer Science 456, pp.51-64 (2012).