QAAってなに?
QAA(Quantum Adiabatic Algorithm)は、あるコスト関数の最小値を発見するための量子アルゴリズムです。
アルゴリズムには比較的に多くのCNOTゲートを必要とするため、NISQ(雑音ありマシン)よりもFTQC(誤り耐性マシン)用と考えられます。
- "多くのCNOT"の定義が難しいところです。QAAではCNOTが
個ぐらいは平気で出てきますが、NISQでは10^{2} 個のCNOTでも楽では有りません。10^{1}
コスト関数最小化を量子計算に持ち込むために、コスト関数はある量子系のハミルトニアンに対応させ、最小値はその最低エネルギー状態に対応させます。
すなわち、与えられたハミルトニアンの最低エネルギー状態(未知)をなんとかして実現し、最後にその量子状態を測定する(=知る)ことで、問題を解きます。
QAAでは、量子断熱定理と呼ばれる量子系の性質をうまく使って、最低エネルギー状態を実現します。
量子断熱定理
例えば以下の解説記事にある通り、
というのが量子断熱定理です。
今回は、これを都合よく使って
「あるハミルトニアンにおいて最低エネルギー状態にある量子は、ハミルトニアンを無限にゆっくり変化させても、その時々のハミルトニアンにおける最低エネルギー状態になっている」
とします。
これにより、以下のことを実現できれば良いとわかります。
- あるハミルトニアンにおいて最低エネルギー状態にある量子 を準備する。
- 与えられたハミルトニアンの元での量子状態の時間変化(次の瞬間に量子状態はどうなるか?)を計算する。
- ハミルトニアンを無限にゆっくり変化させる仕組みを考える。
第一項目は、最低エネルギー状態が既知であるような(かんたんな)ハミルトニアン
第二項目は、シュレディンガー方程式が教えてくれます。ハミルトニアン
第三項目は、初期ハミルトニアン
とします。
断熱定理によれば、このとき量子は
「無限に」の部分は有限の計算資源である実コンピュータでは不可能なので、諦めます。
すなわち時間方向を有限のステップに区切る(差分法)こととします。
時間変化のゲート表現テクニック(Trotter展開)
コンセプトは先に述べたとおりですが、時間変化を表すユニタリ変換
いま、ハミルトニアン
よくある問題設定では、
- 初期ハミルトニアン単体ではユニタリ変換が簡単に実装できて、コストハミルトニアン単体でも簡単に実装できる。
けど、 - その和のハミルトニアンでは簡単に実装できない。
となります。
この場合の解決方法が、Trotter展開です。
Trotter展開は、演算子の指数法則のようなものです。近似的に、
が成り立ちます。
要は、ハミルトニアンの和で描かれている場合の時間発展は、個々のハミルトニアンにおける時間発展の連続操作で近似できると言っています。
我々は、時間方向のステップ数を十分細かく取っておくことで、この近似を正当化します。
実装
上記のコンセプトを実装します。
SDKとしてqiskitを使っていますが、blueqat等のSDKでも簡単に真似できます。
4ノードのMAX CUT 問題を解きます。
初期の(かんたんな)ハミルトニアンとしては、横磁場
このハミルトニアンの最低エネルギー状態は
この状態は、全量子ビットにそれぞれ
コストハミルトニアンは、
解である最低エネルギー状態は"1010"と"0101"の2つあります。
この場合、量子状態はこの2つの均等な重ねあわせ状態に収束しますので、測定すると確率50%でランダムに片方が出ます。
時間発展の秒数は
#!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がどれぐらい使われているのかがわかりません。
そこで、愚直にゲートを並べての実装もしてみました。
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()
# draw the circuit
circ.draw(output="mpl", fold = 50)
<Figure size 3126.88x1047.48 with 1 Axes>
CNOTは64個使われています。
最初に述べたように、NISQでは
実際にIBMのマシン(ibmq_santiago)で実行してみましたが、ほぼランダムな状態に収束してしまいました。
まとめ
QAAについて説明してみました。
NISQでは厳しく、FTQC向けなのでまだ先ですが、断熱定理という量子系の性質をうまく使った興味深いアルゴリズムです。