量子オートマトンの空判定は決定丌能だったり可能だったりする
稲葉 一浩 (k.inaba)
http://www.kmonos.net/
2010/01/16 第4回決定丌能の会

参考文献• V. D. Blondel, E. Jeandel, P. Koiran, and N. Portier"Decidable and Undecidable Problems
about Quantum Automata“
SIAM J. Comput. 34-6, pp. 1464-1473 (2005)
http://arxiv.org/abs/quant-ph/0304082

量子オートマトンとは何か（いくつかの定義がある。この論文での定義）• n 状態の量子オートマトン (QFA) とは– n次元行ベクトル s– n×n ﾕﾆﾀﾘ行列 Xa, Xb, … (文字が {a,b,…}の時)– n×n 射影行列 P– 閾値λユニタリ = 列ベクトルが直交基底（（v1 v2 … vn） なら vi と vj の内積がIf i=j then 1 else 0 ）射影行列

量子オートマトンの例• s = (0.6 0 0.8)
状態1 と 状態3 の重ね合わせ状態
観測すると 36% の確率で状態1、 64%で3に見える• Xa =Xb =P=

100
1/√2 -1/√2 0
10001000 1000001
1/√2 1/√20000
文字 a を読んだときは状態変わらない
λ=0.5
文字 b を読んだら↑こんな感じに変わる
文字列を受理 ⇔ 読んだ後、状態1にいる確率が0.5以上!?

数学的に言うと
QFA が文字列 c1 c2 c3 … cn を受理する
if and only if(案1) || s Xc1 Xc2 … Xcn P || ≧ λ(案2) || s Xc1 Xc2 … Xcn P || ＞ λ※ ||v|| = ベクトルの長さ

今日のお話QFAの空判定問題『入力: QFA
出力: そのQFAが受理する文字列は存在するか？』は(案1) || s Xc1 Xc2 … Xcn P || ≧λならば、 決定丌能(案2) || s Xc1 Xc2 … Xcn P || ＞λならば、 決定可能

余談
量子オートマトン (QFA)

確率オートマトン (PFA)• 状態ベクトルは成分の二乗和が 1• 遷移行列はユニタリ• 状態はベクトルは成分の和が 1• 遷移行列– 列ベクトルが直交基底– 必ず逆行列がある≧λ, ≦λ 決定丌能＞λ, ＜λ 決定可能

– 列ベクトルの成分和が1– 逆行列が無いかも≧λ, ≦λ 決定丌能＞λ, ＜λ 決定丌能≧, ≦ の場合の決定丌能性方針
PCP (Post’s Correspondence Problem) に帰着• 第１回でお勉強した通り、 PCP は決定丌能• 全てのPCPのインスタンスに対して、それと空判定の答えが一致する QFA が作れる方針
• wlog. 文字が２種類 {a, b} のPCPだけ考えます
1. 「文字」をユニタリ行列にエンコード
2. 「文字列」をユニタリ行列にエンコード
3. PCPの「文字列ペア」をﾕﾆﾀﾘ行列にエンコード– これがQFAの「遷移行列」– k個ペアがあるPCP なら、文字がk種類のQFAになる

4. うまい初期状態と観測行列をとると、「PCPに解がある ⇔ ||sX…P||≦0 に！」「文字」のエンコード• Xa =
3/5 -4/5
4/5
3/5
0
000
1

Z軸周りに
θ回転

0-4/5
3/5

X軸周りにθ回転• Xb =
1000
3/5
4/5

θ534

[Swierczkowski 1958]

証明スキップマーク• 定理： 3次元軸回りの arccos(有理数) 回転は自由群を生成する （0, ±1/2, ±1は除く）• 系： Xa, Xb は自由群を生成する– 要は– Xa と Xb を違う順で掛け算すると必ず違う結果になる• 例: Xa Xb ≠ Xa Xb, Xa Xa Xb ≠ Xb Xa Xa, …

– （直感的な理由： arccos(3/5) は”切りが悪い”角度）

「文字列」のエンコード• w = c 1 c2 c3 … cn
を• Xw = Xc1 Xc2 Xc3 … Xcnにエンコード• さっきの定理より、Xw = Xu iff w = u

「文字列ペア」のエンコード• 文字列 u と文字列 v のペア (u, v)
を• Yu,v =1 Xu + Xv
2 Xu – Xv

Xu – Xv
Xu + Xv• これが QFA の「文字」

[EXERCISE]
エンコードしたペアの重要な性質• Yu,v =1 Xu + Xv Xu – Xv
2 Xu – Xv Xu + Xvと定義したとき•Yuv,wx = Yu,w Yv,x

「PCPに解がある」と同値な条件は？
• PCP { (u1,v1), (u2,v2), …, (uk,vk) } に解がある• ∃ i1…in : ui1ui2ui3…uin = vi1vi2vi3…vin

Xui1ui2ui3…uin = Xvi1vi2vi3…vin• ∃ i1…in : Xui1ui2ui3…uin - Xvi1vi2vi3…vin = 0• ∃ i1…in : Yui1ui2ui3…uin,vi1vi2vi3…vin の右上=0• ∃ i1…in : Yui1,vi1 Yui2,vi2 … Yuin,vin の右上=0• ∃ i1…in :「PCPに解がある」と同値な条件は？
• ∃ i1…in :Yui1,vi1 Yui2,vi2 … Yuin,vin の右上=0• と同値な条件を• ∃ i1…in : || s Yui1,vi1 Yui2,vi2 … Yuin,vin P ||=0
• の形で書ければ勝利！

初期状態 s の選び方

• s Yui1,vi1 Yui2,vi2 … Yuin,vin =1 Xu + Xv Xu – Xv
2 Xu – Xv Xu + Xv
(s1 s2 s3 0 0 0) ( … (s1 s2 s3)(Xu-Xv) )(s1 s2 s3) (Xu –Xv) = (0 0 0)
iff (Xu-Xv) = 0 になるように選びたい[EXERCISE]
素晴らしい初期状態• 定理: (3 0 4) Xw = (3 0 4) XuiffXw = Xu

• 証明は k に関する帰納法– {Xa, Xb, Xa-1, Xb-1} を、キャンセルしないようにk 個掛け算した行列 M は∃x1,x2,x3∈Z : (3 0 4) M = (x1, x2, x3) / 5 k
かつ
このとき x2 は(k=0の場合を除き)5で割れない• Then, (3 0 4) Xw Xu-1 = (3 0 4) iff Xw Xu-1 = I

「PCPに解がある」と同値な条件は？
• PCP { (u1,v1), (u2,v2), …, (uk,vk) } に解がある• 中略• ∃ i1…in : Yui1,vi1 Yui2,vi2 … Yuin,vin の右上=0• ∃ i1…in : || s Yui1,vi1 Yui2,vi2 … Yuin,vin P ||=0
– where s = (3/5 0 4/5 0 0 0)
P = (0 0 0 1 1 1) が対角線に並んだ対角行列• ∃ i1…in : || s Yui1,vi1 Yui2,vi2 … Yuin,vin P ||=1
– where s = (3/5 0 4/5 0 0 0)
P = (1 1 1 0 0 0) が対角線に並んだ対角行列ここまでに示されたこと• QFA に対して、–{w | ||s Xw P||≦0} の空判定は決定丌能
–{w | ||s Xw P||≧1} の空判定は決定丌能• ここまでの構成から、s, X, P の成分を全て有理数に限っても決定丌能[EXERCISE]
0, 1 以外の受理境界• 系：任意の有理数λに対し、–{w | ||s Xw P||≦λ} の空判定は決定丌能
–{w | ||s Xw P||≧λ} の空判定は決定丌能• 証明：任意のQFA (受理条件:≧1) A に対し、
∀w ( wをAが受理する iff wをBが受理する )となるような QFA (受理条件: ≧λ) B が作れる
• ≦0 からの帰着も同様

こうやる

新しいQFAが無理数成分を持つのが気持ち悪い• 補題：任意のQFA (受理条件:≧1) A に対し、
∀w ( wをAが受理する iff wをBが受理する )となるような有理数成分 QFA (受理条件: ≧λ)B が作れる証明• ラグランジュの四平方定理 [Lagrange 1770]– 任意の自然数は４つ以下の平方数の和で書ける– 系： 任意の有理数は４つ以下の有理数平方の和まとめ：決定丌能性• QFA に対して、–{w | ||s Xw P||≦λ} の空判定は決定丌能
–{w | ||s Xw P||≧λ} の空判定は決定丌能–arccos(3/5) 回転のなす自由群を、PCPのための文字列のエンコードに使う

＞, ＜ の場合の決定可能性方針 （＜λの場合も全く同じ）{w | ||s Xw P||＞λ} の空判定Algorithm• ||s Xw P|| ＞λ な w が存在すれば有限時間で “No” を返し、しないなら止まらないセミアルゴリズムを不える• すべての w で ||s Xw P|| ≦λ ならば有限時間で “Yes” を返し、しないなら止まらないセミアルゴリズムを不える• 定理 [Who:19??] A と Aの補集合 が recursivelyenumerable なら A は recursive簡単な方• ||s Xw P|| ＞λ な w が存在すれば有限時間で “No” を返し、しないなら止まらない
セミアルゴリズムを不える• アルゴリズム– 文字列 w を短い順に全て試してみるだけ難しい方• すべての w で ||s Xw P|| ≦λ ならば有限時間で “Yes” を返し、しないなら止まらない
セミアルゴリズムを不える• 方針：– 「 ||s Xw P|| ≦λ な w が存在」と同値な一階述語論理の論理式（が有限回で現れる無限列）を作る– 定理 [Tarski1951] : 実数体上の一階述語論理は決定可能 （via quantifier elimination）

同値な条件• すべての w で ||s Xw P|| ≦λ• ∀X∈ξ: ||s X P|| ≦λ– where ξ = {Xa と Xb の生成するモノイド}• ∀X∈clo(ξ): ||s X P|| ≦λ– where clo(ξ) = ξの閉包 = {x | ∀ε∃y∈ξ: ||y-x||<ε}
why? ←は明らか。
→は、||s・P|| が連続より ||s clo(ξ) P|| ⊆ clo( ||sξP|| )∴ ||sξP|| ≦λ  clo( ||sξP|| )≦λ ||s clo(ξ) P|| ≦λ※ 注意
• ||sξP|| ≦λ clo( ||sξP|| )≦λ ||s clo(ξ) P|| ≦λ• ここが、前半の決定丌能な場合との唯一の違い||sξP|| ＜λ  clo( ||sξP|| )＜λは成り立たない！

閉包をとると何が嬉しいか:モノイドが群に• 定理: clo(ξ) はコンパクト群• 証明:– Fact: コンパクト ＝ 点列コンパクト ＝ 有界閉集合– clo(ξ)は明らかに有界で閉なので、コンパクト。
– 点列コンパクト = 任意の点列が収束部分列を持つ– X∈clo(ξ) に対し X0, X1, X2, … は収束部分列を持つ– つまり ∀ε＞0, ∃i＜k, || Xi – Xk ||＜ε
– このとき両辺に X-i-1を掛けて、 || X-1 – Xk-i-1 ||＜ε
– つまり X-1 に任意に近いclo(ξ)の元がとれる。
– よって X-1 ∈clo(ξ)

コンパクト群になると何が嬉しいか• 定理 [Who ????]
行列のコンパクト群 G は多項式で特徴付けられる
具体的には、(実数係数)多項式集合
RG = {f(X) | f(I) = 0 & f(gX)=f(X) forall g in G}をとったとき、G の元はそのゼロ点
g ∈ G iff ∀f∈RG. f(g)=0※実数係数： 実際は、有理数係数のものに限っても成り立つらしい→ RG(の有理数係数のsubset)はrecusively enumerable

多項式で特徴付けられると何が…
• 仮に
RG = {f(X) | f(I) = 0 & f(gX)=f(X) forall g in G}
これが有限基底を持つとする
i.e, f1～fn があって、 RGの元はその結合で書ける• ∀X∈clo(ξ): ||s X P|| ≦λ– where clo(ξ) = ξの閉包

• ∀X: ( f1(X)=0 & … & fn(X)=0 → ||s X P|| ≦λ)– where f1 .. fn は Rclo(ξ) の有限基底
一階述語論
理の式！

ヒルベルトの基底定理（の系）• 定理 [Hilbert 1888]
実数係数多項式環はネーター環である※ネーター環の定義：
イデアルの上昇列 I1 ⊆ I2 ⊆ I3 ⊆…
が必ず有限長 … In ＝ In+1 ＝ In+2 ＝…
※イデアルの定義：∀a,b∈I, a+b∈I かつ ∀x∀a∈I, xa,ax∈I• RG ={f1,f2,…} はイデアル。Ik を{f1, …, fk} の生成するイデアルとすると、↑より、以下のようなnが存在 ∴有限基底
I1 ⊆ I2 ⊆ I3 ⊆… In ＝ In+1 ＝ In+2 ＝ RG

まとめ：決定可能性
文字列 w を順に試す。
||s Xw P|| ＞ λNoで。それ以外
では停止しない

n=1,2,… に対しFO論理式∀X: f1(X)=0 &…& fn(X)=0
 ||s X P ||≦ λYesなら。それ以外では停止しない
実閉体の決定可能性
個々の式の真偽は決定可能

ξ := {Xa, Xb} の生成する半群
clo(ξ) := コンパクト群になる∀X∈clo(ξ) : ||s X P ||≦ λでYes。それ以外では停止しない

行列コンパクト群の性質
Rclo(ξ) = {f1, f2, …} が存在して、g∈clo(ξ) と ∀i fi(g)=0 が同値

ヒルベルトの基底定理
Rclo(ξ) の有限基底 {f1,…,fn} が存在しg∈clo(ξ) と ∀i≦n. fi(g)=0 が同値
nが幾つか不明なので順に試す

おまけ• その他にこの論文にあった結果– 文字が 2 種類のQFAの空判定(≦)も決定丌能
• PCPへの帰着だと「ペア7個以上のPCPが決定丌能」
しかわかっていないので、文字7種以上のQFAの決定丌
能性しか証明できていない• 証明はペア7個のケースを無理矢理2つの行列に押込む– 境界値 λ が「きわどい」かどうかも 決定可能• フォーマルに書くと∃ε＞0. ∀w. | ||s Xw P||-λ|＞ε は決定可能