混合状態を用いた一方向量子有限オートマトンの表現能力の考察

森下 真秀 (0151108)


1994年、Peter Shorによって素因数分解が多項式時間で行える アルゴリズムが発見されてから、 量子計算の分野の研究が盛んに行われるようになった。 計算機科学の分野では、量子チューリングマシン、量子アルゴリズム、量子回路 など多岐にわたる研究テーマがある。 量子計算モデルとして、量子有限オートマトンについても考えられてきている。

その中で、 一方向量子有限オートマトン(1-QFA)は双方向量子有限オートマトン(2-QFA)を 単純化したモデルとして考えることができ取り扱いも容易で理解しやすい。 しかし、1-QFAは一方向決定性有限オートマトン(1-DFA)に比べて 能力が劣る場合があることが知られている。 それは、最小1-DFA Mがforbidden constructionという構造を有する時、 対応する言語は1-QFAによって 確率7/9+ε(ε>0)では認識できないということである。

そこで、状態遷移関数を複数用意し、確率を導入してそれらを選択するような 1-QFAを拡張した計算モデルを考える。 このモデルは、混合状態を取り扱っており、 最小1-DFAがforbidden constructionという構造を含んでいても 7/9+ε(ε>0)よりも高い確率で認識できる 言語が存在することを示す。 さらに、言語によっては、1-QFAよりも高い確率で認識でき、 1-DFAよりも状態数の少ない混合状態を用いた 1-QFAが存在する場合があることを示す。