FPGA開発日記

FPGAというより、コンピュータアーキテクチャかもね! カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages

ゼロから作る量子コンピュータ・シミュレータ(6. Deutsch-Jozsaアルゴリズムを実装する)

量子コンピュータ・シミュレータの実装、骨格となるところは完成しており、あとはいろいろなゲートを挿入するだけとなっている。

かなり進んできたので、少し気分転換にDeutsch-Jazsaのアルゴリズムを実装してみよう。 Deutsch-Jazsaのアルゴリズムについて詳細はここでは説明しないが、量子コンピュータにより古典コンピュータよりも高速に解くことができるといわれているアルゴリズムだ。

詳細なアルゴリズムは以下を参考にした。

http://quantum.classcat.com/category/quantum-algorithms/

この中では、関数 f(x)が与えられたときに、0か1から構成されるnビットの入力が与えられて、

  • 全ての入力ビットが0か1のどちらかである = constant
  • 入力ビットの半分が0、残り半分が1である = balanced

とし、そのどちらであるかどうかを判定するアルゴリズムだ。何に使うんだ?といえばそこまでだが、量子コンピュータの威力を見ることができる簡単な例なので追ってみることにする。

アルゴリズムの原理はさておき、以下のようにすれば f(x)の判定を行うことができるらしい。

  1. n量子ビットを0で初期化する。
  2. n量子ビットにHadamardゲートを適用する。
  3. n量子ビットに対象となる関数f(x)を適用する。
  4. n量子ビットにHadamardゲートを適用する。
  5. n量子ビットを測定する。

上記のウェブサイトで登場するのは  f(x)=x _ {0} \oplus x _ {1} x _ {2} という関数だ。これはBalancedとなる。これを自作量子コンピュータ・シミュレータで実装してみる。

真ん中に入っているのが関数f(x)を表現したオラクル回路U_{f}である。これに対して、前後に全ビットに対してHadamardゲートを適用する。

cat ../test/test_dj_balanced.py
qubits = [qbit.make_qbit() for i in range(3)]

for q in qubits:
    qbit.h(q)

qbit.h(qubits[2])
qbit.cnot(qubits[1], qubits[2])
qbit.h(qubits[2])
qbit.z(qubits[0])

for q in qubits:
    qbit.h(q)

result = [0 for i in range(8)]

for i in range(0, 1000):
    val = qbit.val(qubits[2]) << 2 | qbit.val(qubits[1]) << 1 | qbit.val(qubits[0])
    result[val] = result[val] + 1

print(result)

実行結果は以下のようになった。量子ビットが000になる確率は0であり、Balancedであることが分かる。

$ ./qbit_simulator ../test/test_dj_balanced.py
[0, 265, 0, 244, 0, 255, 0, 236]

一方でConstantの関数を入力してみる。というか今度は U_{f}=Iなだけである(たぶん)。

qubits = [qbit.make_qbit() for i in range(3)]

for q in qubits:
    qbit.h(q)

for q in qubits:
    qbit.h(q)

result = [0 for i in range(8)]

for i in range(0, 1000):
    val = qbit.val(qubits[2]) << 2 | qbit.val(qubits[1]) << 1 | qbit.val(qubits[0])
    result[val] = result[val] + 1

print(result)

実行結果は以下のようになった。量子ビットが000になる確率は100%であり、Constantであることが分かる。

$ ./qbit_simulator ../test/test_dj_constant.py
[1000, 0, 0, 0, 0, 0, 0, 0]
f:id:msyksphinz:20181003000801p:plain