Deutsch-Jozsaのアルゴリズムを実装してみた
Zenn初投稿です。
よろしくお願いします。
Deutsch-Jozsaのアルゴリズムについて
量子コンピュータのアルゴリズムの1つです。このアルゴリズムは、実用性は低いものの、ある種の問題においては量子コンピュータが古典コンピュータよりも有利であることを示したという点で重要です。[1]
問題設定
図1. 入力が(n+1)量子ビットのDeutschのゲート
図1のような量子ゲートを考えます。入力は、
ここで、
- 定値型(すべての
に対して、一定の値をとる。その値は、0と1のいずれか。)x - 分布型(
に対して、0と1の出る頻度が等しい。)x
が2つのどちらかが分からない場合に、どちらであるか当てる、という問題を考えます。f(x)
古典計算機の場合
例えば、
量子計算機の場合(Deutsch-Jozsaのアルゴリズム)
図2Deutsch-Jozsaのアルゴリズムの量子ゲートの配置
量子ゲートを図2のように配置します。ただし、量子ビットは全て
バリア(縦線)上での量子状態を、左から順に
まず、
よって、
よって、
ここで、上位
よって、上位
つまり、量子ビットの数が増えても、理想的には1回のみの試行で
Qiskitで実装する
必要モジュールのインポート
from qiskit import QuantumRegister, QuantumCircuit
from qiskit.circuit.library import CCXGate, C3XGate, C4XGate, MCXGate
定値型
今回は、inst_u_1
という手続きとして使えるようにします。ここで、w_qureg
は、分布型の回路を考えるときに使う作業用ビットです。今は気にする必要はありません。
x_qureg = QuantumRegister(4, name="x")
y_qureg = QuantumRegister(1, name="y")
w_qureg = QuantumRegister(5, name="w")
qc_u_1 = QuantumCircuit(x_qureg, y_qureg, w_qureg, name="u_1")
qc_u_1.barrier()
qc_u_1.x(4)
qc_u_1.barrier()
inst_u_1 = qc_u_1.to_instruction()
qc_u_1.draw("mpl")
図3.
分布型
適当に0から15の間で8個乱数を生成してみて、5, 13, 4, 11, 2, 1, 0, 8
という値が得られました。そこで、次のような
カルノー図を用いて最小積和形を求めると、次のようになります。
量子回路において、ANDはToffoliゲート(QiskitではCCX、C3X、C4X、MCXゲート)として表現できますし、ORはToffoliゲートの制御ビットの前にXゲートを、作用ビットの後にXゲートを置くことで表現できます。以上のことから、次のような量子ゲートinst_u_2
として利用できます。
ccx = CCXGate()
c3x = C3XGate()
c4x = C4XGate()
c5x = MCXGate(5)
qc_u_2 = QuantumCircuit(x_qureg, y_qureg, w_qureg, name="u_2")
# x1 && x2
qc_u_2.append(ccx, [1, 2, 5])
qc_u_2.x(0)
# !x0 && x1 && x3
qc_u_2.append(c3x, [0, 1, 3, 6])
# !x0 && x2 && x3
qc_u_2.append(c3x, [0, 2, 3, 7])
qc_u_2.x(0)
qc_u_2.x(3)
# x0 && x1 && !x3
qc_u_2.append(c3x, [0, 1, 3, 8])
qc_u_2.x(3)
qc_u_2.x([1, 2])
# x0 && !x1 && !x2 & x3
qc_u_2.append(c4x, [0, 1, 2, 3, 9])
qc_u_2.x([1, 2])
qc_u_2.barrier()
# w0 || w1 || w2 || w3 || w4
qc_u_2.x([5, 6, 7, 8, 9])
qc_u_2.append(c5x, [5, 6, 7, 8, 9, 4])
qc_u_2.x(4)
qc_u_2.barrier()
inst_u_2 = qc_u_2.to_instruction()
qc_u_2.draw("mpl")
図4.
長くなってしまいましたが、
AerSimulatorで実行してみる
AerSimulatorは、IBMがメンテナンスを行っている量子コンピュータのシミュレータです。[2]
必要モジュールのインポート
from qiskit import ClassicalRegister
from qiskit_aer.primitives import SamplerV2
from qiskit.visualization import plot_histogram
定値型
回路の準備
x_meas = ClassicalRegister(4, name="c")
qc1 = QuantumCircuit(x_qureg, y_qureg, w_qureg, x_meas)
qc1.x(4)
qc1.h([0, 1, 2, 3, 4])
qc1.append(inst_u_1, list(range(10)))
qc1.h([0, 1, 2, 3])
qc1.measure([3, 2, 1, 0], [3, 2, 1, 0])
qc1.draw("mpl")
図5.
ちなみに、この例でも行っているように、measure()
中の数字の並び方は逆にしておくとplot_histogram()
の出力との対応が分かりやすくておすすめです。
実行(成功)
sampler = SamplerV2()
job1 = sampler.run([qc1.decompose()])
result1 = job1.result()
plot_histogram(result1[0].data.c.get_counts())
ここで、decompose()
は回路を分解するためのメソッドで、ここではinst_u_1
を分解させています。これを実行すると、図6のようなヒストグラムが得られます。
図6.qc1
のシミュレーション実行結果
確率1で状態が確率1で
分布型
回路等の準備は、上の例のinst_u_1
をinst_u_2
に変えるだけなので省略します。
実行(失敗)
図7.inst_u_2
を用いた場合のシミュレーション実行結果
計算上は
分布型の入出力を確かめてみる
test_register = ClassicalRegister(5, name="c")
qc2 = QuantumCircuit(x_qureg, y_qureg, w_qureg, test_register)
qc2.h([0, 1, 2, 3])
qc2.append(inst_u_2, list(range(10)))
qc2.measure([3, 2, 1, 0, 4], [4, 3, 2, 1, 0])
qc2.draw("mpl")
図8.
図9.シミュレーション結果
シミュレーション結果のビットは、左から順に
(分布型)何がいけなかったのか
作業用量子ビットが、入出力量子ビットと量子もつれの状態にあったことが原因です。
分布型の回路においては作業用ビットを用いて計算していました。その際に入出力量子ビットと作業用量子ビットがもつれ合ってしまい、適切な結果を得られませんでした。
もつれ合いをほどく
例えば、単純化して図9のような量子回路を考えましょう。
図9.CNOTを2回施す量子回路
問題は「
具体的にどのようにしてもつれ合いをほどくかというと、計算結果を
図10.
最初の量子状態を
まず、最初の状態は以下のように書けます。
次のように、射影演算子の和を文字でおきます。
さきほどの
ここで、次の等式が成り立ちます。
よって、
このように、一義的に異なる量子ビット状態に分離できました。
もつれ合いのほどきを実装する
図4の回路(inst_u_3f
で他の回路から利用できるようにします。inst_u_3_f
を実装するソースコードを、以下に示します。
qc_u_3_f = QuantumCircuit(x_qureg, y_qureg, w_qureg, name="u_3_f")
# x1 && x2
qc_u_3_f.append(ccx, [1, 2, 5])
qc_u_3_f.x(0)
# !x0 && x1 && x3
qc_u_3_f.append(c3x, [0, 1, 3, 6])
# !x0 && x2 && x3
qc_u_3_f.append(c3x, [0, 2, 3, 7])
qc_u_3_f.x(0)
qc_u_3_f.x(3)
# x0 && x1 && !x3
qc_u_3_f.append(c3x, [0, 1, 3, 8])
qc_u_3_f.x(3)
qc_u_3_f.x([1, 2])
# x0 && !x1 && !x2 & x3
qc_u_3_f.append(c4x, [0, 1, 2, 3, 9])
qc_u_3_f.x([1, 2])
qc_u_3_f.barrier()
qc_u_3_f.x([5, 6, 7, 8, 9])
qc_u_3_f.barrier()
inst_u_3_f = qc_u_3_f.to_instruction()
qc_u_3_f.draw("mpl")
図.inst_u_3_f
の中身
その後、次の回路
図11.計算して、その後作業ビットのもつれ合いをほどく回路
ソースコードは、以下のとおりです。
qc_u_3 = QuantumCircuit(x_qureg, y_qureg, w_qureg)
qc_u_3.append(inst_u_3_f, list(range(10)))
qc_u_3.append(c5x, [5, 6, 7, 8, 9, 4])
qc_u_3.append(inst_u_3_f.inverse(), list(range(10)))
inst_u_3 = qc_u_3.to_instruction()
qc_u_3.draw("mpl")
ゲートinverse()
メソッドを用いることで、随伴ゲートの
分布型で実行(成功)
qc3 = QuantumCircuit(x_qureg, y_qureg, w_qureg, x_meas, name="u_3")
qc3.x(4)
qc3.h([0, 1, 2, 3, 4])
qc3.append(inst_u_3, list(range(10)))
qc3.h([0, 1, 2, 3])
qc3.measure([3, 2, 1, 0], [3, 2, 1, 0])
図12.
job3 = sampler.run([qc3.decompose(reps=2)])
result3 = job3.result()
plot_histogram(result3[0].data.c.get_counts())
図13.qc3
のシミュレーション実行結果
IBM Runtimeでも実行してみる
qiskit_ibm_runtime
を使用すれば、IBMの量子コンピュータを利用できます。公式サイトの記述[3]に基づいて、アカウントの設定がされているものとします。
必要モジュールのインポート
SamplerV2
はAerSimulatorのものと名前が衝突してしまうので、RuntimeSamplerV2
としてインポートします。
from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import SamplerV2 as RuntimeSamplerV2
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager
backend、PM(Pass Manager)の取得
backend(実行する量子コンピュータ)を取得します。また、量子コンピュータに回路の情報を渡すためにISA回路に変換する必要があります。PM(Pass Manager)の機能で、ISA回路に変換できます。
service = QiskitRuntimeService()
backend = service.least_busy(simulator=False, operational=True)
print(f">>> selected service: {backend}")
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
>>> selected service: <IBMBackend('ibm_kyiv')>
ウクライナはキーウのサーバーが選択されました。
定値型
ISA回路に変換
isa_circ1 = pm.run(qc1)
isa_circ1.draw("mpl", idle_wires=False)
図14.ISA回路への変換結果
Hadamardゲートが分解されています。
実行
sampler = RuntimeSamplerV2(backend)
job1 = sampler.run([isa_circ1], shots=1024)
print(f">>> backend: {backend}")
print(f">>> Job ID: {job1.job_id()}")
print(f">>> Job Status: {job1.status()}")
result1 = job1.result()
print(f">>> Job Status: {job1.status()}")
plot_histogram(result1[0].data.c.get_counts())
>>> backend: <IBMBackend('ibm_kyiv')>
>>> Job ID: cy6tbsqcw2k0008k02zg
>>> Job Status: QUEUED
>>> Job Status: DONE
図15.
ほとんど1の確率で、状態が
分布型
ISA回路に変換
isa_circ3 = pm.run(qc3)
isa_circ3.draw("mpl", idle_wires=False)
(ISA回路は恐ろしく長くなったので省略します・・・)
実行
図16.
ほぼほぼランダムみたいになってしまいました。
図17.
最適化レベルを3にして、バリアも全てなくしてISA回路に変換し、実行した結果を図17に示しました。やはり、ほぼランダムになってしまっています。実際に使うためには、ゲート数を減らすための工夫が必要なようです。
なお、試しに3量子ビット入力でも行ってみましたが、やはりほぼランダムになってしまいました。ヒストグラムを図18に示します。なお、
という関数
図18. 3量子ビットの場合の結果
3量子ビットの場合はCCXゲート、C3Xゲートを用いました。C3Xゲートの入出力を図19のような回路で確かめてみたところ、図20のような結果が得られました。C3Xゲート単体で、確率振幅のみ見ると、入出力は、正しくできているようです。
図19. C3Xゲートの入出力を確かめる量子回路
図20. C3Xゲートの入出力
Deutsch-Jozsaのアルゴリズムは、本質的には制御ビットの位相反転を用いているので、位相反転エラーが強く現れているものと考えられます。
おわりに
Deutsch-Jozsaのアルゴリズムは量子アルゴリズムの中で最も早くからあったものの1つですが、実際に実装してみると様々な学びがありました。
あと、IBM Runtimeは日本では日中に動かしたほうが良いです。夜だと、欧米の方々が積極的に利用している様子で、全然繋がりません。日中だと数十秒でつながるのに、夜中だと1時間以上待ちというケースが多々ありました。
最後までお読みいただき、ありがとうございました。
-
宮野、古澤(2016)「量子コンピュータ入門(第2版)」(日本評論社) ↩︎
-
IBM(アクセス日:2025年1月19日)「Qiskit ecosystem」https://www.ibm.com/quantum/ecosystem ↩︎
-
IBM(アクセス日:2025年1月19日)「IBM Quantum Documentation」https://docs.quantum.ibm.com/guides/setup-channel#set-up-to-use-ibm-quantum-platform ↩︎
Discussion
こんにちは。貴重な記事を投稿していただきありがとうございます。
さて、図11の下のソースコード中の、
qc_u_3.append(inst_u_3_f, list(range(10)))
の inst_u_3_f は、どこで作成していますか?
qc_u_3やqc2 から取得してみましたが、結果が、図13の通りになりません。
宜しければ、ご教授ください。
コメントありがとうございます。
「もつれ合いのほどきを実装する」の項に、
inst_u_3_f
の実装を追記しました。