Deutschによって初めて量子計算の数学的モデルが提案されて以来,多くの研究によって量子計算の古典計算に対する計算能力の優位性が示されてきた.その代表例が,Shorの素因数分解アルゴリズムである.一方で,計算モデルによっては,その量子モデル版を考えても優位性が得られない場合や,逆に古典モデルより能力が弱くなってしまう場合があることも知られている.さらに,対話型証明のように高等なモデルや有限状態オートマトンのように能力が制限されたモデルにおいては,量子モデル化がどのような効果をもたらすかが不明な場合が多く,このようなモデルの量子版の能力を解析することは,量子計算が古典計算に比べどの程度優れているのか,あるいは,どのような状況下で量子計算が優位性を発揮できるのか,といった疑問を解明する糸口として重要と考えられる.そこで,本論文では,対話型証明に関連深い計算モデルとしては,多証明者対話型証明に,有限状態オートマトンに関連深いモデルとしては,カウンタオートマトンにそれぞれ焦点を当て,その量子版の能力を解析する.

　証明者が一人だけの対話型証明に関しては,その量子版がWatrousによって定義され,複数の研究により,古典モデルより強力なことを示すいくつかの性質が分かっている.しかしながら,証明者が複数いる場合のモデルの量子版はこれまで未定義であるため,本論文ではまず,量子多証明者対話型証明の定義を,Watrousの定義を拡張することにより与える.量子多証明者対話型証明としては,証明者間に事前の量子相関を許す場合と許さない場合の二つの自然なモデルが考えられる.本論文では特に後者に焦点を当て,証明者間に事前の量子相関のない量子多証明者対話型証明を持つ言語クラスが古典計算量クラスNEXPと一致することを示す.この結果は,証明者が一人の場合とは対照的に,多証明者対話型証明においては,証明者間の事前量子相関がなければ,量子モデルと古典モデルの間に計算量的な能力の差が出ないことを意味する.これに関連して,証明者が一人だけの対話型証明においても,証明者が自分だけが扱える量子空間を持たない場合には,量子対話型証明を持つ言語クラスはNEXPと一致することも示す.これらの結果は,古典計算量のクラスを量子計算の観点から正確に特徴付けた数少ない例の一つとしても非常に興味深い.さらに,証明者間に高々多項式で抑えられる数の量子ビット数の事前量子相関を許しても,量子多証明者対話型証明を持つ言語クラスはNEXPに含まれることも示す.

　これらの結果とは対照的に,本論文ではさらに,以下のような多証明者対話型証明の特殊な場合,つまり,証明者達が検証者に最初に各1回のみ証拠を送り,検証者には質問が許されない場合には,量子モデルと古典モデルと古典モデルの間に構造的な違いがあることを指摘する.この場合,古典モデルにおいては,証明者が複数いることと一人だけいること,つまり,証拠が複数送られることとただ一つのみ送られることは本質的に同等である.しかしながら,量子モデルにおいては,証拠が量子状態として複数独立に送られる場合,全体としての証拠列は各証拠のテンソル積として表されるため,検証者はそのテンソル積の構造を検証に利用できる可能性がある.この理由から,量子モデルにおいては,証拠が複数送られることとただ一つのみ送られることは本質的に異なると考えられる.そこで本論文では,証拠が複数送られる場合の検証者の計算能力をさらに追求し,任意の定数kに対し,k個の量子状態の証拠を受け取って"no"側の片側有限誤り確率で効率的に検証できる言語は,2個の量子状態の証拠を受け取るのみでも"no"側片側有限誤り確率で検証できることを示す.また,正確な検証や"yes"側片側誤りでの検証の場合には,量子証拠を複数利用しても検証能力は変わらないことも示す.さらに,量子証拠を用いて正確に検証可能な,あるいは"yes"側片側誤りで検証可能な言語クラスは,NPのもう一つの量子的一般化であるクラスNQPに含まれることも示す.

　一方,能力が限定されたモデルであるカウンタオートマトンに関しては,本論文では1方向1カウンタオートマトンと2方向1カウンタオートマトンの二つを考える.1方向1カウンタオートマトンに関しては,その量子版がKravtsevによって定義され,いくつかの非文脈自由言語を有限誤り確率で認識できることが示されている.本論文では,1方向量子1カウンタオートマトンの性質をさらに解明するために,その能力を1方向決定性1カウンタオートマトン,及び,1方向確率可逆1カウンタオートマトンと比較する.本論文ではまず,新たな非文脈自由言語の族{Leq(k)},〓,〓,が1方向確率可逆1カウンタオートマトンで有限誤り確率で認識できることを示し,さらに量子干渉効果をうまく用いることにより,1方向量子1カウンタオートマトンで受理確率を改善できることを示す.一方で,1方向量子1カウンタオートマトンでは有限誤り確率で認識できない正則言語Llast={{a,b}*a}の存在も示す.これらの結果は,ごく最近にBonner, Freivalds, Kravtsevによって得られた,1方向量子1カウンタオートマトンでは有限誤り確率で認識可能だが,1方向確率1カウンタオートマトンでは有限誤り確率では認識できない言語の存在を示す結果と合わせて,1方向量子1カウンタオートマトンと各古典1方向1カウンタオートマトンの間の認識可能な言語クラスの関係を完全に解明する.

　さらに,本論文では,2方向量子1カウンタオートマトンを定義し,その能力を2方向決定性1カウンタオートマトンと比較する.まず,カウンタ用のテープの長さが有界であれば,2方向決定性1カウンタオートマトンが2方向可逆1カウンタオートマトンで模倣可能なことを示し,さらに,2方向決定性1カウンタオートマトンでは認識できない非文脈自由言語〓と〓が,2方向量子1カウンタオートマトンで任意に小さい"no"側片側定数誤り確率で,多項式時間内に認識可能なことを示す.すなわち,有界な長さのカウンタテープを用いた実際的なモデルにおいては,2方向量子1カウンタオートマトンは2方向決定性1カウンタオートマトンより真に強力であることが示される.他にも,Lpower={amb2m|m〓1}などの非文脈自由言語が2方向量子1カウンタオートマトンで任意に小さい"no"側片側定数誤り確率で認識可能なことも示す.

　本論文は,量子計算の数学的モデルにおいて,量子モデル化が計算能力においてどのような効果をもたらすかを古典計算モデルと比較することにより明らかにしようとしたものである.計算モデルとしては,大きな計算能力をもったものとして多証明者対話型証明システム,また能力が限定されたモデルとしてカウンタオートマトンを取り上げて,その量子版の能力を解明する一連の定理を得ている.

　本論文は,7章からなり,第1章から第2章では,計算の量子化モデル全般について,その概念とこれまでに知られている結果を概観し,本論文で得られら結果の位置付けをしている.

　第3章では,Watrousによって定義された証明者が一人だけの対話型証明システムを拡張することにより,量子多証明者対話型証明システムの定義を与えている.この量子多証明者対話型証明システムでは,証明者間に事前の量子相関を許す場合と許さない場合の二つのモデルが考えられる.本論文では,まず,証明者間に事前の量子相関のない量子多証明者対話型証明をもつ言語クラスは古典計算量クラスNEXPと一致するという結果を証明している.この結果は,証明者が一人の場合とは対照的であり,多証明者対話型証明システムにおいては,証明者間の事前量子相関がなければ,量子モデルと古典モデルの間に計算量的な能力の差がないという著しい性質を明らかにしている.また,証明者が一人だけの対話型証明においても,証明者が自分だけが扱える量子空間をもたない場合には,量子対話型証明をもつ言語クラスはNEXPと一致することも証明している.これらの結果は,古典計算量のクラスを量子計算の観点から正確に特徴付けた数少ない結果ともいえる.

　第4章では,証明者達が検証者に最初に各1回のみ証拠を送り,検証者には質問が許されないという多証明者対話型証明の特殊な場合について考察している.古典モデルにおいては,証拠が複数送られることとただ1つのみ送られることは本質的に同等であるが,量子モデルにおいては,証拠が量子状態として複数独立に送られる場合,全体としての証拠列は各証拠のテンソル積として表されるため,検証者はそのテンソル積の構造を検証に利用できる可能性がある.このことに着目し,任意の定数kに対し,k個の量子状態の証拠を受け取って"no"側の片側有限誤り確率で効率的に検証できる言語は,2個の量子状態の証拠を受け取るのみでも"no"側片側有限誤り確率で検証できることなどを証明している.

　第5章と第6章では,それぞれ1方向カウンタオートマトンと2方向カウンタオートマトンの量子化モデルを定義し,1方向量子1カウンタオートマトンと各古典1方向1カウンタオートマトンの間の認識可能な言語クラスの関係を完全に解明し,2方向カウンタオートマトンについては,2方向量子1カウンタオートマトンが2方向決定性1カウンタオートマトンより真に強力であることなどを証明している.最後に第7章では,本論文の成果を総括している.

　なお、本論文の第3章から6章についての内容は,徳永裕己氏,山上智幸氏,山崎智弘氏,松本啓史氏,今井浩氏との共同研究であるが,論文提出者が主体となって分析及び検証を行ってもので,論文提出者の寄与が十分であると判断する.

　したがって,博士(理学)の学位を授与できると認める.