アダマールゲート
スピンなんかのZ軸の上向き・下向きを基底にとって、それらを \( \Ket{0} \) と \( \Ket{1} \) で書くことにする。 このとき、アダマールゲート (Hadamard) \( H \) は、\[ H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \] とかける。これによって、たとえば、\[ \Ket{0} \to \frac{1}{\sqrt{2}} \left( \Ket{0} + \Ket{1} \right) \] と変換される。
次に、 \( n \) 量子ビットを考えることにする。初期状態としてすべて \( \Ket{0} \) である量子ビットを考えるとすると、$$ \bigotimes_{n} \Ket{0} = \Ket{0}^{\otimes n}$$ とテンソル積を使って表現することができるが (右辺は左辺を以下こう書くという意味)、この\( n \)量子ビットを\( 1 \) ビットずつそれぞれアダマールゲート \( H \) を作用させると、$$ \begin{equation} \begin{split} H^{\otimes n} \Ket{0}^{\otimes n} &= \bigotimes_{n} \left[ \frac{1}{\sqrt{2}} \left( \Ket{0} + \Ket{1}\right) \right] \\ &= \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} \Ket{k} \end{split} \end{equation}$$ と書け、そうだなあといつも思う。
いつもわからなくなるのはここからで今日のテーマにしたい。もういっかいアダマールゲートを作用させてみることを考える。すなわち、$$ H^{\otimes n} \left( H^{\otimes n} \Ket{0}^{\otimes n} \right) = H^{\otimes n} \left( \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} \Ket{k} \right) $$ を計算していきたい。
式は \(k \) の総和なので、とりあえず \( k = y \) となる \( y \) の項を考えてみる。まず第\( 1 \) ビット目から考えていくと、もし \( \Ket{0} \) であれば、\[ \Ket{0} \to \frac{1}{\sqrt{2}} \left( \Ket{0} + \Ket{1} \right) \] と変換され、もし\( \Ket{1} \) であれば、\[ \Ket{1} \to \frac{1}{\sqrt{2}} \left( \Ket{0} – \Ket{1} \right) \] と変換される。
ここでの気づきは、とりあえず \( \frac{1}{\sqrt{2^n}} \) が係数としてまた出てくること、\( \Ket{0}\) だろうが \( \Ket{1}\) だろうが \( H^{\otimes n} \Ket{y} \) からは \( \sum_{x=0}^{2^n-1} \Ket{x} \) みたいな項が出てくるということだ。
ただ注意しないといけないのは符号である。\( \Ket{1} \) に\( H \) を作用させると、上で見た通り、作用後の \( \Ket{1} \) に対して\( -1 \) の係数がひとつでる。そこで次は、展開後の \( \Ket{x} \) それぞれに対して、符号がどうなるかを考えてみることにする。
\( \Ket{x} \) の符号が \( + \) か \( – \) かを考えるときには、\( \Ket{x} \) に含まれる \( \Ket{1} \) が 「もともと \( \Ket{0} \) に \( H \) を作用させたときのもの」か、「もともと \( \Ket{1} \) に \( H \) を作用させたときのもの」かを鑑別すればよい。その考えを一歩進めれば、\( \Ket{x} \) に含まれる \( \Ket{1} \) と、\( \Ket{y} \) に含まれる \( \Ket{1} \) の位置がまったく同じ場合だと \( -1 \) がひとつ出てくることがわかる。そしてその個数を数え、奇数個なら \( -1 \) だし、偶数個なら \( +1 \) が \( \Ket{x} \) に対する係数になることがわかる。
ここで唐突だが XOR演算を考えることにする。XOR演算は排他的論理和と呼ばれるもので、記号だと \( \oplus \) で表記されることが多い。真偽表だと下記の通り。
| 0 | 1 | |
| 0 | 0 | 1 |
| 1 | 1 | 0 |
XOR演算は競技プログラムでもよくつかわれるもので、代数的に言えば下記の特徴がある
- 可換である。\( a \oplus b = b \oplus a \)
- 結合律を満たす。\( \left( a \oplus b\right) \oplus c = a \oplus \left( b \oplus c\right) \)
- \( 0 \) を中立元 としてもつ。 \( a \oplus 0 = a \)
- 自身を逆元としてもつ。 \( a \oplus a = 0 \)
すると、いま古典的な \( n \) ビットに対して、\( \bigoplus_{k} b_{k} \) (ただし \(b_{k}\) は \(k\)ビット目の数字 \(0 or 1\) を表すものとする) を計算すると、\( 0 \) は中立元のため無視できること、\( 1 \) が2個あると \( 0 \) と中立元になって無視できることを踏まえると、\( 1 \) の個数が奇数個の場合には \( \bigoplus_{k} b_{k} = 1 \) であるし、偶数個の場合には\( \bigoplus_{k} b_{k} = 0 \) であることがわかる。以上から、$$ x \cdot y = \bigoplus_{k} x_k y_k $$ というものを考えると ( \(x_k y_k\) は掛け算と思っても、AND演算と思ってもよい)、$$ \left( -1 \right)^{x \cdot y} $$ はまさに \( \Ket{x} \) に対する係数になることがわかる。
ということでずいぶん長くなってしまったが、$$ \begin{equation} \begin{split} H^{\otimes n} \left( H^{\otimes n} \Ket{0}^{\otimes n} \right) &= H^{\otimes n} \left( \frac{1}{\sqrt{2^n}} \sum_{y=0}^{2^n-1} \Ket{y} \right) \\ &= \frac{1}{2^n} \sum_{x=0}^{2^n-1} \sum_{y=0}^{2^n-1} \left( -1 \right)^{x \cdot y} \Ket{x} \end{split} \end{equation}$$ となることがわかる。
これけっこうよく出てくるんだけど、いつもすぐわからなくなっちゃうんだよねえ。