量子アルゴリズムによる近似文字列出現頻度問い合わせ

概要

論文の詳細を見る
本研究では文字列出現頻度問い合わせに対する量子アルゴリズムを考察する.これは,入力としてテキストTとパターンPが与えられたとき,T中にPが出現する回数を求める問題である.文字列探索の量子アルゴリズムでは,時間計算量がO^^〜(√<n>+√<m>)であることが過去の研究により示されている.ここで,n,mはそれぞれT,Pの長さである.対して,古典アルゴリズムによる時間計算量は,KMP法によりO(n+m)である.上記問題の解決にあたり,入力として、ある小さい確率以下で誤りを含む0/1のデータ列が与えられたとき,データ列中の1の数を求める問題について考察する.この問題に対して通常の数え上げをそのまま適用しても,計算過程で誤りが起きるために正しい数え上げが出来るかどうか保証はない.本研究では,majority votingにより誤りを高確率で吸収することで,量子数え上げを文字列出現頻度問い合わせで適用できるようにした.これを用いて時間計算量の考察を行う.また,ミスマッチ許容文字列探索及び数え上げに対する量子アルゴリズムも設計し,時間計算量を考察する.
2004-12-03