<jupyter_start><jupyter_text>Deutsch algorithm(ドイチ アルゴリズム)（概要） Oracleまずはこのアルゴリズムに出てくるオラクルから説明します。簡単にいうと、ある入力に対し 0 あるいは 1 を返す関数です。  例として、物を買う状況を考えましょう。入力がお肉屋さんで買える場合に 1、 買えない場合に 0 を出力とします。すると以下の状況になります。$$f(x) = \begin{cases}   1\ \  (x\ がお肉屋さんで買える。)\\    0\ \  (x\ がお肉屋さんで買えない。)  \end{cases}$$これを用いるとパソコンはお肉屋さんで買えなく、牛肉は買えるので、$$f(パソコン) = 0,\ \ \ \ f(牛肉) = 1$$となります。このように入力に応じて 0 か 1 を出力する関数をオラクルと言います。量子コンピュータでは $x$ に状態を入れて、特定の状態のみを取り出すのに使います。つまりある状態のみを取り出すゲートのことを言います。  Deutsch algorithmまずは Deutsch さんが考えたアルゴリズムについて説明していきます。Deutsch algorithm とは、$\lvert 0\rangle$ か $\lvert1\rangle$ である1ビットの入力のOracleを判別するというものです。つまりはこういう状況のことを言います。$x =\lvert 0\rangle$ または $\lvert1\rangle$ のとき考えられるオラクルは以下の4通りになります。$$f(x) = \begin{cases}   0\ \  (x= \lvert 0\rangle)\\    0\ \  (x= \lvert1\rangle)  \end{cases}  \mathrm{or}\   \begin{cases}   0\ \  (x=\lvert 0\rangle)\\    1\ \  (x=\lvert 1\rangle)  \end{cases}    \mathrm{or}\   \begin{cases}   1\ \  (x=\lvert 0\rangle)\\    0\ \  (x=\lvert 1\rangle)  \end{cases}    \mathrm{or}\   \begin{cases}   1\ \  (x=\lvert 0\rangle)\\    1\ \  (x=\lvert 1\rangle)  \end{cases}$$Deutsch algorithm はこの $f$ が $\lvert 0\rangle$ と $\lvert 1\rangle$ で値が同じものなのか、それとも違うものなのかを判定してくれます。 具体的な回路を考えます。この $U_f$ が Oracle です。ただし $q_0$については入ってきた値($x$)をそのまま返し、$q_1$の$\oplus$は$q_1$に入ってきた値($y$)と $f(x)$ との和のmod2をとるものとします。(mod2 → 2で割った余り) ではそれぞれの状態を確認します。$$|\psi_1\rangle = H|0\rangle \otimes H|1\rangle = \frac{1}{\sqrt{2}}(\lvert0\rangle + \lvert1\rangle) \otimes \frac{1}{\sqrt{2}}(\lvert0\rangle - \lvert1\rangle)$$ここで上の式を$$\frac{1}{2} \lvert0\rangle \otimes (\lvert0\rangle - \lvert1\rangle) + \frac{1}{2} \lvert1\rangle \otimes (\lvert0\rangle - \lvert1\rangle)$$と変形させます。1番目のビットを見ると、$x = \lvert0\rangle$ と $x = \lvert1\rangle$ を入れ替えると符号が変わることがわかります。  この状態で上の4通りの $f(x)$ について $\lvert \psi_2\rangle$ を考えてみます。$f(x)$ は 1番目のビットにかかるので$$f(x)=0 \to q_1 は変化しない$$$$f(x)=1 \to q_1は反転する$$よって、変形した2つの項で作られた式を見ると$$f(0)=f(1) \to 各項は同符号$$$$f(0)\neq f(1) \to 各項は異符号$$ このことから$$\begin {align}\lvert \psi_2 \rangle &= \begin{cases}\pm \frac{1}{2} \lvert 0 \rangle \otimes (\lvert 0\rangle - \lvert 1\rangle) \pm \frac{1}{2} \lvert 1 \rangle \otimes (\lvert 0\rangle - \lvert 1\rangle)  \ \  \ \ (f(0)= f(1)) \\\pm \frac{1}{2} \lvert 0 \rangle \otimes (\lvert 0\rangle - \lvert 1\rangle) \mp \frac{1}{2} \lvert 1 \rangle \otimes (\lvert 0\rangle - \lvert 1\rangle)  \ \  \ \ (f(0)\neq f(1)) \end{cases} \\&= \begin{cases}\pm H\lvert 0 \rangle \otimes H \lvert 1 \rangle \ \  \ \ (f(0)= f(1)) \\ \pm H\lvert 1 \rangle \otimes H \lvert 1 \rangle \ \  \ \ (f(0)\neq f(1))\end{cases}\end {align}$$となります。さらに $q_0$ に$H$ゲートをかけます。  すると $|\psi_3\rangle$ は$$\lvert \psi_3 \rangle = \begin{cases}\pm \lvert 0\rangle \otimes H\lvert 1 \rangle\ \  \ \ (f(0)= f(1)) \\\pm \lvert 1\rangle \otimes H\lvert 1 \rangle\ \  \ \ (f(0)\neq f(1))\end{cases}$$測定には ± は関係ないので、0番目のビットを測定するとOracleを判別することがわかります。以上が Deutsch algorithm の説明です。 これをblueqatで実装してみましょう。<jupyter_code>from blueqat import Circuit
import numpy as np<jupyter_output><empty_output><jupyter_text>$f(x)$ の入出力値に対して、4通りのオラクルが考えられました。  今回は4通りをそれぞれ実装し、乱数によってランダムにオラクルが選ばれるようにします。<jupyter_code>def oracle_00(c):
    c.i[:]
    
def oracle_01(c):
    c.cx[0, 1]
    
def oracle_10(c):
    c.x[0]
    c.cx[0, 1]
    c.x[0]
    
def oracle_11(c):
    c.x[1]
    
def oracle(c):
    f = np.random.rand()
    if f < 0.25:
        oracle_00(c)
        return "f(0) = 0, f(1) = 0"
    elif f < 0.5:
        oracle_01(c)
        return "f(0) = 0, f(1) = 1"
    elif f < 0.75:
        oracle_10(c)
        return "f(0) = 1, f(1) = 0"
    else:
        oracle_11(c)
        return "f(0) = 1, f(1) = 1"<jupyter_output><empty_output><jupyter_text>ここでDeutsch のアルゴリズムを用いると、測定結果から確率1でオラクルを判別できます。<jupyter_code>c = Circuit(2)
c.x[1].h[:]
oracle_str = oracle(c)
c.h[0].m[0]
res = c.run(shots = 128)
print(res)
print("Selected oracle:", oracle_str)<jupyter_output>Counter({'10': 128})
Selected oracle: f(0) = 1, f(1) = 0
{'fraction_non_alphanumeric': 0.19750572664800203, 'fraction_numerical': 0.04759480783914482, 'mean_word_length': 3.5911214953271027, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '450930', 'license': 'Apache-2.0', 'n_tokens_mistral': 2397, 'n_tokens_neox': 2177, 'n_words': 327, 'path': 'tutorial-ja/100_deutsch.ipynb', 'repo_name': 'ryuNagai/Blueqat-tutorials', 'size': '3929'}