この記事に関して
ここではpythonライブラリのblueqatを用いて量子プログラミングを行っていこうと思います。
内容は公式のチュートリアルを元に作成しています。
今回はDeutsch-Jozsaのアルゴリズムを実装していきます。
Deutsch-Jozsaのアルゴリズム
詳しい内容はここに書いてます。
今回は Oracle が2量子ビットの実装を行います。
このアルゴリズムでは Oracle が下の1. か 2. かを判別するアルゴリズムです。
全ての入力で $f(x)$ が同じ
→ 全ての $x$ で $f(x)=0$ または 全ての $x$ で $f(x)=1$入力の半分で $f(x)$ が異なる
→ $2^{n−1}$ 個の $x$ で $f(x)=0$ 、残りの $x$ で $f(x)=1$
今回は 1. ならば 00 が 2. ならば 10, 01, 11 のどれかが取れます。
2 の場合を考えます。
回路の作成には Oracle の結果を出力させるビットを加えた 3量子ビット使います。
\left|0\right> \otimes \left|0\right> \otimes \left|1\right>
また Olacleを出力させるビットは $\left|1\right>$ にしておきます。
始めに重ね合わせの状態を作ります。
\left|0\right> \otimes \left|0\right> \otimes \left|1\right> \xrightarrow{H \otimes H \otimes H} \frac{1}{2}(\left|00\right> + \left|01\right> + \left|10\right> + \left|11\right>) \otimes \frac{1}{\sqrt2}(\left|0\right> - \left|1\right>)
ここでは Oracle を CXゲートします。
\left|00\right> \xrightarrow{CX} \left|00\right>, \left|01\right> \xrightarrow{CX} \left|01\right>\\
\left|11\right> \xrightarrow{CX} \left|10\right>, \left|10\right> \xrightarrow{CX} \left|11\right>
Oracle の出力を 1 番目のビットと見ると 0 から 1 番目に CX ゲート を施したとき 01, 10 で 1番目のビットが 1 になりますので Deutsch-Jozsaのアルゴリズムが使えることがわかります。
この出力を 2番目のビットに送るので以下のようにします。
\frac{1}{2}(\left|00\right> + \left|01\right> + \left|10\right> + \left|11\right>) \otimes \frac{1}{\sqrt2}(\left|0\right> - \left|1\right>)\\ \xrightarrow{CX[0,1]} \frac{1}{2}(\left|00\right> + \left|01\right> + \left|11\right> + \left|10\right>) \otimes \frac{1}{\sqrt2}(\left|0\right> - \left|1\right>) \\
\xrightarrow{CX[1,2]} \frac{1}{2}(\left|00\right> - \left|01\right> - \left|11\right> + \left|10\right>) \otimes \frac{1}{\sqrt2}(\left|0\right> - \left|1\right>) \\
\xrightarrow{CX[0,1]} \frac{1}{2}(\left|00\right> - \left|01\right> - \left|10\right> + \left|11\right>) \otimes \frac{1}{\sqrt2}(\left|0\right> - \left|1\right>)
これは $CX[0,1]$ で Oracleの出力を 1番目に集約して、その結果を $CX[1,2]$ で2番目に送り、また $CX[0,1]$ で中身の順番を戻すという作業をしています。
Oracle の結果で符号が反転していることがわかります。
最後に重ね合わせを戻します。
\frac{1}{2}(\left|00\right> - \left|01\right> - \left|10\right> + \left|11\right>) \otimes \frac{1}{\sqrt2}(\left|0\right> - \left|1\right>) \xrightarrow{H \otimes H \otimes H} \left|11\right> \otimes \left|1\right>
0, 1 番目のビットを見ると 11 になっているので 2. の場合の Oracleだとわかります。
回路の作成
回路は以下のようになります。
\begin{array}{cccc}
\left|0\right> &-&H&-&*&-&*&-&H&-&→出力 \\
&&&&|&&|& \\
\left|0\right> &-&H&-&X&*&X&-&H&-&→出力 \\
&&&&&|& \\
\left|1\right> &-&H&-&-&X&-&-&H&- \\
\end{array}
始めの Hゲートで重ね合わせを作っています。
次の CXゲートが Oracle です。
この Oracle の出力を $\left|1\right>$ の行に CXゲートで送って、そのあとの CXゲートで順番を戻しています。
実装します。
from blueqat import Circuit
c = Circuit().x[2].h[:]
c.cx[0,1].cx[1,2].cx[0,1]
c.h[:].m[:].run(shots=1000)
出力
Counter({'111': 1000})
11 が取れたのでこの Oracleは 2. の場合だとわかります。
まとめ
今回はblueqatを用いてDeutsch-Jozsaのアルゴリズムを実装しました。
次回はBernstein-Vaziraniのアルゴリズムをblueqatで実装してみます。