量子回路

すーぱーおぺれーたー続き。前回適当に書きなぐったことは、とりあえず9割くらいは間違ってなかった。

superoperatorについては、

http://www.lorentz.leidenuniv.nl/quantumcomputers/literature/preskill_1_to_6.pdf

あたりを読むと詳しく書いてあるけども、

・なんで単なるpositive mapでなく、completely positive mapなのか

物理的には、系Aと独立な系Bがあって、系Bの密度行列が時間発展しないとき、自然に定まる系A+Bの時間発展は、やはりpositive mapに決まってる。完全正値写像になる理由はそんだけ。数学的に見ると、positive map同士のテンソル積は、もはやpositive mapになるとは限らないので、都合悪いとか、operator sum representationという形式でsuperoperatorを表すためには、completely positive mapであることが必要とか、そんなのが単なるpositive mapだとダメな理由。

・なんでトレースが保存するという条件ではなく、トレースが増加しないという、より緩い条件なのか?

上にあげた文献では、トレースが保存するという条件になってるのだった。Selingerという人のTowards a Quantum Programming Languageという論文読むと、次のようなことが書いてある

In the physics literature, superoperators are usually assumed to be trace preserving,i.e., satisfying trF(A) = trA for all A (see e.g. (Preskill 1998)). In our setting, it is appropriate　to relax this condition in view of possible non-termination of programs.

しかし、トレースが保存するという条件を緩めることと、停止しない計算を扱えることに、どういう繋がりがあるのか分からない。

まあ、とりあえず、そういう感じで8割くらいは納得できた。

Haskellでの実装 in Sabryの論文。下準備編
type Vec a = a -> Complex Double
は、型aに属する値の線型結合で張られる複素ベクトル空間を表す。イメージは
Vec Bool = {a|True> + b|False> | a , b is Complex Numer}
とか、そんな感じ。Vecは殆どモナドだけども、一般には(>>=)が定義できない。これを定義するためには、Vec aの基底の集合を得る必要があって、それは、型aに属する値の全体なんだけども、Haskellではそれを取得する術はない。仕方ないので、
class Eq a => Basis a where
basis :: [a]
とか基底の全体を取得できる型クラスを定義する。BoolはBasisのinstanceで、単に
instance Basis Bool where
basis = [True , False]

で、「伝統的には」
type Lin a b = a -> Vec b
を使ってたけど、
type Super a b = (a,a) -> Vec (b,b)
使った方がよくね?という主旨らしい。Lin a bはVec aからVec bの線型写像全体で、Vec a->Vec bにしない理由は、そうすると線形でない関数まで入ってきてしまうから。線型写像は基底の行き先を決めれば全部の行き先が決まるので、a->Vec bでよい。同様に、Superの方は、意図はVec(a,a)からVec(b,b)への線型写像の全体。まあ、density matrixの棲息する空間は、波動関数の棲息する空間を二つテンソルしたものじゃなくて、波動関数の棲息する空間上のendomorphismの全体、要するに行列環と考えるべきだと思うけど、そのへんは、まあいい

さて、SuperはArrowになるよ！って書いてあるけど、Vecが厳密にはモナドでないのと同じ理由で、厳密にはArrowではないし、SuperがArrowであるという意味では、LinもArrowになるんだけど、そこは突っ込んではいけないの世界。論文では、fun2linとか書いてあるのがarrに相当する。そんな感じで、表記上は、Linでも全く同じことになって別にSuper使うことに特にメリットはない気がした。実際に、Linで同じことをやってみた

module QComp where
import Complex

class Eq a => Basis a where
 basis :: [a]

instance Basis Bool where
 basis = [True , False]
instance (Basis a,Basis b)=>Basis(a,b) where
 basis = [ (a,b) |a<-basis , b<-basis]
instance (Basis a,Basis b,Basis c) =>Basis(a,b,c) where
 basis = [(a,b,c) | a<-basis,b<-basis,c<-basis]

type Vec a = a -> Complex Double
type Lin a b = a -> Vec b

return :: (Basis a) => a->Vec a
return a =(\b->if (a==b) then 1.0 else 0.0)

bind :: (Basis a) => Vec a -> (a -> Vec b) -> Vec b
bind va f =(\b -> sum[(va a)* ((f a) $ b) |a<-basis])

vplus :: Vec a -> Vec a -> Vec a
vplus v1 v2 = (\a -> (v1 a)+(v2 a))

vminus :: Vec a -> Vec a -> Vec a
vminus v1 v2 = (\a -> (v1 a)-(v2 a))

--tensor product
(<*>) :: Vec a -> Vec b -> Vec(a,b)
v1 <*> v2 =(\(a,b) ->(v1 a) *(v2 b))

--スカラー倍
($*) :: Complex Double -> Vec a -> Vec a
pa $* v = (\a -> pa *(v a))

adjoint :: Lin a b -> Lin b a
adjoint f = (\b -> (\a -> conjugate ((f a) b)))

arr :: (Basis a,Basis b) => (a -> b) -> Lin a b
arr f = (\a -> QComp.return (f a))

(>>>) :: (Basis b,Basis c,Basis d) => Lin b c -> Lin c d -> Lin b d
f >>> g = (\b -> bind (f b) g)

first :: (Basis b,Basis c,Basis d) => Lin b c -> Lin (b,d) (c,d)
first f =(\(b,d) -> (f b) <*> (QComp.return d))

controlled :: Basis a => Lin a a -> Lin (Bool,a) (Bool,a)
controlled f = (\(b1,b2) -> (QComp.return b1) <*> (if b1 then (f b2) else (QComp.return b2)))

--controlled NOT
cnot :: Lin (Bool,Bool) (Bool,Bool)
cnot = controlled (arr not)

--Hadamard transformation
hadamard :: Lin Bool Bool
hadamard False = (1/sqrt 2) $* (vplus (QComp.return True) (QComp.return False))
hadamard True = (1/sqrt 2) $* (vminus (QComp.return True) (QComp.return False))

--なんぞこれ
phase :: Lin Bool Bool
phase False = QComp.return False
phase True = (0 :+ 1) $* (QComp.return True)

cphase = controlled QComp.phase
caphase = controlled (adjoint QComp.phase)

--toffoli Gate(合ってる?
toffoli :: Lin (Bool,Bool,Bool) (Bool,Bool,Bool)
toffoli = 
 arr (\(a0,b0,c0) -> (c0 , (a0,b0))) >>>
 (first hadamard) >>>
 arr (\(c1,(a0,b0)) -> ((b0,c1),a0)) >>>
 (first cphase) >>>
 arr (\((b1,c2),a0) -> ((a0,b1),c2)) >>>
 (first cnot) >>>
 arr (\((a1,b2),c2) -> ((b2,c2),a1)) >>>
 (first caphase) >>>
 arr (\((b3,c3),a1) -> ((a1,b3),c3)) >>>
 (first cnot) >>>
 arr (\((a2,b4),c3) -> ((a2,c3),b4)) >>>
 (first cphase) >>>
 arr (\((a3,c4),b4) -> (c4,(a3,b4))) >>>
 (first hadamard) >>>
 arr (\(c5,(a3,b4)) -> (a3,b4,c5))

で、SuperとLin、どっち使った方がいいのかっていうと、まあ、どっちでもよいと思う。シミュレータとしては、結局やることは行列の計算で、そんでもって、Superにしろ、Linにしろ遅いだろう。なので、結局どっちを使うのかはnotationをどうするかって話に過ぎなくて、そして(型を書かなければ)見掛け上はどっちも変わらない。物理的に、数学的に、どっちの定式化がいいかというと、有限自由度で考えてる限りは、別にどっちでもいいだろう。

Lin a aはユニタリーでない変換を含んでいたり、Superも実際には、Superoperatorでないものを含んでいて、そこらへんは、Haskellでは割とどうしようもない気がする。arrとか使ってコード書くと、実際には実現できない回路が書けてしまう可能性があって、論文の最後の方にごにょごにょ書いてるのは、そういうのをどうするかって話を書いてるんだと思うけど、arrとか使わず、基本ゲートを使って書くようにすれば解決する話で、まあ別段気にするほどの話でもないと思う

あと、Linは、線形代数分かる人にとっては、Arrowを理解するための結構いい例なんじゃないかと思った