Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

QSVT Filteringによるグラフ分割問題の求解

タグ: algorithm optimization oracle-based

本チュートリアルでは、Quantum Singular Value Transform(QSVT)を使って、与えられたハミルトニアンの基底エネルギーを求め、グラフ分割問題を解く方法を説明します。

Lin and Tongの基底エネルギーアルゴリズムLin & Tong, 2020は、フィルタリングによってコストハミルトニアンの最小固有値を求めます。閾値パラメータμ\muを1つ決めると、Linear Combination of Unitaries(LCU)によってH−μIH - \mu Iのブロックエンコーディングを構築できます。さらにsign関数のQSVT近似を用いて、閾値パラメータμ\muの片側にある固有空間へのprojectorを作ります。post-selectionを通過したショットの割合が、μ\muをどちらへ動かせばよいかを古典的な二分探索に伝えます。

本チュートリアルでは、この手順をグラフ分割問題に適用し、ブロックエンコーディングの構築、単一の閾値での評価、二分探索による基底エネルギーの推定までを示します。

問題設定

グラフ分割は、頂点を同じ大きさの2つのグループへ分けながら、切断される辺の数をできるだけ少なくする問題です。ここでは等サイズ制約のもとで切断辺数を最小化します。この制約はto_huboがペナルティ項として目的関数に取り込みます。

グラフ分割問題そのものの詳細はQAOAによるグラフ分割を参照してください。

Loading...
<Figure size 500x500 with 1 Axes>

アルゴリズム

イジングコストハミルトニアンをHHと書き、閾値μ\muを1つ選びます。アルゴリズムが扱うのはシフトした演算子H−μIH - \mu Iで、その固有値はEi−μE_i - \muです。残したい固有状態でちょうど負に、それ以外で正になります。したがって両者を分けるのはsign関数の役目です。

ブロックエンコーディングは、ユニタリでない演算子をより大きなユニタリUUの1つのブロックとして埋め込みます。LCUはH−μIH - \mu IをPauli列の重み付き和として書くことでこれを構築します。その代償が正規化定数α′\alpha'であり、実際にエンコードされるのは正規化された演算子(H−μI)/α′(H - \mu I) / \alpha'です。そのスペクトルは[−1,1][-1, 1]に収まります。このブロックは、ancillaレジスタ、すなわちsignalレジスタがすべて0と測定されることで選択されます。

続いてQSVTは、エンコードされた演算子をその多項式で置き換えます。位相Φ\Phiが与えられると、次の交替列を適用し、

R(ϕ0),  U,  R(ϕ1),  U†,  …R(\phi_0),\; U,\; R(\phi_1),\; U^\dagger,\; \dots

同じブロックにp ⁣((H−μI)/α′)p\!\left((H - \mu I)/\alpha'\right)を残します。ここでppとしてsign関数の近似を選べば、

p ⁣(H−μIα′)≈sign⁡ ⁣(H−μIα′),p\!\left(\frac{H - \mu I}{\alpha'}\right) \approx \operatorname{sign}\!\left(\frac{H - \mu I}{\alpha'}\right),

このブロックは鏡映RRになります。すなわちμ\muより下の固有空間には-1として、上の固有空間には+1として作用します。

鏡映はまだprojectorではありませんが、Pμ=(I−R)/2P_\mu = (I - R)/2はprojectorであり、しかも2つのユニタリの和なので、量子ビットを1つ追加したHadamard testによって確率的に実現できます。一様重ね合わせ∣φ0⟩=H⊗n∣0⟩|\varphi_0\rangle = H^{\otimes n}|0\rangleから出発したとき、すべてのancillaが0と測定されるショットの割合は次の量を推定します。

P(μ)=∥Pμ∣φ0⟩∥2=#{i:Ei<μ}2n,P(\mu)=\lVert P_\mu |\varphi_0\rangle \rVert^2 = \frac{\#\{i : E_i < \mu\}}{2^n},

これはμ\muより下にあるスペクトルの割合です。この値を、古典的な二分探索で探索方向を決める判定条件として用います。∣φ0⟩|\varphi_0\rangleのなかでμ\muより下の固有状態が重みを持つときに限り、この値は0から離れた値をとります。

探索そのものはLin and TongのAlgorithm 1Lin & Tong, 2020です。固有値は[c−α,c+α)[c-\alpha, c+\alpha)に存在します。ここでα\alphaはHH単体の正規化定数、ccはその定数項です。ある閾値μ\muを基底エネルギーλ0\lambda_0と比較して考えます。μ\muが[c−α,λ0)[c-\alpha, \lambda_0)にあるときは固有値がすべて除かれ、P(μ)=0P(\mu)=0となります。区間[λ0,λ1)[\lambda_0,\lambda_1)では基底の固有空間だけが残り、縮退度をddとしてγ2=d/2n\gamma^2 = d/2^nを与えます。λ1\lambda_1より上では確率は増える一方です。したがって探索は[c−α,c+α)[c-\alpha,c+\alpha)を間隔hhのグリッドに分割し、P(μ)P(\mu)がτ=γ2/2\tau = \gamma^2/2を超えるかどうかで進む方向を決めます。

成否を分ける入力が2つあります。γ\gammaは初期状態の重なりの下界ですが事前には分からないため、仮定して与えるしかありません。またhhは(これも未知の)スペクトルギャップより小さくとる必要があります。最後に、近似誤差によって推定したP(μ)P(\mu)が単調でなくなる場合があります。そのため探索は1点だけを信用せず、連続する2つのグリッド点(Bk,Bk+1)(B_k, B_{k+1})を組にして評価します。

Qamomileによる実装

Qamomileは、上で説明した固有状態フィルタリングのアルゴリズムをqamomile.optimization.qsvt_eigenstate_filterのQSVTEigenstateFilterConverterとして提供しています。このコンバーターは問題ハミルトニアンのブロックエンコーディングの構築、フィルタの位相の計算、probe回路の組み立て、そして測定サンプルのpost-selectionとデコードまでを行うため、手順全体を問題インスタンスから直接実行できます。以下ではまずこれを使って閾値を1つ試し、次にコンバーターが組み立てる構成要素を順に見て、最後に二分探索を実行します。

ただし内部のパラメータの多くが解の品質を左右するため、以下ではそれぞれのパラメータと選び方を説明します。

イジングハミルトニアンの定数項はブロックエンコーディングから除いてあります。この手法の性能は正規化定数α\alphaに依存しており、恒等演算子の項はこの値を大きくしてしまうためです。一方で定数のオフセットはすべての固有値を等しくずらすだけなので、どの状態が最良かは変わりません。normalization(α\alpha)とenergy_offset(cc)の2つが揃ってスペクトルの範囲を与え、閾値はこの区間のなかから選ぶことになります。

alpha=3.0  offset=6.0
every eigenvalue lies in [3.0, 9.0]
levels=[3. 5. 7. 9.]  ground=3.0 (2-fold)

閾値を1つ試す

transpileはμ\muを回路に埋め込むため、閾値ごとに個別のコンパイルが必要です。フィルタはデフォルトでμ\muより下の固有空間を残します。これは最小固有値(基底エネルギー)を探索したい場合に必要な向きです。

degreeとdeltaは対で決まります。deltaは多項式の遷移領域の幅を定め、degreeはChebyshev展開の次数で、その遷移を表現できるだけ大きくとる必要があります。

分解能は次の式で与えられます。

Δ=min⁡i∣Ei−μ∣α+∣μ−c∣\Delta = \frac{\min_i |E_i-\mu|}{\alpha + |\mu - c|}

ここでEiE_iは固有値で、その他のパラメータはこれまでに定義したものです。分解能を知るには基底エネルギーを事前に知っている必要がある、という状況がしばしば起こります。実際には分解能を上回るように、値を推測するか上界を見積もることになります。degreeはおおよそO(1/Δ)O(1/\Delta)で増えます。

以下ではμ=4\mu=4としてアルゴリズムを実演します。このとき上回るべき分解能はΔ=∣4−3∣3+∣4−6∣=1/5\Delta = \frac{|4-3|}{3 + |4 - 6|} = 1/5であり、delta=8とすれば遷移領域の幅がこのギャップに合い、degree=21でそれを表現できます。対の取り方を誤っても精度が静かに落ちるわけではなく、∣p∣≤1|p| \le 1のチェックによってその場で棄却されます。

probe filter: degree=21, delta=8 -> 22 phases
p(mu=4.0) = 0.0310   (exact: 0.0312)

パラメータから定まる多項式近似に対応する位相因子の計算には、外部ライブラリのpyqspを使っています。

Converterはprojectorの量子回路を構築します。その回路を実行し、サンプルのカウントからsuccess_probabilityメソッドで成功確率を求めます。(上の厳密計算は精度を確認するための参照値です)

構成要素

transpileは3つの回路を入れ子に合成します。その順に描画すると、ブロックエンコーディングがどのようにprojectorへ変わっていくかが分かります。

図を読みやすく保つため、位相ベクトルは4要素に短くしてあります(上で使った22要素ではありません)。

alpha' = 5.0   signal=4  system=6

1. ブロックエンコーディング UU

イジングハミルトニアンはユニタリの線形結合として書かれ、PREPARE⁡\operatorname{PREPARE}、SELECT⁡\operatorname{SELECT}、PREPARE⁡†\operatorname{PREPARE}^\daggerとして実現されます。PREPARE⁡\operatorname{PREPARE}は係数の振幅をsignalレジスタに載せ、SELECT⁡\operatorname{SELECT}はsignalの状態に応じて対応するPauli-ZZ項をsystemに作用させ、PREPARE⁡†\operatorname{PREPARE}^\daggerがそれをuncomputeします。

得られるのは、左上のブロック、つまりsignalレジスタがすべて0と測定される部分が(H−μI)/α′(H - \mu I)/\alpha'となるようなユニタリです。そのブロックの外側は利用できないため、すべてのショットをそこでpost-selectする必要があります。

<Figure size 1789.5x1320 with 1 Axes>

2. QSVTの交替列

ブロックエンコーディングが与えられると、qmc.qsvtは次を適用します。

R(ϕ0),  U,  R(ϕ1),  U†,  R(ϕ2),  U,  …R(\phi_0),\; U,\; R(\phi_1),\; U^\dagger,\; R(\phi_2),\; U,\; \dots

ここでUUは上で構築したブロックエンコーディング、R(ϕ)=eiϕ(2Π−I)R(\phi) = e^{i\phi(2\Pi - I)}であり、Π\Piはsignalレジスタをすべて0の状態へ射影します。この一連の列はすべてprimitiveが担当します。位相回転用の補助量子ビットを自前で確保し、UUとU†U^\daggerを交互に並べ、位相を適用します。

その効果は、encodeされた演算子をその多項式で置き換えることです。pyqspが生成した位相を使うと、この多項式はsign\mathrm{sign}を近似するため、良いブロックはμ\muの片側の固有空間に関する鏡映になります。

<Figure size 3853.5x896 with 1 Axes>

3. Lin & Tongのprojector

目標は、この鏡映を射影Pμ=(I±R)/2P_\mu = (I \pm R)/2に変えることです。しかしこのprojectorはユニタリではないため、回路でそのまま適用することはできません。

鍵になるのは、これがIIとRRという2つのユニタリの和である点です。そのためHadamard testを使えば確率的に実現できます。このテストではprobe量子ビットと呼ぶancillaを1つ使い、恒等演算子の分岐と鏡映の分岐をコヒーレントに選択させます。probe量子ビットを重ね合わせにし、その制御のもとでQSVTの鏡映を作用させ、2つ目のHadamardで2つの分岐を干渉させます。probe量子ビットが0と測定されれば、PμP_\muが作用した分岐であることが分かります。このアルゴリズムに成功確率という概念があるのはそのためであり、post-selectionをprobeとsignalレジスタの両方に対して行う理由もここにあります。

<Figure size 885x896 with 1 Axes>

二分探索

ここまでで、古典的な探索に必要なものは判定条件だけになりました。B(k)は「グリッド点xkx_kが残すべき固有空間を捉えている」という1ビットで、ループはアルゴリズムの節で述べたとおり、このビットを連続する2つずつ組にして消費します。

結果

探索を実行すると、基底エネルギーの位置を一切教えないままその範囲を絞り込めます。得られた閾値をフィルタに戻して与えれば基底状態そのものが準備でき、そこからサンプリングすることで分割が復元されます。

grid +3.50..+8.50  G=6  h=1.0  tau=0.0156
  k=2: B(+5.50)=1  B(+6.50)=1  ->  (1,1) U<-3  [+3.50, +6.50]
  refine: first B=1 at k=0 (+3.50)

lambda_0 in [+3.00, +3.50]   true lambda_0 = +3.00
decode filter: degree=41, delta=11 -> 42 phases
kept 531 of 20000 shots, 89.3% at the ground energy
most sampled partition: [1, 2, 5] | cut=3
<Figure size 500x500 with 1 Axes>

2つの三角形{0,3,4}\{0,3,4\}と{1,2,5}\{1,2,5\}は同じ分割を表すため、実行ごとにどちらが最上位に来ることもあります。対応する目的関数値(最小カット)は3です。

まとめ

本notebookでは次のことを行いました。

  • QSVTEigenstateFilterConverterを使ってグラフ分割問題のインスタンスをend-to-endで解き、三角柱グラフの一意な最適分割を復元しました。

  • このアルゴリズムが確率的である理由を確認しました。Pμ=(I−R)/2P_\mu = (I - R)/2はユニタリではないためHadamard testで実現され、すべてのショットをprobeとsignalレジスタの両方でpost-selectする必要があります。

  • すべてのパラメータが、正規化されたギャップΔ=min⁡i∣Ei−μ∣/α′\Delta = \min_i |E_i - \mu| / \alpha'という1つの数値に帰着することを見ました。イジングの定数項をブロックエンコーディングから除くことが重要なのも、normalizationとenergy_offsetが対で報告されるのも、このためです。

References
  1. Lin, L., & Tong, Y. (2020). Near-optimal ground state preparation. 10.48550/ARXIV.2002.12508