Deutsch-Jozsaのアルゴリズム

$$
\def\bra#1{\mathinner{\left\langle{#1}\right|}}
\def\ket#1{\mathinner{\left|{#1}\right\rangle}}
\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}}
$$

#ドイチ・ジョザのアルゴリズム

今回はドイチ・ジョザのアルゴリズムを実装したいと思います。

ブラックボックス問題と呼ばれる種の問題を普通のコンピュータ（古典アルゴリズム）よりも少ない問合せ回数にて答えを導き出せることを最初に証明してくた量子アルゴリズムをドイチ・ジョザのアルゴリズムと言います。

##ドイチ・ジョザのアルゴリズムとは
#####一言で言うと２種類の関数があり、この量子アルゴリズムでは1回の問合せ回数でその2つのうちどちらかを判別できるというものです。

２種類の関数は以下のように、(i)どんなxを入れても0か1を返すf(x)、(ii)半分のxに対しては0,残り半分のxに対しては1を返す関数です。

入力するxは

\ket{00\cdots000}, \ket{00\cdots001}, \ket{00\cdots011}, \cdots, \ket{11\cdots111}

の$2^n$通りのxです。

( i ) 一定関数
→ 全ての x で f(x)=0 または 全ての x で f(x)=1

( ii ) 均等関数
→ $2^{n-1}$ 個の x で f(x)=0 、残りの x で f(x)=1

この２種類の関数のどちらかを何回の問合せ回数で判別できるかを古典アルゴリズムと量子アルゴリズムで競います。

肝となるのは古典アルゴリズムでは当然一度の問合せで一つの$x$しか入力できませんが、量子アルゴリズムでは入力に重ね合わせ状態を用いる点です。

##さて、実際に具体的な流れを追ってみましょう。

登場人物は2人、アリスとボブです。それぞれの目的は

アリス　→　関数の種類を判別したい人
ボブ　→　関数の種類を選び、"私が選んだ関数はどちらでしょう"という問いを投げかける人です。

それぞれがとる行動は

アリス　→　$2^n$のxを投げる
ボブ　→　関数の種類によりオラクルを実装します

###①初期状態

\ket{psi}\ket{0}^{⊗n}⊗\ket{1}

###②重ね合わせ状態を作る

H^{⊗n}\ket{0}⊗H\ket{1}=
\frac{1}{\sqrt{2^{n+1}}}\sum_{x\in\{0,1\}^n}^{2^n} \{\left|x\right> \otimes (\left|0\right>-\left|1\right>)\}\\
=\frac{1}{\sqrt{2^{n+1}}}\sum_{x\in\{0,1\}^n}^{2^n} \left|x\right> \otimes \left|-\right>

準備完了です。

###③オラクルUfに投げる

\frac{1}{\sqrt{2^{n+1}}}\sum_{x\in\{0,1\}^n}^{2^n} \ket{x} \otimes (\ket{0}-\ket{1}) \xrightarrow{U_f}
\frac{1}{\sqrt{2^{n+1}}}\sum_{x\in\{0,1\}^n}^{2^n} \ket{x} \otimes (\ket{0\oplus f(x)}- \ket{1\oplus f(x)})

=\frac{1}{\sqrt{2^{n+1}}} \sum_{x\in\{0,1\}^n}^{2^n} \ket{x} \otimes (-1)^{f(x)} (\ket{0}-\ket{1})

$(-1)^{f(x)}$はグローバル位相のため補助ビットから入力ビットの方へ移動が可能（位相キックバック）

=\frac{1}{\sqrt{2^{n+1}}} \sum_{x\in\{0,1\}^n}^{2^n} (-1)^{f(x)} \ket{x} \otimes (\ket{0}-\ket{1})

列ベクトルで入力ビットがどうなってるか確認してみます。

( i )一定関数の場合

\frac{1}{\sqrt{2^{n}}}\sum_{x\in\{0,1\}^n}^{2^n} \left|x\right> = \frac{1}{\sqrt{2^{n}}}\begin{pmatrix}
1 \\ 1 \\ 1 \\ \vdots \\ 1 \\ \end{pmatrix} 　\xrightarrow{U_f}　\frac{1}{\sqrt{2^{n}}}\begin{pmatrix}
1 \\ 1 \\ 1 \\ \vdots \\ 1 \\ \end{pmatrix}　or　\frac{1}{\sqrt{2^{n}}}\begin{pmatrix}
-1 \\ -1 \\ -1 \\ \vdots \\ -1 \\ \end{pmatrix}

1qubitで考えると$\ket{+} or -\ket{+}$です。

( ii )均等関数の場合

\frac{1}{\sqrt{2^{n}}}\sum_{x\in\{0,1\}^n}^{2^n} \left|x\right> = \frac{1}{\sqrt{2^{n}}}\begin{pmatrix}
1 \\ 1 \\ 1 \\ \vdots \\ 1 \\ \end{pmatrix} 　\xrightarrow{U_f}　\frac{1}{\sqrt{2^{n}}}\begin{pmatrix}
1 \\ -1 \\ 1 \\ \vdots \\ -1 \\ \end{pmatrix}

1qubitで考えると$\ket{-} (or -\ket{-})$です。

###④アダマールゲートをかけて測定

( i )一定関数の場合

H^{⊗n} \frac{1}{\sqrt{2^{n}}}\begin{pmatrix}
1 \\ 1 \\ 1 \\ \vdots \\ 1 \\ \end{pmatrix}　or　H^{⊗n}\frac{1}{\sqrt{2^{n}}}\begin{pmatrix}
-1 \\ -1 \\ -1 \\ \vdots \\ -1 \\ \end{pmatrix}　=　\begin{pmatrix}
1 \\ 0 \\ 0 \\ \vdots \\ 0 \\ \end{pmatrix} 　or　-\begin{pmatrix}
1 \\ 0 \\ 0 \\ \vdots \\ 0 \\ \end{pmatrix}　\xrightarrow{measure}　\ket{000\cdots0}

( ii )均等関数の場合

H^{⊗n} \frac{1}{\sqrt{2^{n}}}\begin{pmatrix}
1 \\ -1 \\ 1 \\ \vdots \\ -1 \\ \end{pmatrix}　=　\begin{pmatrix}
0 \\ 0 \\ 0 \\ \vdots \\ 1 \\ \end{pmatrix}　\xrightarrow{measure}　\ket{111\cdots1}

##コードベースで追ってみる(均等な関数)

####⓪準備します

# 必要なライブラリのインポート
from qiskit import IBMQ, BasicAer, Aer
from qiskit.providers.ibmq import least_busy
from qiskit import QuantumCircuit, execute
import numpy as np

# 描画ツールのインポート
from qiskit.visualization import plot_histogram

####①初期状態

#入力用量子ビットの数を設定
n = 3

#ドイチ・ジョザアルゴリズムに均等な関数を実装した回路を"balanced_dj"と名付ける
balanced_dj = QuantumCircuit(n+1, n)

#各量子ビットはもともと|0>に初期化されているため、最後の補助ビットだけ|1>に
balanced_dj.x(n)

####②重ね合わせ状態を作る

#全体にアダマールをかけて入力用量子ビットはすべて|+⟩ に、そして補助ビットは|−⟩に
for qubit in range(n):   
    balanced_dj.h(qubit)

####③オラクルUfに投げる

#####オラクルに投げる前に、オラクル自体を実装せねばなりません。

#ボブがアリスには内緒で均等関数のオラクル"balanced_oracle"を作ります。
balanced_oracle = QuantumCircuit(n+1,n)

balanced_oracle.barrier()   #回路をみやすくするためにバリアを配置

for qubit in range(n):    #入力用量子ビットにCNOTゲートを適用
    balanced_oracle.cx(qubit, n)

balanced_oracle.barrier() #回路をみやすくするためにバリアを配置
balanced_oracle.draw()

ボブがオラクルを作りました。

このオラクルに色々な$x(\ket{000} \cdots \ket{111})$を代入すると$0$と$1$が均等に帰ってくることがわかります。

まさにこのオラクルが均等な関数の役割をになっていることがわかります。
（任意のコントロールビット奇数個をXゲートで挟むことにより、出力を逆にできます。）

####均等関数のオラクルが完成したので実際に重ね合わせ状態をこのオラクルへ投げてみます。

balanced_dj += balanced_oracle  #ボブが作った均等な関数の追加
balanced_dj.draw()

（急に回路しょぼくなってゴメン）

####④アダマールゲートをかけて測定

for qubit in range(n):
    balanced_dj.h(qubit)
balanced_dj.barrier()
for i in range(n):
    balanced_dj.measure(i, i)

balanced_dj.draw()

# 回路をシミュレーターに投げて結果を出力します
simulator = Aer.get_backend('qasm_simulator')
result = execute(balanced_dj, backend=simulator, shots=1).result()

# 結果をヒストグラムでプロットします
plot_histogram(result.get_counts(balanced_dj))

$\ket{111}$という結果が出てきたので、アリスは均等関数だということが確認できました。

###よくある間違いを自分の言葉で訂正してみた(ので他にいい表現があったら教えてください)

#####アルゴリズムは1人で実装するのでは？　→　アリスはオラクルの実装には関わらない
関数の種類によってオラクルは変化しますので、アリスがオラクルを実装したということは、すなわちアリスはアルゴリズムを動かす前から関数の種類を知っているということになります。それでは本末転倒ではないでしょうか。オラクルはブラックボックスです。

#####アリスは関数の種類によって行動は変わる？　→　アリスの行動は変わらない
アリスはただ$2^n$のxをオラクルに投げるだけです。関数はアリスの意思とは関係なく決定されます。ほぼ上と被っている話です。

#####関数の種類を判別するのがオラクル？　→　xに対してf(x)の値を返すのがオラクル
オラクルは判別しているわけではありません。ただf(x)という値を返しているだけです。古典コンピュータでは一度問い合わせるときに一つのxしか尋ねることができませんが、量子コンピュータであれば$2^n$のxの重ね合わせ状態を問合せます。ので、結果的にオラクルが関数の種類を判別しているということと同値になります。

##終わりに

よくある間違いのところでも言及しましたが、オラクルの解釈がやや複雑です。

気づいたのは、グローバーのアルゴリズムでもドイチ・ジョザのアルゴリズムでも、前者であればマーキングしたい状態、後者であれば関数の種類によってオラクルの形が変化します。マーキングしたいデータ、関数の種類をアルゴリズムを実行する前から知っている前提では本末転倒です。

##参考文献

[ドイチ・ジョザアルゴリズム (Deutsch-Jozsa algorithm)]
(https://qiita.com/KeiichiroHiga/items/6c13657bcd59f9a805a1)

[QuantumTokyo]
(https://youtu.be/nTX6F-r5lME)