漸く実装を見ていく。その前に Simon's Algorithm がとても分りやすく感じるのでこれをみてから実装に入るのが良いだろう。
tools/__init__.py#L26-L41 で定義された simon_oracle がなかなか。textbook での $Q_f$、書籍での $U_f$ にあたるものだ。書籍のコードでは one_to_one_oracle と two_to_one_oracle として実装されている。
まずは textbook のサンプルから見よう。簡単のため、手計算の $b=11$ に合わせてコードを b = '11' に書き換える。作られる回路図は以下のようなものであった:
textbook の手計算の回路図とは異なるので simon_oracle が期待する動きをしているのか確認する。まず、
\begin{align*}
\ket{\psi_1} = \ket{00}_1\ket{00}_2
\end{align*}
で初期化される。1 個目のレジスタにアダマールゲートを適用して
\begin{align*}
\ket{\psi_2} = \frac{1}{2}(\ket{00}_1 + \ket{01}_1 + \ket{10}_1 + \ket{11}_1)\ket{00}_2
\end{align*}
が得られる。ここまでは同じだ。$Q_f = CX_{1_b 2_a} CX_{1_b 2_b} CX_{1_a 2_a} CX_{1_b 2_b}$ として simon_oracle が実装されているので、
\begin{align*}
\ket{\psi_3} = \frac{1}{2}(\ket{00}_1 \ket{00}_2 + \ket{01}_1 \ket{01}_2 + \ket{10}_1 \ket{01}_2 + \ket{11}_1 \ket{00}_2)
\end{align*}
を得る。1 個目のレジスタに着目すると、$00 \oplus 11 = 11$ と $01 \oplus 11 = 10$ であることから、$\ket{00}_1$ と $\ket{11}_1$ に対応する 2 個目のレジスタ、および $\ket{01}_1$ と $\ket{10}_1$ に対応する 2 個目のレジスタがそれぞれ一致していれば 2-to-1 のオラクルの問い合わせ関数であることになる。これはそれぞれ $\ket{00}_2$ と $\ket{01}_2$ で一致しているので、確かに問い合わせ関数になっている。後の流れは 2 個目のレジスタを測定して〜という話につながる。
実際のコードでは測定せずに、1 個目のレジスタにアダマールゲートを適用している。
\begin{align*}
\begin{cases}
H^{\otimes 2} \ket{00} &= \frac{1}{2} (\ket{0} + \ket{1}) (\ket{0} + \ket{1}) &= \frac{1}{2} (\ket{00} + \ket{01} + \ket{10} + \ket{11}) \\
H^{\otimes 2} \ket{01} &= \frac{1}{2} (\ket{0} + \ket{1}) (\ket{0} - \ket{1}) &= \frac{1}{2} (\ket{00} - \ket{01} + \ket{10} - \ket{11}) \\
H^{\otimes 2} \ket{10} &= \frac{1}{2} (\ket{0} - \ket{1}) (\ket{0} + \ket{1}) &= \frac{1}{2} (\ket{00} + \ket{01} - \ket{10} - \ket{11}) \\
H^{\otimes 2} \ket{11} &= \frac{1}{2} (\ket{0} - \ket{1}) (\ket{0} - \ket{1}) &= \frac{1}{2} (\ket{00} - \ket{01} - \ket{10} + \ket{11})
\end{cases}
\end{align*}
に注意すると最終的に
\begin{align*}
\ket{\psi_\mathrm{final}} = \frac{1}{2}(\ket{00}_1 \ket{00}_2 + \ket{11}_1 \ket{00}_2 + \ket{00}_1 \ket{01}_2 - \ket{11}_1 \ket{01}_2)
\end{align*}
が得られる。よって、1 個目のレジスタとしては 2 個目のレジスタの測定結果によって $\frac{1}{\sqrt{2}}(\ket{00} \pm \ket{11})$ という状態なので、1 個目のレジスタを測定すると $\ket{00}$ か $\ket{11}$ が 50% ずつ観測されることになる。
シミュレータの結果は以下のようになっていた:
これらの観測結果は秘密ビット列 $b = 11$ と要素ごとの積の XOR をとると 0 になるはずだが、実際
\begin{align*}
\begin{cases}
b \cdot 00 &= 11 \cdot 00 &= 0\cdot 0 \oplus 0\cdot 0 &= 0 \\
b \cdot 11 &= 11 \cdot 11 &= 0\cdot 0 \oplus 1\cdot 1 &= 0 \\
\end{cases}
\end{align*}
で理論に符合していることが分かる。2-to-1 のケースについては textbook のコードも書籍のコードも $b$ の長さに応じて回路図は見た目がややこしくなるが、オラクルの問い合わせ関数部分をブラックボックスとして見なかったことにすれば同じことである。
