QAAってなに?

QAA(Quantum Adiabatic Algorithm)は、あるコスト関数の最小値を発見するための量子アルゴリズムです。
アルゴリズムには比較的に多くのCNOTゲートを必要とするため、NISQ(雑音ありマシン)よりもFTQC(誤り耐性マシン)用と考えられます。

"多くのCNOT"の定義が難しいところです。QAAではCNOTが $10^{2}$ 個ぐらいは平気で出てきますが、NISQでは $10^{1}$ 個のCNOTでも楽では有りません。

コスト関数最小化を量子計算に持ち込むために、コスト関数はある量子系のハミルトニアンに対応させ、最小値はその最低エネルギー状態に対応させます。
すなわち、与えられたハミルトニアンの最低エネルギー状態（未知）をなんとかして実現し、最後にその量子状態を測定する（＝知る）ことで、問題を解きます。
QAAでは、量子断熱定理と呼ばれる量子系の性質をうまく使って、最低エネルギー状態を実現します。

量子断熱定理

例えば以下の解説記事にある通り、

「量子化された定常状態にある系は系を無限にゆっくり動かすとき状態が変化しない」
というのが量子断熱定理です。
今回は、これを都合よく使って
「あるハミルトニアンにおいて最低エネルギー状態にある量子は、ハミルトニアンを無限にゆっくり変化させても、その時々のハミルトニアンにおける最低エネルギー状態になっている」
とします。

これにより、以下のことを実現できれば良いとわかります。

あるハミルトニアンにおいて最低エネルギー状態にある量子を準備する。
与えられたハミルトニアンの元での量子状態の時間変化（次の瞬間に量子状態はどうなるか？）を計算する。
ハミルトニアンを無限にゆっくり変化させる仕組みを考える。

第一項目は、最低エネルギー状態が既知であるような（かんたんな）ハミルトニアン $H_{reference}$ を使ってしまえば解決できます。

第二項目は、シュレディンガー方程式が教えてくれます。ハミルトニアン $H$ の元での、 $\Delta t$ 秒後の量子状態は、ユニタリ変換 $U=e^{-iH\Delta t}$ を行うと得られます。今回、ハミルトニアンは刻々と変化していきますので、 $e^{-iH(t=2\Delta t)\Delta t}e^{-iH(t=\Delta t)\Delta t}e^{-iH(t=0)\Delta t}$ のようになります。

第三項目は、初期ハミルトニアン $H_{reference}$ と、解きたい問題に相当するコストハミルトニアン $H_{cost}$ に対して
$H(t) := (1-t/T)H_{ref.} + (t/T)H_{cost}$
とします。 $T$ は時間変化を行う秒数です。
$t=0$ では、系のハミルトニアンは $H_{ref.}$ で、時間が経過する毎にだんだんと $H_{ref.}$ は弱まって、 $H_{cost}$ が強くなり、最後は $H_{cost}$ だけになります。
断熱定理によれば、このとき量子は $H_{cost}$ の最低エネルギー状態にあるはずです。

「無限に」の部分は有限の計算資源である実コンピュータでは不可能なので、諦めます。
すなわち時間方向を有限のステップに区切る（差分法）こととします。

時間変化のゲート表現テクニック(Trotter展開)

コンセプトは先に述べたとおりですが、時間変化を表すユニタリ変換 $U=e^{-iH\Delta t}$ を、なんとか量子コンピュータで使えるゲートで表現する必要があります。
いま、ハミルトニアン $H$ は初期ハミルトニアンとコストハミルトニアンの和です。
$H(t) := (1-t/T)H_{ref.} + (t/T)H_{cost}$
よくある問題設定では、

初期ハミルトニアン単体ではユニタリ変換が簡単に実装できて、コストハミルトニアン単体でも簡単に実装できる。
けど、
その和のハミルトニアンでは簡単に実装できない。

となります。
この場合の解決方法が、Trotter展開です。
Trotter展開は、演算子の指数法則のようなものです。近似的に、

$e^{-iH(t)\Delta t} = e^{-i(1-t/T)H_{ref.}\Delta t}e^{-i(t/T)H_{cost} \Delta t}$

が成り立ちます。 $\Delta t$ が小さければ近似精度が高くなります。
要は、ハミルトニアンの和で描かれている場合の時間発展は、個々のハミルトニアンにおける時間発展の連続操作で近似できると言っています。
我々は、時間方向のステップ数を十分細かく取っておくことで、この近似を正当化します。

実装

上記のコンセプトを実装します。
SDKとしてqiskitを使っていますが、blueqat等のSDKでも簡単に真似できます。
4ノードのMAX CUT 問題を解きます。

初期の（かんたんな）ハミルトニアンとしては、横磁場 $\sum X_{i}$ を使います。
このハミルトニアンの最低エネルギー状態は $|- \rangle ^{\otimes n}$ です。
この状態は、全量子ビットにそれぞれ $X$ ゲートと $H$ ゲートをかけることで作れます。

コストハミルトニアンは、 $\sum Z_{i}Z_{i+1}$ となります。

解である最低エネルギー状態は"1010"と"0101"の2つあります。
この場合、量子状態はこの2つの均等な重ねあわせ状態に収束しますので、測定すると確率50%でランダムに片方が出ます。

時間発展の秒数は $T=2$ 、ステップ数は $N=8$ とします。

#!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では $10^{1}$ 個のCNOTも楽では有りませんので、これはNISQでは動かないと考えられます。
実際にIBMのマシン(ibmq_santiago)で実行してみましたが、ほぼランダムな状態に収束してしまいました。

まとめ

QAAについて説明してみました。
NISQでは厳しく、FTQC向けなのでまだ先ですが、断熱定理という量子系の性質をうまく使った興味深いアルゴリズムです。

量子断熱時間発展(QAA)のチュートリアル

量子熊

QAAってなに?

量子断熱定理

時間変化のゲート表現テクニック(Trotter展開)

実装

まとめ