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.

OMMX Quantum Benchmarksの活用: Qamomileによる量子アルゴリズムの実装とベンチマーク

タグ: integration optimization variational

本チュートリアルでは、公開ベンチマークデータセットの問題にQamomileの量子アルゴリズムを適用し、その解の品質を同じワークフロー上で古典ソルバーと比較する方法を示します。

目標: QamomileでQAOAソルバーを構築し、OMMX Quantum BenchmarksデータセットからロードしたLow Autocorrelation Binary Sequences (LABS)インスタンスに対して実行し、ommx-pyscipopt-adapter経由で利用できる古典ソルバーSCIPと結果を比較します。QAOA側とSCIP側はどちらも同じommx.v1.Instanceを入力とするため、主な違いはアルゴリズムそのものです。そのため直接比較できます。

OMMX Quantum Benchmarksとは?

OMMX(Open Mathematical prograMming eXchange)は、数理最適化問題をツール間で受け渡すためのデータフォーマットです。ommx.v1.Instanceには目的関数、制約条件、決定変数のメタデータが格納されます。

OMMX Quantum Benchmarksは、このommx.v1.Instance形式で配布される最適化ベンチマークインスタンス集です。最初に提供されているデータセットはQOBLIB(Quantum Optimization Benchmarking Library)arXiv:2504.03832で、近年の量子最適化研究で使われている9つの問題ファミリーを収録しています。LABS、Market Split、Independent Set、Steiner Tree Packingなどが含まれます。

各ベンチマークインスタンスはommx.v1.Instanceとして表現されるため、QAOAConverterを含むommx.v1.Instance対応のQamomileワークフローは、追加の実装なしにこれらの問題を扱えます。さらに、参照解もommx.v1.Solution形式で含まれており、ベンチマークの評価に使用できます。同じInstanceはommx-pyscipopt-adapterのような古典側のOMMXアダプタにも渡せるので、1つの問題定義を量子・古典の両方のワークフローで使えます。

問題: Low Autocorrelation Binary Sequences (LABS)

LABSは、s=(s0,s1,…,sn−1)∈{−1,+1}n\boldsymbol{s} = (s_0, s_1, \dots, s_{n-1}) \in \{-1, +1\}^nというバイナリ系列のうち、非対角の自己相関

ck(s)=∑i=0n−k−1si si+k,k=1,2,…,n−1c_k(\boldsymbol{s}) = \sum_{i=0}^{n-k-1} s_i \, s_{i+k}, \qquad k = 1, 2, \dots, n-1

をできるだけ0に近づけるものを求める問題です。ベンチマークの目的関数は自己相関の二乗和

E(s)=∑k=1n−1ck(s)2,E(\boldsymbol{s}) = \sum_{k=1}^{n-1} c_k(\boldsymbol{s})^2,

であり、これを最小化します。LABSはNP-hardであり、古典・量子の両方のヒューリスティクスのストレステストとして長く使われてきました。

LABSインスタンスのロード

Labsは2つのモデルを公開しています。一つは"integer"(ckc_kを整数決定変数として導入し、それらをs\boldsymbol{s}と結びつける制約を加える形式)、もう一つは"quadratic_unconstrained"(積xixi+k+1x_i x_{i+k+1}を表す補助バイナリ変数zi,kz_{i,k}を2次のペナルティで導入したQUBO定式化)です。QAOAにはQUBO形式が自然に対応するため、本チュートリアルでは後者を使用します。

Dataset:           02_labs
Available models:  ['integer', 'quadratic_unconstrained']
Instance count:    99
First 5 instances: ['labs002', 'labs003', 'labs004', 'labs005', 'labs006']

ここではn=5n=5のインスタンスであるlabs005を選びます。このQUBO定式化では合計n+n(n−1)=25n + n(n-1) = 25個のバイナリ変数(5個の系列ビットxix_iとn(n−1)=20n(n-1) = 20個の補助zi,kz_{i,k})を使います。Instance.to_qubo()がペナルティ項を目的関数に畳み込み、未使用変数を取り除くと、15量子ビットの問題になります。ローカルでシミュレートできる程度に小さく、かつQAOAとして非自明なサイズです。

OMMX variables:    25
OMMX constraints:  0
Reference E(s):    2.0
Reference feasible: True

同梱の参照解から、n=5n=5における既知の最適値がE⋆=2E^\star = 2であることが分かります。QAOAとSCIPの結果はこの値と比較していきます。

アルゴリズム: QAOA

ここでは高レベルのQAOAConverterを使わず、QAOA for MaxCut: Building the Circuit from Scratchと同じレシピに従って@qkernelでQAOAワークフローを一から構築します。各ゲートの導出はそちらのチュートリアルに任せ、ここでは実装に焦点を当てます。

OMMXインスタンスからスピンモデルを作る

Instance.to_qubo()はペナルティ形式のommx.v1.InstanceをQUBOに変換します。続いてBinaryModelにラップし、QAOAのコストレイヤーが想定するスピン(-1/+1)領域に変換します。また、エネルギースケールを実行間で揃えるため、係数を正規化します。

QAOA qubits: 15

コストハミルトニアン

最適化に「ショット推定」ではなく「厳密な期待値」を用いるため、スピンモデルの係数からIsing型のコストハミルトニアンを直接構築します。線形項はZiZ_i、2次項はZiZjZ_i Z_jに対応します。

QAOAのqkernel

ansatzには、一様重ね合わせ、コストレイヤー、ミキサーレイヤーの3つの小さなqkernelを使います。これらを組み合わせて状態準備のためのqaoa_stateを作り、さらに2通りにラップします。1つはqmc.expvalを使う最適化時の期待値計算のためのqaoa_expval、もう1つはqmc.measureを使う最終ヒストグラム用のサンプリングのためのqaoa_samplingです。

トランスパイルと最適化

両方のqkernelをp=3p = 3でトランスパイルします。期待値用のexpval_executableは最適化のために使い、サンプリング用のsampling_executableは最後にショット分布を取るために使います。オプティマイザーにはコストハミルトニアンの厳密な期待値をAerのEstimatorV2プリミティブ経由で渡すので、BFGSの有限差分勾配はサンプリングノイズに乱されません。パラメータの軌跡を再現できるよう、NumPyにシードを設定します。

Optimized expectation value (normalized): 1.9622
Function evaluations:                     385
Wall time:                                17.41 s
<Figure size 800x400 with 1 Axes>

最終サンプリング

最適化されたパラメータでショット数を増やして再度サンプリングします。その後、元のommx.v1.Instanceに対してデコードすることで、返ってくるommx.v1.SampleSetから元のQUBO目的関数の値を直接読み取れます。このQUBO定式化では、補助変数zzが積xixi+k+1x_i x_{i+k+1}を正しく表現しているサンプルではペナルティが発生せず、目的関数値がLABSエネルギーE(s)=∑kck2E(\boldsymbol{s}) = \sum_k c_k^2と一致します。一方、z=xixi+k+1z = x_i x_{i+k+1}という暗黙の関係を破ったサンプルには、ペナルティが加算されます。

Shots:                4096
QAOA best objective:  2
Reference E*:         2

目的関数値の分布

QAOAは一つの解ではなくビット列の分布を返します。下のヒストグラムは、最適化済みパラメータで取得した各ショットのQUBO目的関数の値です。赤の点線は最適値E⋆E^\starを示します。その線上、またはすぐ右側にあるサンプルは、xxの値がLABS和を最小化し、zzの値が積を正しく符号化しています。線から大きく右に離れたサンプルは、zzの不整合に対するペナルティが加算されています。

<Figure size 800x400 with 1 Axes>

古典ベースライン: OMMXアダプタ経由のSCIP

SCIPは分枝限定法ベースのMILP/QUBOソルバーで、厳密解を求めることができます。同じommx.v1.Instanceをommx_pyscipopt_adapter.OMMXPySCIPOptAdapter.solveに渡すと、PySCIPOpt経由で問題がSCIPに渡され、元のインスタンスに対して評価されたommx.v1.Solutionが返ります。そのため、.objectiveはQAOA側と直接比較できます。

SCIP E(s):    2
SCIP feasible: True
Wall time:    0.425 s

結果の比較

SCIPは最適解を決定論的に返します。一方、QAOAはビット列の分布を返します。そこでQAOA側はベストショット(全サンプル中で最も低い目的関数値を達成したビット列)と、参照最適値に対するヒット率(その値を達成したショットの割合)を見てみます。

Solver                     E(s)     Time (s)
----------------------------------------------
Reference (bundled)           2            -
SCIP (classical)              2        0.425
QAOA (best shot)              2        17.41

QAOA hit rate on E* = 2: 4.6%  (4096 shots)

このベンチマークから読み取れることは大きく2点あります。

  1. 最適値の到達: SCIPとQAOAベストショットのどちらも参照最適値E⋆=2E^\star = 2に到達しており、QAOAはn=5n = 5かつp=3p = 3という軽い設定でも最適系列を見つけられることが分かります。

  2. 集中度: QAOAの価値はサンプリング確率を低エネルギーのビット列に集中させる点にあります。上記のヒット率とヒストグラム左端の集中が、その性質を定量化したものです。

なお、経過時間の値はあくまでも参考に留まります。SCIPの計測値はCPU上でのソルバーの実行時間であるのに対し、QAOA側の計測値は状態ベクトルシミュレータ上での古典・量子最適化ループ全体を含み、いずれも実行環境に依存します。このため、実際はより公正な評価方法が必要です。いずれにせよ、OMMX Quantum BenchmarksのようなデータセットとQamomileを組み合わせることで、量子アルゴリズムと古典ソルバーを様々な指標のもとで容易に比較することができます。

まとめ

本チュートリアルでは次のことを行いました。

  1. OMMX Quantum BenchmarksデータセットからLABSインスタンスをそのままommx.v1.Instanceとして読み込みました。

  2. Instance.to_qubo()でQUBOを取り出してBinaryModelにラップし、スピン領域に切り替えた上で、@qkernelを使った自作のQAOA ansatzをQiskitTranspiler + AerSimulatorを通じて実行しました。

  3. QAOAの出力(ベストショット、ヒット率、サンプリング分布)を、同じインスタンスに対するommx_pyscipopt_adapter.OMMXPySCIPOptAdapter.solveの結果、およびベンチマークに同梱された参照最適値と比較しました。

同じパターンは他のQOBLIBデータセット(Marketsplit、IndependentSet、Networkなど)にも適用できます。対応するデータセットクラスでロードし、Instance.to_qubo()でQUBOを取り出して、同じBinaryModel + QAOA ansatz + transpileのループを再利用します。大きなインスタンスがローカルシミュレータの能力を超えた場合は、同じexecutableをQamomileの他の量子SDK連携(QuriPartsTranspiler、CudaqTranspilerなど)や実機に切り替えられます。