量子コンピュータ・シミュレータの実装、骨格となるところは完成しており、あとはいろいろなゲートを挿入するだけとなっている。
かなり進んできたので、少し気分転換にDeutsch-Jazsaのアルゴリズムを実装してみよう。 Deutsch-Jazsaのアルゴリズムについて詳細はここでは説明しないが、量子コンピュータにより古典コンピュータよりも高速に解くことができるといわれているアルゴリズムだ。
詳細なアルゴリズムは以下を参考にした。
http://quantum.classcat.com/category/quantum-algorithms/
この中では、関数が与えられたときに、0か1から構成されるnビットの入力が与えられて、
- 全ての入力ビットが0か1のどちらかである = constant
- 入力ビットの半分が0、残り半分が1である = balanced
とし、そのどちらであるかどうかを判定するアルゴリズムだ。何に使うんだ?といえばそこまでだが、量子コンピュータの威力を見ることができる簡単な例なので追ってみることにする。
アルゴリズムの原理はさておき、以下のようにすればの判定を行うことができるらしい。
上記のウェブサイトで登場するのは という関数だ。これはBalancedとなる。これを自作量子コンピュータ・シミュレータで実装してみる。
真ん中に入っているのが関数を表現したオラクル回路である。これに対して、前後に全ビットに対して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の関数を入力してみる。というか今度はなだけである(たぶん)。
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]