この記事に関して

ここでは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ゲートで順番を戻しています。

実装します。

sample.ipynb

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で実装してみます。