濃緑研の日記: 量子フーリエ変換

量子フーリエ変換

量子フーリエ変換で述べた

レジスタaが最後に示す確率振幅？は

|0>+|4>+|8>+|12>　→　1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0

と考えるのか、状態関数として
|0>+|4>+|8>+|12>+|0>+|4>+|8>+|12>+|0>+|4>+|8>+|12>+|0>+|4>+|8>+|12>
と考えるのか
この場合の例は特殊すぎてどちらも波数はたまたま4で同じだが

状態4の量子フーリエ変換を理論的に計算すると
|0>+|4>+|8>+|12>+|0>+|4>+|8>+|12>+|0>+|4>+|8>+|12>+|0>+|4>+|8>+|12>
このようになる。これをレジスタaの状態と考えていいのか？

しかしレジスタaの実際の確率振幅は
1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0

で間違いないと思う。

Nは素因数分解したい値

xとNの最大公約数が1である適切なxを選び

b = x^a mod　N

の計算に対し
aを0から1づつ増加して.実施した場合得られるbは周期性を持つことがわかっている。

量子コンピュータの場合、レジスタaを0からレジスタのビット数で表しうる最大整数までの重ね合わせ状態にして計算するとレジスタbも計算結果の重ねあわせ状態になる。

例えばNを15、xを7としてbを求めると
a=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
に対して
b=1,7,4,13,1,7,4,13,1,7,4,13,1,7,4,13
といった具合に1,7,4,13の繰り返しという周期性を持つことがわかる。

量子コンピュータの場合レジスタbは
1,7,4,13の状態の重ね合わせとして
|1>+|7>+|4>+|13>
と表現します。

レジスタbを観測するとそのうち1つの数値が観測できるわけですが
その際レジスタaはレジスタbの観測値が
1の場合
|0>+|4>+|8>+|12>

7の場合
|1>+|5>+|9>+|13>

4の場合
|2>+|6>+|10>+|14>

13の場合
|3>+|7>+|11>+|15>

といった重ね合わせ状態となり、どの場合でも同じ周期性があります。

この周期性を量子フーリエ変換で（正確には逆変換）で求めようというのです。

しかしフーリエ変換の入力データはレジスタbの状態の確率振幅でなければなりません。

例えばレジスタbの観測値が1だった場合、レジスタaの状態の確率振幅は
1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0

7だった場合
0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0

４だった場合
0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0

13だった場合
0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1

といった感じです。

どの場合もフーリエ変換すれば4が求まります。

しかしどうやったら確率振幅を入力データとすることができるのでしょう？

ってことで、この2ヶ月量子コンピュータの原理と格闘しているのですが、いまだ理解に至らず、すっきりしない日々です。