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.

組合せ多項式二値最適化のためのGrover適応探索

タグ: algorithm optimization oracle-based

Grover適応探索(GAS)は、二値変数上の多項式目的関数を最小化する手法です。Groverオラクルに「どの xx が f(x)<yf(x) < y を満たすか」という1つの問いを繰り返し投げ、より良い解が見つかるたびに閾値 yy を下げていきます Gilliam et al., 2021。

このページでは、QamomileのGASConverterを使って制約なしのポートフォリオ選択問題を解きます。

このチュートリアルは次の構成で進めます。

  1. JijModelingで問題を定式化します。

  2. 具体的なデータからインスタンスを作成します。

  3. GASConverterで現在の閾値に対応するGrover回路を構築します。

  4. サンプリングして最良の候補を保持し、停止条件を満たすまで繰り返します。GASは単一の回路ではなくハイブリッドなループです。

背景

Grover探索は、目的の状態の位相を反転させて区別するオラクルを受け取り、振幅増幅によってその測定確率を高めます。これは判定問題を解く手続きです。固定された判定条件はどの状態が条件を満たすかを示すだけで、どれが最良かは示しません。

GASは判定条件を変更することで、これを最小化に応用します。f(x)<yf(x) < y を満たす候補に対応する量子状態の位相を反転させて区別し、候補をサンプリングします。候補の目的関数値が現在の閾値を下回る場合、古典レイヤーが yy をその値に更新します。量子回路が一度に1つの固定された問いに答え、古典レイヤーが閾値を更新するという処理を繰り返します。

問題設定

このチュートリアルでは、GASを適用する問題例としてポートフォリオ選択問題を扱います。

nn 個の資産(株式、債券など)があり、それぞれを購入するかどうかという二値の選択をします。リターンを最大化しつつリスクを最小化したいのですが、次のような対立があります。

  • μ\mu は各資産に期待される収益性を表します

  • Σ\Sigma は資産同士の連動の仕方を表します(相関のある資産はリスクを増幅させます)

  • qq はリターンに対してリスクをどれだけ重視するかを制御します

相関リスクを過度に負うことなく、できるだけ大きな収益を得られる資産の部分集合を選ぶ必要があります。

min⁡x∈{0,1}n(qxTΣx−μTx)\min_{x\in \lbrace 0 , 1 \rbrace^n} \big( q x^T \Sigma x - \mu^T x \big)
Loading...

以下のインスタンスは9個の資産を持ちます。

名前期待収益分散
資産12212
資産2415
資産31910
資産4318
資産52314
資産6220
資産7511
資産82516
資産9313

JijModelingの問題を上記のデータで評価すると、OMMXインスタンスが得られます。

アルゴリズム

GASでは、候補解の目的関数値を閾値 yy として設定し、それを下回る候補をGrover探索で探します。量子回路から得られた候補を古典計算で評価し、より良い候補が見つかれば閾値を更新するという処理を、停止条件を満たすまで繰り返します。ここでの yy は候補解ではなく、目的関数値に対する閾値です。GASは、判定条件 f(x)<yf(x) < y を満たす候補に対応する量子状態の位相を反転させ、ほかの候補と区別します。Groverアンザッツは次の3つの要素から構成されます。

  • AyA_y:準備演算子です。量子辞書の状態 ∑x∣x,f(x)−y⟩\sum_x \ket{x, f(x) - y} を構築することで、各入力に f(x)−yf(x) - y を対応付けます。回路実装は Gilliam et al., 2021 により、QFTを用いる方法で与えられています。レジスタは f(x)−yf(x) - y を2の補数で保持するため、判定条件を満たす候補は、最上位ビット(MSB)が 1 になるものとして識別できます。

  • OyO_y:位相オラクルです。判定条件 f(x)<yf(x) < y を満たす候補の位相を反転させます。符号化された値 f(x)−yf(x) - y が負かどうかは最上位ビット(MSB)で判別できるため、そのMSBに作用する1つの ZZ ゲートで実装できます。

  • DD:拡散演算子で、位相を反転させて区別した状態の振幅を増幅します。XX 層に挟まれた1つの多重制御 ZZ ゲートで構成されます。

1回の反復では OyO_y を適用し、続いて Ay†A_y^\dagger、DD、AyA_y を適用します。位相反転 OyO_y だけでは測定確率は変わりません。それを振幅へ変換するのが反射 AyDAy†A_y D A_y^\dagger です。入力レジスタの測定で得られた候補を古典レイヤーで評価し、その目的関数値が現在の閾値を下回る場合にのみ、yy をその値に更新します。

残る問題は、Grover演算子を何回適用するかです。GASはこれに対して、改善が得られなかったラウンドのたびに少しずつ広がる範囲から繰り返し回数をサンプリングすることで答えます。

実装

Qamomileは、GASに用いる量子回路の実装をGASConverterとして提供しています。このセクションでは、その使い方と回路を構成する演算を紹介し、最後に古典計算のループと組み合わせてGASを実装します。

GASConverterはOMMXインスタンスを受け取り、QUBO/HUBO形式の問題へ変換します。transpile()メソッドを使うと、指定したtranspilerに対して適応探索で使うGrover回路を構築できます。

Grover回路の実装

GASConverter.transpile()は内部で以下のサンプリング用量子カーネルを構築し、transpilerに渡します。可視化するには、同じ量子カーネルに対してTranspiler.to_blockとMatplotlibDrawer.drawを使います。

出力レジスタの幅は自由なパラメータではありません。すべての xx について f(x)−yf(x) - y を保持できる必要があり、足りないと2の補数表現が巡回して、オラクルが判定している符号ビットそのものが反転してしまいます。required_output_bits()は、与えた閾値に対してtranspile()が選ぶ幅を返します。

y=0に対する出力レジスタの幅: 9 量子ビット
<Figure size 40129x1616 with 1 Axes>

構成要素の確認

AyA_y はQFTによる位相エンコーディングから ∑x∣x,f(x)−y⟩\sum_x \ket{x, f(x) - y} を準備します。

<Figure size 15426x2432 with 1 Axes>

DD は入力レジスタを一様重ね合わせのまわりで反転させます。

<Figure size 902.5x1192 with 1 Axes>

古典レイヤー

QamomileのGASConverterは、指定した閾値に対するGrover回路の構築と、測定結果を候補解に変換する機能を提供します。一方、候補解の評価や閾値の更新、Grover反復回数の調整、停止条件の判定といった、探索全体を制御する古典計算部分は含まれていません。そのため、GASによる最適化を行うには、これらの処理を自分で実装する必要があります。以下の関数は、その実装例です。

converter.transpile()とconverter.decode()を量子プリミティブとして使い、GASの古典的な外側ループを実装しています。ランダムな候補 xx と y=f(x)y = f(x) から始め、Grover回路をサンプリングし、より良いサンプルが得られるたびに暫定解を更新します。改善のないラウンドがmax_no_improvement回続いた時点で探索を終了します。

  • converter.transpile(transpiler, y=y, num_iterations=num_iterations)は、現在の閾値 yy と指定したGrover反復回数に対応するGrover回路を構築します。

  • executable.sample(executor, shots=256)はバックエンド上で回路を実行します。Groverであっても、NISQデバイスはノイジーであるため複数ショットが必要です。

  • converter.decode(result)は生のビット列カウントを決定変数の割り当てにマッピングして返します。

結果

このセクションでは、ポートフォリオ選択問題にGASを実行し、得られた目的関数値を全探索による最適値と比較して結果を検証します。

lambはGrover繰り返し回数のサンプリング範囲が広がる速さを、max_no_improvementは停止条件を決めます。

[GAS] 初期化
[GAS] n=9, lambda=1.2
[GAS] 初期状態: x=[0, 1, 1, 1, 0, 1, 0, 0, 1], y=57.0, k=1

[GAS] イテレーション 1 | 現在のy=57.0, k=1.000000, Grover繰り返し回数=0
[GAS] 候補: x=[1, 0, 1, 1, 1, 0, 0, 0, 0], y=-23.0
[GAS] 改善を検出 -> 候補を採用し、kを1にリセットします

[GAS] イテレーション 2 | 現在のy=-23.0, k=1.000000, Grover繰り返し回数=0
[GAS] 候補: x=[1, 0, 1, 1, 1, 0, 0, 0, 0], y=-23.0
[GAS] 改善なし -> 現在の解を維持し、kをスケーリングします: 1.000000 -> 1.200000

[GAS] イテレーション 3 | 現在のy=-23.0, k=1.200000, Grover繰り返し回数=0
[GAS] 候補: x=[1, 0, 1, 1, 1, 0, 0, 0, 0], y=-23.0
[GAS] 改善なし -> 現在の解を維持し、kをスケーリングします: 1.200000 -> 1.440000

[GAS] イテレーション 4 | 現在のy=-23.0, k=1.440000, Grover繰り返し回数=0
[GAS] 候補: x=[1, 0, 1, 1, 1, 0, 0, 0, 0], y=-23.0
[GAS] 改善なし -> 現在の解を維持し、kをスケーリングします: 1.440000 -> 1.728000

[GAS] イテレーション 5 | 現在のy=-23.0, k=1.728000, Grover繰り返し回数=1
[GAS] 候補: x=[1, 0, 0, 0, 1, 0, 0, 1, 0], y=-28.0
[GAS] 改善を検出 -> 候補を採用し、kを1にリセットします

[GAS] イテレーション 6 | 現在のy=-28.0, k=1.000000, Grover繰り返し回数=0
[GAS] 候補: x=[1, 0, 1, 1, 1, 0, 0, 0, 0], y=-23.0
[GAS] 改善なし -> 現在の解を維持し、kをスケーリングします: 1.000000 -> 1.200000

[GAS] イテレーション 7 | 現在のy=-28.0, k=1.200000, Grover繰り返し回数=0
[GAS] 候補: x=[1, 0, 1, 1, 1, 0, 0, 0, 0], y=-23.0
[GAS] 改善なし -> 現在の解を維持し、kをスケーリングします: 1.200000 -> 1.440000

[GAS] イテレーション 8 | 現在のy=-28.0, k=1.440000, Grover繰り返し回数=1
[GAS] 候補: x=[1, 0, 0, 0, 1, 0, 0, 1, 0], y=-28.0
[GAS] 改善なし -> 現在の解を維持し、kをスケーリングします: 1.440000 -> 1.728000

[GAS] イテレーション 9 | 現在のy=-28.0, k=1.728000, Grover繰り返し回数=0
[GAS] 候補: x=[1, 0, 1, 1, 1, 0, 0, 0, 0], y=-23.0
[GAS] 改善なし -> 現在の解を維持し、kをスケーリングします: 1.728000 -> 2.073600

[GAS] イテレーション 10 | 現在のy=-28.0, k=2.073600, Grover繰り返し回数=2
[GAS] 候補: x=[1, 0, 0, 0, 1, 0, 0, 1, 0], y=-28.0
[GAS] 改善なし -> 現在の解を維持し、kをスケーリングします: 2.073600 -> 2.488320

[GAS] 10 回のイテレーション後に終了。最良解: x=[1, 0, 0, 0, 1, 0, 0, 1, 0], y=-28.0
選択された資産: [1, 5, 8], 目的関数値: -28.0

探索はmax_no_improvement回続けて解が改善しなくなった時点で停止します。これはヒューリスティックな規則であり、それ自体が返された解の最適性を保証するものではありません。今回は資産が 9 個であり、29=5122^9 = 512 通りの割り当てをすべて列挙できるため、厳密な全探索の結果と照合して確認しましょう。

GAS   : x=[1, 0, 0, 0, 1, 0, 0, 1, 0], 目的関数値=-28.0
全探索 : x=[1, 0, 0, 0, 1, 0, 0, 1, 0], 目的関数値=-28.0

GASは全探索の最適解と一致しました。

まとめ

このノートブックでは、次のことを行いました。

  • 制約なしのポートフォリオ問題をGrover適応探索で解きました。量子回路が「どの xx が f(x)<yf(x) < y を満たすか」に答え、古典ループがより良い候補を得たときに閾値 yy を更新します。

  • GASをQamomileで実装する例を紹介しました。量子側の処理はGASConverterとして提供されています。transpile()が現在の閾値とGrover反復回数に対応するGrover回路を構築し、decode()がビット列カウントをOMMXを通じて決定変数に戻します。

  • ポートフォリオ選択問題を例にGASを実行し、得られた目的関数値が全探索による最適値と一致することを確認しました。

References
  1. Gilliam, A., Woerner, S., & Gonciulea, C. (2021). Grover Adaptive Search for Constrained Polynomial Binary Optimization. Quantum, 5, 428. 10.22331/q-2021-04-08-428