量子最適化の結果に「最適解が得られた」とあっても、それが1回だけなのか、何度も得られたのかで受け取り方は変わります。たくさん試した末の1件と、少ない試行で繰り返し得られる良い答えは、同じ成績ではありません。
二つのグループに分ける組合せ問題「Max-Cut」を使うと、この違いを小さな例で確かめられます。QED-Cの共同研究による評価方法と公開実装を手掛かりに、最良値、平均、そこへ至る試行の量を分けて見ていきます。［1］
簡単にまとめると？
- Max-Cutは、点を二組に分け、組をまたぐ辺の数を大きくする問題です。最良の1件と標本全体の平均は、違う問いに答えます。
- 試行回数を増やすと、同じ分布でも良い答えを一度は引き当てやすくなります。最良値の比較には、試行数と時間の条件が必要です。
- 結果を読むときは、問題、成績の指標、試行予算をそろえます。量子回路だけでなく、パラメーターを更新する古典計算の時間も区別します。
Max-Cutの「良い答え」を、四つの点で考える
正方形の四つの頂点に点を置き、隣同士を4本の辺で結んだグラフを考えます。それぞれの点を赤か青に分け、両端の色が違う辺を数えます。この数がcut値です。色を交互に置けば4本すべてが組をまたぎ、この例の最大値は4になります。全点を同じ色にすれば0本です。
4点への二色の割当ては16通りあります。色を逆にしたものも別の割当てとして数えると、cut値が0の割当ては2通り、2は12通り、4は2通りです。どの割当ても同じ確率で選ぶなら、平均は2ですが、最良の答えとして4を得る可能性もあります。
これは説明のために全16通りを数えた独立の小例です。原著が評価に使う、各点につながる辺が3本のグラフとは異なり、量子回路の実行結果でもありません。原著のMax-Cutでも、組をまたぐ辺を多くするという目的は同じです。［1］
「最良」と「平均」で順位が入れ替わる
同じ正方形の問題から、次のような4回分の答えが得られたとします。AとBは指標の違いを見るために作った標本で、装置やアルゴリズムの測定値ではありません。
| 標本 | 4回のcut値 | 最良値 | 平均 | 平均÷最適値4 |
|---|---|---|---|---|
| A | 4、0、0、0 | 4 | 1 | 0.25 |
| B | 2、2、2、2 | 2 | 2 | 0.50 |
最良の答えだけならAが上です。一方、標本全体の平均ではBが上になります。一度でも良い候補を得て採用したいのか、繰り返し良い候補が出るかを見たいのかによって、必要な指標が変わるわけです。ただし、4回の標本だけで、次回以降もBの方が安定すると確定できるわけではありません。
原著は、標本の平均を最適値で割る近似比に加えて、最良の測定結果や、良い側の一部を重視する指標も比較しています。平均の近似比が1なら、その標本はすべて最適値ですが、最良値の比が1でも他の答えの質は分かりません。［1］
符号にも注意が要ります。確認した公開実装は、最小化する計算へ渡すため平均cut値にマイナスを付け、成績を記録するときに符号を戻して最適値で割っています。ここでは一貫して正のcut値で比べています。値が大きいほど良いのか、小さいほど良いのかを確かめるだけでも、異なる出力の取り違えを防げます。［2］
最良値は、試す回数にも左右される
先ほどの16通りを毎回独立に同じ確率で選ぶ方法では、1回で最適値4を得る確率は2÷16、つまり12.5%です。同じ選び方でも8回試せば、一度以上4を得る確率は約65.6%になります。最適値を一度も引かない確率を使い、1−(7/8)8で求められます。
選ぶ仕組みは改善していません。それでも、試す回数を増やすだけで「最適解を得られた」と報告しやすくなります。一方、この選び方の1回あたりの期待cut値は2のままです。この計算は一様で独立な試行の仮例であり、学習中の量子回路の出力確率を表すものではありません。
量子近似最適化アルゴリズム（QAOA）は、量子回路から得た標本を評価し、古典計算で回路のパラメーターを更新していきます。回路を何回測ったかを示すshotsだけでなく、更新を何回行い、初期値を変えて何回やり直したかも、結果を得るための予算に含まれます。最終回のshots数だけでは、探索全体でどれほど試したかは分かりません。［1］
同じ時間での質か、同じ質に届く時間か
原著が整理する比較の一つは、時間を決めたときに、どの程度の答えが得られるかです。もう一つは、目標とする答えの質へ届くまでに、どれだけの時間がかかるかです。前者は締切がある仕事に、後者は必要な品質を先に決められる仕事に対応します。［1］
その時間が量子処理だけなのか、古典計算も含むのか、準備などを含む全体の経過時間なのかで、比較の意味は変わります。回路の中だけが速くても、パラメーター更新に時間を使えば、候補を得るまでの総時間が同じように短くなるとは限りません。
結果の表を見るときは、まず同じ問題を比べているかを確かめます。次に、平均なのか最良値なのか、既知の最適値を分母にしているのかを読みます。最後に、shots、更新回数、やり直し回数と、時間に含めた範囲を見ます。大きな問題で最適値そのものが分からない場合、既知の最良値との比を「最適値との比」と呼ばない区別も必要です。
原著の結果は、こうした評価方法を具体化するための例であり、すべての装置や設定を尽くした性能順位ではありません。良い答えを1件得たという数字に、答えの分布と試行予算を添えることで、その結果が自分の用途に合うかを判断しやすくなります。［1］
参考資料
- Thomas Lubinskiほか「Optimization Applications as Quantum Performance Benchmarks」arXiv:2302.02278v2、2024年2月1日改訂。Max-Cutの定義、品質指標、時間との関係、結果の適用範囲。本文ではこの保存版を参照。
- SRI International / QED-C「QC-App-Oriented Benchmarks：Max-Cut公開実装」commit 21dfc331ce61a2170b06f88259aa19f901c021bc。compute_sample_meanと品質比の記録処理を参照。