@yuichirominato 2019.01.06更新 298views

Deutsch(ドイチェ)のアルゴリズム

Deutsch ドイチ 量子ゲート 量子回路

はじめに

とても基本的に量子コンピュータが何ができるのかを確認するために実装コードとともにDeutsch(ドイチェ)のアルゴリズムを見てみたいと思います。

Deutschのアルゴリズム

$f:\{0,1\} \rightarrow \{0,1\}$となる関数$f(x)$がxに依存するかしないかを問い合わせ1回で解くことができるアルゴリズム。

均一の場合、
$f(1)=1,f(0)=1$もしくは$f(1)=0,f(0)=0$
等分の場合、
$f(1)=0,f(0)=1$もしくは$f(1)=1,f(0)=0$

実現したいのは、$f(0) \oplus f(1)$で、f(0)とf(1)のXORが0なら均一、1なら等分と判断できる。

数理

1、まず入力に$\mid 0 \rangle \mid 1 \rangle$を準備する。

2、次に両方の量子ビットにアダマールゲートをかける。量子状態は下記のようになる。

$$H(\mid 0 \rangle)H(\mid 1 \rangle) = \frac{1}{2}(\mid 0 \rangle + \mid 1 \rangle)(\mid 0 \rangle – \mid 1 \rangle) = \frac{1}{2}(\mid 0 \rangle \mid 0 \rangle – \mid 0 \rangle \mid 1 \rangle + \mid 1 \rangle \mid 0 \rangle – \mid 1 \rangle \mid 1 \rangle)$$

3、次に関数をかけて$\mid x \rangle \mid y \rangle \rightarrow \mid x \rangle \mid f(x) \oplus y \rangle$を考えると、

$$\frac{1}{2}(\mid 0 \rangle \mid f(0) \oplus 0 \rangle – \mid 0 \rangle \mid f(0) \oplus1 \rangle + \mid 1 \rangle \mid f(1) \oplus 0 \rangle – \mid 1 \rangle \mid f(1) \oplus 1 \rangle) \\ = \frac{1}{2}(\mid 0 \rangle ( \mid f(0) \oplus 0 \rangle – \mid f(0) \oplus1 \rangle) + \mid 1 \rangle ( \mid f(1) \oplus 0 \rangle – \mid f(1) \oplus 1 \rangle))$$

4、ここで、f(0)とf(1)についてそれぞれXORの排他的論理和を考えると、

$f(0) = 0$の時、$f(0)\oplus 0 =0,f(0)\oplus 1 =1,$
$f(0) = 1$の時、$f(0)\oplus 0 =1,f(0)\oplus 1 =0,$

また、

$f(1) = 0$の時、$f(1)\oplus 0 =0,f(1)\oplus 1 =1,$
$f(1) = 1$の時、$f(1)\oplus 0 =1,f(1)\oplus 1 =0,$

より、上記の場合分けを適用すると下記のようになる。

$$\frac{1}{2}((-1)^{f(0)}\mid 0 \rangle ( \mid 0 \rangle – \mid 1 \rangle) + (-1)^{f(1)}\mid 1 \rangle ( \mid 0 \rangle – \mid 1 \rangle))$$

さらにまとめて、

$$(-1)^{f(0)} \frac{1}{2}(\mid 0 \rangle + (-1)^{f(0) \oplus f(1)}\mid 1 \rangle)( \mid 0 \rangle – \mid 1 \rangle))$$

5、そして、グローバル位相の$(-1)^{f(0)}$は考慮せず、1量子ビット目を抜き出すと、

$$\frac{1}{\sqrt{2}}(\mid 0 \rangle + (-1)^{f(0) \oplus f(1)}\mid 1 \rangle$$

6、この時点で、だいたい1量子ビット目は$f(0) \oplus f(1)$によって左右し、2量子ビット目は$\mid 1 \rangle$に戻るのが確認できるが、念の為アダマール変換を再度かけてみると、1量子ビット目は、

$$\frac{1}{2}((1+(-1)^{f(0)\oplus f(1)})\mid 0 \rangle+(1-(-1)^{f(0)\oplus f(1)})\mid 1 \rangle)$$

これは$f(x)$のXORの結果だけによって、均一か等分かを判断できる。

量子回路

基本の回路は0と1を用意して、アダマール変換で囲んだf(x)の関数を表現したオラクルを評価します。

|0> --H--??--H--M
|1> --H--??--H--M

例題と実装

Blueqatのコードで実装してみる。2量子ビットの初期状態はXゲートを持って準備できて、オラクルとして評価する量子ゲートを下記のように準備する。

-----H--X--H--M
--X--H-----H--M

0番目にXゲートを適用すると、

from blueqat import Circuit
Circuit().x[1].h[:].x[0].h[:].m[:].run(shots=100)
Counter({'01': 100})

0番目の量子ビットの結果だけをみて、最初は0なのでこれは均一。

-----H--*--H--M
--X--H--X--H--M

CNOT(CX)をいれてみます。CNOTを評価すると、

Circuit().x[1].h[:].cx[0,1].h[:].m[:].run(shots=100)
Counter({'11': 100})

1がでましたので、等分。CNOTを逆さまにしてみると、

-----H--X--H--M
--X--H--*--H--M
Circuit().x[1].h[:].cx[1,0].h[:].m[:].run(shots=100)
Counter({'01': 100})

0がでましたので、こちらは均一。0が1になり、1は1のままで、常に1がでるので、あってそう。このように将来的な周期性の判定に繋がりそうな基本的な量子回路の評価方法でした。

参考

https://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm

Recommended


CONTACT

info@mdrft.com

ブログトップへ Wikiへ移動

量子コンピュータ一般

量子ゲートアルゴリズム

量子アニーリング一般

量子アニーリングアルゴリズム

BlueqatSDKの使い方