Pebble Coding

ソフトウェアエンジニアによるIT技術、数学の備忘録

ドイッチのゲート

量子コンピュータの原理を調べているが、結局のところ、使っている数学は、線形代数と離散フーリエ変換くらいである。 この記事では、ドイッチのゲートの計算を確かめる。
なお、基礎的な量子論理ゲートである、アダマールゲート、制御ユニタリゲート、制御NOTゲートの知識があることを前提とする。

以下の形のものはドイッチのゲートと呼ばれている。

f:id:pebble8888:20190409213841p:plain

左側の入力が量子ビット2つ、右側の出力が量子ビット2つである。計算する際、上側を第1ビット、下側を第2ビットとする。

f(x)はxが0, 1の値に応じて0,1の値を返す任意の関数を表している。
任意とはいっても入力が2種類、出力が2種類しかないので、実質以下の4種類しかない。
パターン1: f(0) = 0, f(1)= 0
パターン2: f(0) = 0, f(1)= 1
パターン3: f(0) = 1, f(1)= 0
パターン4: f(0) = 1, f(1)= 1

示したい定理は、以下である。
入力を
| \psi_{0} \rangle = |01 \rangleとしたとき
\displaystyle | \psi_{2} \rangle = \frac {(-1)^{f(0)} |0 \rangle + (-1)^{f(1)} |1 \rangle} { \sqrt {2} } \otimes (\frac {|0 \rangle - |1 \rangle } {\sqrt {2} }) = \frac {1} {\sqrt {2}} \sum_{x} (-1)^{f(x)} |x \rangle \otimes (\frac {|0 \rangle - |1 \rangle } {\sqrt {2} }) (式A)
である。

場合の数は多くないので、4つのパターンを全て計算して、検証することが可能である。
まず、パターン1の場合を計算してみる。アダマールゲートは
H |0 \rangle = \frac {1} {\sqrt {2}} (|0 \rangle + |1 \rangle)
H |1 \rangle = \frac {1} {\sqrt {2}} (|0 \rangle - |1 \rangle)
なので、
| \psi_{1} \rangle = H | \psi_{0} \rangle = H |01 \rangle = H|0 \rangle \otimes H|1 \rangle = \frac {1} {\sqrt {2}} (|0 \rangle + |1 \rangle) \otimes \frac {1} {\sqrt {2}} (|0 \rangle - |1 \rangle) = \frac {1} {2} (|00 \rangle - |01 \rangle + |10 \rangle - |11 \rangle)
| \psi_{2} \rangle = U_{f} | \psi_{1} \rangle = U_{f} \frac {1} {2} (|00 \rangle - |01 \rangle + |10 \rangle - |11 \rangle) = \frac {1} {2} (|0, 0 \oplus f(0) \rangle - |0, 1 \oplus f(0) \rangle + |1, 0 \oplus f(1) \rangle - |1, 1 \oplus f(1) \rangle)
4つのパターンで計算してみると、
パターン1: f(0)=0, f(1) = 0
| \psi_{2} \rangle = \frac {1} {2} (|0, 0 \oplus 0 \rangle - |0, 1 \oplus 0 \rangle + |1, 0 \oplus 0 \rangle - |1, 1 \oplus 0 \rangle) = \frac {1} {2} (|0, 0 \rangle - |0, 1 \rangle + |1, 0 \rangle - |1, 1 \rangle) = \frac {1} {2} (|0 \rangle + |1 \rangle)(|0 \rangle - |1 \rangle)
パターン2: f(0)=0, f(1) = 1
| \psi_{2} \rangle = \frac {1} {2} (|0, 0 \oplus 0 \rangle - |0, 1 \oplus 0 \rangle + |1, 0 \oplus 1 \rangle - |1, 1 \oplus 1 \rangle) = \frac {1} {2} (|0, 0 \rangle - |0, 1 \rangle + |1, 1 \rangle - |1, 0 \rangle) = \frac {1} {2} (|0 \rangle - |1 \rangle)(|0 \rangle - |1 \rangle)
パターン3: f(0)=1, f(1) = 0
| \psi_{2} \rangle = \frac {1} {2} (|0, 0 \oplus 1 \rangle - |0, 1 \oplus 1 \rangle + |1, 0 \oplus 0 \rangle - |1, 1 \oplus 0 \rangle) = \frac {1} {2} (|0, 1 \rangle - |0, 0 \rangle + |1, 0 \rangle - |1, 1 \rangle) = - \frac {1} {2} (|0 \rangle - |1 \rangle)(|0 \rangle - |1 \rangle)
パターン4: f(0)=1, f(1) = 1
| \psi_{2} \rangle = \frac {1} {2} (|0, 0 \oplus 1 \rangle - |0, 1 \oplus 1 \rangle + |1, 0 \oplus 1 \rangle - |1, 1 \oplus 1 \rangle) = \frac {1} {2} (|0, 1 \rangle - |0, 0 \rangle + |1, 1 \rangle - |1, 0 \rangle) = - \frac {1} {2} (|0 \rangle + |1 \rangle)(|0 \rangle - |1 \rangle)

これで(式A)が確かめられた。

また、
H \frac {1} {\sqrt {2}} (|0 \rangle + |1 \rangle) = |0 \rangle
H \frac {1} {\sqrt {2}} (|0 \rangle - |1 \rangle) = |1 \rangle
であるから、4つのパターンで計算すると、
| \psi_{3} \rangle = |0 \rangle \otimes \frac {1} {\sqrt {2}} (|0 \rangle - |1 \rangle) = |f(0) + f(1) \rangle \otimes \frac {1} {\sqrt {2}} (|0 \rangle - |1 \rangle)
| \psi_{3} \rangle = |1 \rangle \otimes \frac {1} {\sqrt {2}} (|0 \rangle - |1 \rangle) = |f(0) + f(1) \rangle \otimes \frac {1} {\sqrt {2}} (|0 \rangle - |1 \rangle)
| \psi_{3} \rangle = - |1 \rangle \otimes \frac {1} {\sqrt {2}} (|0 \rangle - |1 \rangle) = - |f(0) + f(1) \rangle \otimes \frac {1} {\sqrt {2}} (|0 \rangle - |1 \rangle)
| \psi_{3} \rangle = - |0 \rangle \otimes \frac {1} {\sqrt {2}} (|0 \rangle - |1 \rangle) = - |f(0) + f(1) \rangle \otimes \frac {1} {\sqrt {2}} (|0 \rangle - |1 \rangle)
となるので、
| \psi_{3} \rangle = (-1) ^ {f(0)} |f(0) + f(1) \rangle \otimes \frac {1} {\sqrt {2}} (|0 \rangle - |1 \rangle)
と書けることが分かる。
これはf(x)の4パターンの加算処理をいくつかのゲートを使ってはいるが同時平行に行っていることになる。