種々の制約のある量子計算機の能力の解析

量子計算機は従来の計算機（古典計算機）とは異なり，量子力学に基づく動作をする。したがって，量子アルゴリズムは従来のアルゴリズムとは根本から異なるものであり，それゆえ従来のアルゴリズムでは成し得ない高速化を達成できる。その一方で，量子計算機の実現には技術的に困難な点も多く，量子計算機が実現した初期の段階では，状態遷移やメモリの扱いに関して様々な制約が付くものと予想されている。本研究では，このような制約の下で，量子計算機がどの程度の能力を発揮するのかを，理論・実験の両面から解析することが目標である。本年度は量子カウンタオートマトンに近い性質を持つaffineカウンタオートマトンについて，誤りのない計算を行う際に，言語の認識能力や必要となる状態数について，古典計算モデルよりも優れていることを示す等，affineカウンタオートマトンとその他のモデルの能力の比較を行った。さらに，主に量子オートマトンのシミュレーションのための要素技術として，昨年度提案したGPGPU向け並列マージ処理の高速化手法の詳細な分析も行った。本手法はMergePathと呼ばれるマージ処理の分割法を応用したものであり，マージ処理を分割する際の粒度を粗くすることで，分割に要する処理時間を低減し，大域メモリのバンド幅を最大限活用できる。昨年度の成果を基に，追加実験による詳細な検証を行い，提案手法が有効に働く条件を調査した。大規模な入力に対しては限界に近い性能を持つことをすでに確認していたが，従来手法と比較した場合の優位性も含め詳細な性能比較を行った。また，提案手法は，メモリ領域の確保を不要とすることにより，要素数の小さなマージに関しても，性能の劣化が少ないアルゴリズムであるという点についても示すことができた。

量子計算機は従来の計算機（古典計算機）とは異なり，量子力学に基づく動作をする。したがって，量子アルゴリズムは従来のアルゴリズムとは根本から異なるものであり，それゆえ従来のアルゴリズムでは成し得ない高速化を達成できる。その一方で，量子計算機の実現には技術的に困難な点も多く，量子計算機が実現した初期の段階では，状態遷移やメモリの扱いに関して様々な制約が付くものと予想されている。本研究では，このような制約の下で，量子計算機がどの程度の能力を発揮するのかを，理論・実験の両面から解析することが目標である。本年度は量子カウンタオートマトンに近い性質を持つaffineカウンタオートマトンについて，誤りのない計算を行う際に，言語の認識能力や必要となる状態数について，古典計算モデルよりも優れていることを示す等，affineカウンタオートマトンとその他のモデルの能力の比較を行った。さらに，主に量子オートマトンのシミュレーションのための要素技術として，昨年度提案したGPGPU向け並列マージ処理の高速化手法の詳細な分析も行った。本手法はMergePathと呼ばれるマージ処理の分割法を応用したものであり，マージ処理を分割する際の粒度を粗くすることで，分割に要する処理時間を低減し，大域メモリのバンド幅を最大限活用できる。昨年度の成果を基に，追加実験による詳細な検証を行い，提案手法が有効に働く条件を調査した。大規模な入力に対しては限界に近い性能を持つことをすでに確認していたが，従来手法と比較した場合の優位性も含め詳細な性能比較を行った。また，提案手法は，メモリ領域の確保を不要とすることにより，要素数の小さなマージに関しても，性能の劣化が少ないアルゴリズムであるという点についても示すことができた。