量子コンピュータの基本アルゴリズムの一つにドイチアルゴリズムというのがあります。さまざまな量子アルゴリズムの基礎となっているようなので、まとめておきました。
概要
ドイチ問題:
-
2進数変数$x = [0, 1]$と2進数関数$f(x) = [0, 1]$の性質を見つけ出す問題。
-
関数$f(x)$の性質
- $f(0) = f(1)$ → 定数関数
- $f(0) \neq f(1)$ → 均等関数
-
変数と関数が両方とも1ビットの時の組み合わせは4通り
f(0) f(1) 性質 0 0 定数 0 1 均等 1 0 均等 1 1 定数 -
変数$x$に値を入れて、関数の性質(定数or均等)を知りたい、
-
古典アルゴリズムでは２回調べる必要がある。
- 量子アルゴリズムでは1回調べれば知ることができるらしい。
- 例えば$f(x) = x$であれば均等関数、$f(x) = 1$であれば定数関数
-
関数の性質を書き換えると以下のようにも書ける。
- $f(0)\oplus f(1) = 0$：定数関数
- $f(0)\oplus f(1) = 1$：均等関数
量子回路
オラクル(神託)
未知の関数$f(x)$を実装する量子回路のこと。
オラクルの言葉の定義は
ラテン語orareから派生した語で、神託とも訳される。人間は、人生の、あるいは国家、社会の難局に直面すると、人力を超えた神の指示を仰いできた。そのようなとき語られる神のことばがオラクルである。(引用元)
とのこと。オラクルは神の言葉らしい。なるほど、かっこいいね。アインシュタインがどう思うのかが気になるところ。。
そのオラクル自体は以下の画像のようになる。
$\ket{x}$を入力したら出力が$\ket{y\oplus f(x)}$になって出てきたというイメージだと思っています。
オラクルを調べるのに位相キックバックというのを使用するらしい。
位相キックバック
次のようにオラクルの下位ビットをアダマールゲートで囲んだ回路を考える。
すると、出力ビットは$(-1)^{f(x)}\ket{x}\ket{1}$となる。(式変形は最下部に記載) 出力の上位ビットに係数$(-1)^{f(x)}$がついているが、これは位相キックバックという。今回は下位ビットにアダマールを作用させて、上位ビットに位相のキックバックが作用しているのがわかると思う。
ドイチ問題を解くアルゴリズム
ドイチ問題を解くアルゴリズムは、先ほどの入力ビットの$\ket{x}$を$\ket{0}$に変え、オラクルの上位ビットもアダマールゲートで囲む回路とのこと。図にすると以下。
出力ビットは$\pm \ket{f(0) \oplus f(1)}\ket{1}$となり、上位ビットを測定すれば定数関数or均等関数の判別ができる。
実装
今回使用する回路は画像のようになっている。オラクルを未知として、先に説明したようにアダマールゲートで囲み、上位ビットを測定する。
実装。
from qiskit import *
from qiskit.tools.visualization import *
# -----------------------------------------------
# ここは神のみぞ知るので我々は何も知りません。
def oracle(qci, x, y_fx):
qci.cx(x, y_fx)
qci.x(y_fx)
#------------------------------------------------
# 回路を実装
bn = 2
cn = 1
q = QuantumRegister(bn, 'q')
c = ClassicalRegister(cn, 'c')
qc = QuantumCircuit(q, c)
qc.x(q[1])
for i in range(2):
qc.h(i)
oracle(qc, q[0], q[1])
for i in range(2):
qc.h(q[i])
qc.measure(q[0], c[0])
#実行
r = execute(qc, Aer.get_backend('qasm_simulator')).result()
rc = r.get_counts()
print(rc)
plot_histogram(rc)
測定結果
測定結果は$1$となったので、今回のオラクルは均等関数ということがわかりました。
次に、オラクルを二つ用意し、同時に見ていく。回路は以下
実装
from qiskit import *
from qiskit.tools.visualization import *
# -----------------------------------------------
# ここは神のみぞ知るので我々は何も知りません。
def oracle1(qci, x, y_fx):
qci.x(y_fx)
def oracle2(qci, x, y_fx):
qci.cx(x, y_fx)
#------------------------------------------------
# 回路を実装
bn = 4
cn = 2
q = QuantumRegister(bn, 'q')
c = ClassicalRegister(cn, 'c')
qc = QuantumCircuit(q, c)
qc.x(q[1])
qc.x(q[3])
for i in range(4):
qc.h(q[i])
oracle1(qc, q[0], q[1])
oracle2(qc, q[2], q[3])
for i in range(4):
qc.h(q[i])
qc.measure(q[0], c[0])
qc.measure(q[2], c[1])
#実行
r = execute(qc, Aer.get_backend('qasm_simulator')).result()
rc = r.get_counts()
print(rc)
plot_histogram(rc)
測定結果
結果からオラクル1は均等関数、オラクル2は定数関数だとわかりました。
まとめ
確かに一度の測定で（シミュレータは1000回回しているが）関数の性質を知ることができました！
今回面白かった点はオラクルをアダマールゲートで囲むことで、キックバックを起こせたことだと思います。キックバックが起こることで関数（オラクル）の性質が弾き出されるのはすごいと思いました。
ドイチアルゴリズムと同様に基本アルゴリズムとして、ドイチ・ジョサアルゴリズム、ベルンシュタインヴァジラニアルゴリズム、サイモンアルゴリズムなどあるらしいので、そのうち勉強したいと思います。
おまけ
大変汚い字で見苦しいかもしれませんが備忘用に残しておきます。
-
式変形1
-
式変形2
$$\newcommand{\ket}[1]{\left|{#1}\right\rangle}$$
$$\newcommand{\bra}[1]{\left\langle{#1}\right|}$$
$$\newcommand{\braket}[2]{\left\langle{#1}\middle|{#2}\right\rangle}$$