目的
前回、Qiskit textbook の Solving combinatorial optimization problems using QAOA の中の難しいなと感じる式を証明してみたが、その上で読み直してもすぐにはよく分からないので、適当に行間を埋めてみたい。
但し、textbook を読んでも原論文 A Quantum Approximate Optimization Algorithm を読んでも、何故問題のハミルトニアンとミキサーを交互に混ぜるのか?などは見えておらず、あくまで雰囲気だけの記事である。
記号
-
x=(x1,x2,x3,x4)∈{0,1}4, ∣x⟩=∣x1x2x3x4⟩
- ∣s⟩=H⊗4∣0⟩⊗4=∑x∈{0,1}4∣x⟩=∣0000⟩+∣1000⟩+∣0100⟩+⋯+∣1111⟩
-
I=(1001), X=(0110), Z=(100−1)
- Z1=Z⊗I⊗I⊗I
- Z2=I⊗Z⊗I⊗I
- Z3=I⊗I⊗Z⊗I
- Z4=I⊗I⊗I⊗Z
-
p≥1 なる自然数
- β=(β1,⋯,βp)∈Rp
- γ=(γ1,⋯,γp)∈Rp
MAXCUT 問題を追いかける
MAXCUT 問題は、無向グラフの頂点を 2 色に塗り分ける時、辺(枝)で繋がっている隣接頂点同士が異なる色の場合に辺をカットするという試行を考えた時に、最大のカット数は幾つになるか?を求める問題である。
コスト関数を作る
教材ではいきなり問題のハミルトニアンが出てきて眺めているうちに問題が解けてしまいよく分からないことになるので、最初から Appendix を見つつハミルトニアンを作っていく。
この教材の例題では n=4 で、コスト関数 C(x) は具体的には
C(x)=x1(1−x2)+x2(1−x1)+x2(1−x3)+x3(1−x2)+x3(1−x4)+x4(1−x3)+x4(1−x1)+x1(1−x4)(1)
となる。ここで、0 の頂点を x1 に、1 の頂点を x2 に、2 の頂点を x3 に、3 の頂点を x4 に割り当てている。
この関数は xi(1−xj)+xj(1−xi) の形の項のペアを 4 つ連結したものであり、xi=xj で 0 となり、xi=xj で 1 となる。
x=x1x2x3x4 の順番で書くことにし、具体的に C(x) を計算すると、C(0000)=0,C(1000)=2,C(0100)=2,C(1100)=2,C(0010)=2,C(1010)=4,C(0110)=2,C(1110)=2,C(0001)=2,C(1001)=2,C(0101)=4,C(1101)=2,C(0011)=2,C(1011)=2,C(0111)=2,C(1111)=0 である。この時点で雰囲気的に明らかなのだが、コストが最大になっている 1010 と 0101 が問題の解であって、これを量子アルゴリズムで求めましょうということになる。
ハミルトニアンを作る
教材に従い、スペクトル分解のような形のハミルトニアンを作ると以下のようになる。
H=x∈{0,1}4∑C(x)∣x⟩⟨x∣=2∣1000⟩⟨1000∣+2∣0100⟩⟨0100∣+2∣1100⟩⟨1100∣+2∣0010⟩⟨0010∣+4∣1010⟩⟨1010∣+2∣0110⟩⟨0110∣+2∣1110⟩⟨1110∣+2∣0001⟩⟨0001∣+2∣1001⟩⟨1001∣+4∣0101⟩⟨0101∣+2∣1101⟩⟨1101∣+2∣0011⟩⟨0011∣+2∣1011⟩⟨1011∣+2∣0111⟩⟨0111∣(2)
ハミルトニアンの期待値と MAXCUT 問題の解
ここで、実は求めたい状態があって、それは MAXCUT 問題の 2 つの解に対応する状態
∣ψopt⟩=21(∣1010⟩+∣0101⟩)
である。この状態に対するハミルトニアンの期待値は ⟨ψopt∣H∣ψopt⟩=4 でコスト関数の最大値をとる形で最大となる。
では、この ∣ψopt⟩ はどこからくるのか?というと、あるパラメータ付きのユニタリ演算子、従って PQC(パラメータ付き量子回路)U(β,γ) を使って、∣ψopt⟩←∣ψ(β,γ)⟩:=U(β,γ)∣s⟩ という形で得られることになっている。
つまり、⟨ψ(β,γ)∣H∣ψ(β,γ)⟩ が最大値(ここでは 4)をとるようにパラメータ β と γ を最適化し、その時に βopt と γopt になったとすると、∣ψopt⟩≈∣ψ(βopt,γopt)⟩ が得られたと考えることにしますというストーリである。
MAXCUT 問題の最終的な解は ∣ψ(βopt,γopt)⟩ を計算基底について測定することで、概ね ∣1010⟩ と ∣0101⟩ が 1/2 ずつくらいの確率で得られるであろうことから x1=1,x2=0,x3=1,x4=0 或は x1=0,x2=1,x3=0,x4=1(つまり頂点を交互に赤のグループと青のグループに割り振る)が解として得られる。
ストーリーが分かったところで、(2) 式のハミルトニアンを量子回路として実装する必要がある。これはどうすれば良いのであろうか?ここで前回の記事の出番である。
量子回路の実装
問題のハミルトニアン
前回の記事の結果を使って (1) を書き直すと、
H=(21−Z1)(21+Z2)+(21−Z2)(21+Z1)+⋯=21−Z1Z2+21−Z2Z3+21−Z3Z4+21−Z4Z1=2I−21(Z1Z2+Z2Z3+Z3Z4+Z4Z1)
となる。これが (2) 式と等しいというのが前回確認した内容であった。
定数項 2I は期待値をとる時に常に定数 2 の寄与であるので最適化の考察上は除外して問題ない。よって、textbook に倣い
HP=Z1Z2+Z2Z3+Z3Z4+Z4Z1=(Z⊗Z⊗I⊗I)+(I⊗Z⊗Z⊗I)+(I⊗I⊗Z⊗Z)+(Z⊗I⊗I⊗Z)(3)
の部分だけを考える。負符号も取り去ったので、この “新しい” ハミルトニアンに対しては期待値を最小化する形での最適化を行うことになる。
ミキシングハミルトニアン
“ミキサー” と呼んでいる文献もある。ここはまったく理解できていないのでそのまま受け入れる。
HB=(X⊗I⊗I⊗I)+(I⊗X⊗I⊗I)+(I⊗I⊗X⊗I)+(I⊗I⊗I⊗X)
パラメータ付き量子回路 U(β,γ)
∣ψopt⟩←∣ψ(β,γ)⟩:=U(β,γ)∣s⟩ という状態を作る回路が必要であるが、ここも理解できていないのでそのまま受け入れる。
パラメータ β=(β1,⋯,βp)∈Rp と γ=(γ1,⋯,γp)∈Rp に対して
U(β,γ)=p(e−iβpHBe−iγpHP)(e−iβp−1HBe−iγp−1HP)⋯(e−iβ1HBe−iγ1HP)
という 2p 個のユニタリ行列の積を考える。e−iγiHP は Rzz ゲートで、e−iβiHB は Rx ゲートで実装が可能である。
ここまでで必要な回路の実装の道筋が見えた。後は回路のパーツを組み合わせて、ハミルトニアン HP の期待値を COBYLA オプティマイザを使って最小化し、パラメータの最適値 βopt と γopt を求めることで、MAXCUT 問題の解を得ることができる。
最後に期待値の計算の部分を眺めて終わりにしよう。
期待値の計算
∣ψ(β,γ)⟩=U(β,γ)∣s⟩=α0000∣0000⟩+α1000∣1000⟩+⋯+α1111∣1111⟩
となったとする。この時 HP に対する期待値を計算したい。
いきなりは難しいので、練習問題として ∣ψ⟩=∣1100⟩ について期待値を見てみよう:
== ⟨ψ∣HP∣ψ⟩ ⟨1100∣(Z⊗Z⊗I⊗I)+(I⊗Z⊗Z⊗I)+(I⊗I⊗Z⊗Z)+(Z⊗I⊗I⊗Z)∣1100⟩ (−1)(−1)+(−1)+(1)+(−1)=0
である。もう 1 つのサンプルとして ∣ψ⟩=∣1010⟩ でも試してみよう:
== ⟨ψ∣HP∣ψ⟩ ⟨1010∣(Z⊗Z⊗I⊗I)+(I⊗Z⊗Z⊗I)+(I⊗I⊗Z⊗Z)+(Z⊗I⊗I⊗Z)∣1010⟩ (−1)+(−1)+(−1)+(−1)=−4
である。他のケースを見ても分かるが、1010 のようなビット列を考えた時に、先頭と末尾を繋げてリング状にした場合に、0 と 1 が切り替わるところの個数だけ −1 し、00 や 11 のように同じビットが連なるところでは +1 する形で求まる。
よって、この “部分的な期待値” を計算する関数を f とでもすると、
f(0000)=4, f(1000)=0,⋯, f(1100)=0,⋯, f(1010)=−4,⋯
ようになっており、全体の期待値は
⟨ψ(β,γ)∣HP∣ψ(β,γ)⟩=∣α0000∣2f(0000)+∣α1000∣2f(1000)+⋯+∣α1111∣2f(1111)
で求まる。これが textbook の関数 compute_expectation
の実装である。
まとめ
大分長くなってしまったが、Qiskit textbook の Solving combinatorial optimization problems using QAOA の前半部分の例題「MAXCUT」について全体の流れを「よく分からないところはそういうものとして割り切って受け入れる」形で眺めてみた。
読み返しつつまとめてみてもまだまだスッキリとはしないので、また何度も読み返して考察する必要があるように感じる。他のケースでの問題設定での解を求めてみたりもしたい。
Discussion