2
QAA(Quantum Adiabatic Algorithm)は、あるコスト関数の最小値を発見するための量子アルゴリズムです。
アルゴリズムには比較的に多くのCNOTゲートを必要とするため、NISQ(雑音ありマシン)よりもFTQC(誤り耐性マシン)用と考えられます。
コスト関数最小化を量子計算に持ち込むために、コスト関数はある量子系のハミルトニアンに対応させ、最小値はその最低エネルギー状態に対応させます。
すなわち、与えられたハミルトニアンの最低エネルギー状態(未知)をなんとかして実現し、最後にその量子状態を測定する(=知る)ことで、問題を解きます。
QAAでは、量子断熱定理と呼ばれる量子系の性質をうまく使って、最低エネルギー状態を実現します。
例えば以下の解説記事にある通り、
http://rhodia.ph.tsukuba.ac.jp/~hatsugai/modules/d3blog/details.php?bid=21
「量子化された定常状態にある系は系を無限にゆっくり動かすとき状態が変化しない」
というのが量子断熱定理です。
今回は、これを都合よく使って
「あるハミルトニアンにおいて最低エネルギー状態にある量子は、ハミルトニアンを無限にゆっくり変化させても、その時々のハミルトニアンにおける最低エネルギー状態になっている」
とします。
これにより、以下のことを実現できれば良いとわかります。
第一項目は、最低エネルギー状態が既知であるような(かんたんな)ハミルトニアンを使ってしまえば解決できます。
第二項目は、シュレディンガー方程式が教えてくれます。ハミルトニアンの元での、秒後の量子状態は、ユニタリ変換を行うと得られます。今回、ハミルトニアンは刻々と変化していきますので、のようになります。
第三項目は、初期ハミルトニアンと、解きたい問題に相当するコストハミルトニアンに対して
とします。は時間変化を行う秒数です。
では、系のハミルトニアンはで、時間が経過する毎にだんだんとは弱まって、が強くなり、最後はだけになります。
断熱定理によれば、このとき量子はの最低エネルギー状態にあるはずです。
「無限に」の部分は有限の計算資源である実コンピュータでは不可能なので、諦めます。
すなわち時間方向を有限のステップに区切る(差分法)こととします。
コンセプトは先に述べたとおりですが、時間変化を表すユニタリ変換を、なんとか量子コンピュータで使えるゲートで表現する必要があります。
いま、ハミルトニアンは初期ハミルトニアンとコストハミルトニアンの和です。
よくある問題設定では、
となります。
この場合の解決方法が、Trotter展開です。
Trotter展開は、演算子の指数法則のようなものです。近似的に、
が成り立ちます。が小さければ近似精度が高くなります。
要は、ハミルトニアンの和で描かれている場合の時間発展は、個々のハミルトニアンにおける時間発展の連続操作で近似できると言っています。
我々は、時間方向のステップ数を十分細かく取っておくことで、この近似を正当化します。
上記のコンセプトを実装します。
SDKとしてqiskitを使っていますが、blueqat等のSDKでも簡単に真似できます。
4ノードのMAX CUT 問題を解きます。
https://dojo.qulacs.org/ja/latest/notebooks/5.3_quantum_approximate_optimazation_algorithm.html
初期の(かんたんな)ハミルトニアンとしては、横磁場を使います。
このハミルトニアンの最低エネルギー状態は です。
この状態は、全量子ビットにそれぞれゲートとゲートをかけることで作れます。
コストハミルトニアンは、となります。
解である最低エネルギー状態は"1010"と"0101"の2つあります。
この場合、量子状態はこの2つの均等な重ねあわせ状態に収束しますので、測定すると確率50%でランダムに片方が出ます。
時間発展の秒数は、ステップ数はとします。
Copy #!pip install qiskit #!pip install pylatexenc from qiskit.aqua.operators import WeightedPauliOperator from qiskit import QuantumCircuit from qiskit import execute, Aer, IBMQ from qiskit.quantum_info.operators import Operator from qiskit.tools.visualization import plot_histogram import numpy as np n_qubits = 4 pauli_dict = {'paulis': [{"coeff": {"imag": 0.0, "real": 1}, "label": "XIII"}, {"coeff": {"imag": 0.0, "real": 1}, "label": "IXII"}, {"coeff": {"imag": 0.0, "real": 1}, "label": "IIXI"},{"coeff": {"imag": 0.0, "real": 1}, "label": "IIIX"}]} H_ref = WeightedPauliOperator.from_dict(pauli_dict).to_opflow() pauli_dict = {'paulis': [{"coeff": {"imag": 0.0, "real": 1}, "label": "ZZII"}, {"coeff": {"imag": 0.0, "real": 1}, "label": "IZZI"}, {"coeff": {"imag": 0.0, "real": 1}, "label": "IIZZ"},{"coeff": {"imag": 0.0, "real": 1}, "label": "ZIIZ"}]} H_cost = WeightedPauliOperator.from_dict(pauli_dict).to_opflow() T = 2 N = 8 dt = T/N t = np.arange(0,T,dt) circ = QuantumCircuit(n_qubits) circ.x(range(n_qubits)) circ.h(range(n_qubits)) circ.barrier() for tt in t: circ.hamiltonian(H_ref,(1-tt/T)*dt,[0,1,2,3]) # time evolution circ.barrier() circ.hamiltonian(H_cost,tt/T*dt*3,[0,1,2,3]) # time evolution circ.barrier() circ.measure_all() results = execute(circ,backend=Aer.get_backend('qasm_simulator'),shots=1024).result() counts = results.get_counts() # zero-padding for i in range (2**n_qubits): counts.setdefault(format(i, '0'+str(n_qubits)+'b'),0) plot_histogram(counts)
<Figure size 504x360 with 1 Axes>
確かに解が高い確率で得られています。
差分ステップ数を多くすると、Trotter展開の精度が良くなるので、解でない状態が出る確率は下げることが出来ます。
今回、ライブラリを使って実装しましたので、CNOTがどれぐらい使われているのかがわかりません。
そこで、愚直にゲートを並べての実装もしてみました。
Copy circ = QuantumCircuit(n_qubits) circ.x(range(n_qubits)) circ.h(range(n_qubits)) circ.barrier() for tt in t: # time evolution by H_ref for i in range(n_qubits): circ.rx(+2*(1-tt/T)*dt,i) circ.barrier() # time evolution by H_cost for i in range(n_qubits): circ.cnot(i,(i+1)%n_qubits) circ.rz(+2*tt/T*dt*3,(i+1)%n_qubits) circ.cnot(i,(i+1)%n_qubits) circ.barrier() circ.measure_all()
Copy # draw the circuit circ.draw(output="mpl", fold = 50)
<Figure size 3126.88x1047.48 with 1 Axes>
CNOTは64個使われています。
最初に述べたように、NISQでは個のCNOTも楽では有りませんので、これはNISQでは動かないと考えられます。
実際にIBMのマシン(ibmq_santiago)で実行してみましたが、ほぼランダムな状態に収束してしまいました。
QAAについて説明してみました。
NISQでは厳しく、FTQC向けなのでまだ先ですが、断熱定理という量子系の性質をうまく使った興味深いアルゴリズムです。
© 2024, blueqat Inc. All rights reserved