Theoretical Foundations of Resource-Bounded Quantum Computation

点击翻译按钮获取中文摘要

量子計算を使用する上で本質的になると予想される３つの分野（委託量子計算・分散量子計算・単体量子計算）について研究を進めた．委託量子計算分野に関しては，セキュリティの基礎となる，一方向性関数，コミットメント，電子署名等に関する成果を得た．具体的には，古典暗号の場合は一方向性関数が最も基礎的な仮定であるが、量子を用いた暗号の場合は必ずしもそうではないことを示した。特に、量子通信をもちいたコミットメント、電子署名について、一方向性関数よりも弱い仮定と考えられている疑似ランダム量子状態を用いて構成した。また、古典では構成方法が知られていない仮定から公開鍵暗号を構成する方法を提示し，さらに，コミットメントの安全性の等価性を示した。分散量子計算の分野では，量子非対話型証明および量子対話型証明についてネットワーク上に量子計算機が分散的に存在するような環境（分散的環境）での研究を進めた．分散型量子対話型証明においては通常の分散的でない場合と同様に，一般的なプロトコルを定数ラウンドのプロトコルに変換する方法を示すことができた．また分散型量子非対話型証明においては量子状態生成の検証という新しい文脈で効率的なプロトコルを開発した．単体量子計算の分野では，グラフ彩色問題に対する指数時間量子アルゴリズムを開発した。現在知られている最速の古典アルゴリズムは n 頂点グラフの彩色数の計算に Ω(2^n) 時間かかる。本研究では O(1.914^n) 時間の量子アルゴリズムを開発した。また、無線通信における最適化問題を効率的に解く量子アルゴリズムを提案した。さらに，使用可能な量子メモリ量に制限がある場合において，ポストセレクションを任意のタイミングで許しても，計算の最後にのみ許した場合と比べて計算能力に変わりがなく，量子メモリ量の制限が計算能力に本質的に大きな影響を与えることを示す結果を得た．