「ナップサック問題が量子アニーリング(QA)で解けない」は本当か？
Pusey-Nazaro & Date, 2020, "Adiabatic Quantum Optimization Fails to Solve the Knapsack Problem"
を読み、実際にその内容を検証・考察したものです。
ナップサック問題 概要定式化未定乗数の決定計算手法量子アニーリング古典解法インスタンスと最適解の確認計算結果ハミング距離各手法の最悪解と最良解平均値と標準誤差考察ハミング距離による比較は最適な方法か?QAのハードウェア依存性SQAはQAの良い近似になっているか?結言参考文献
ナップサック問題
概要
ここにいくつかの物があります。
| Objects | 価値 (百万円) | 重さ (kg) |
| 1 | 13 | 11 |
| 2 | 8 | 15 |
| 3 | 25 | 19 |
| 4 | 11 | 12 |
| 5 | 13 | 21 |
そしてナップサックは最大で26kgまで荷物を運ぶことができるとします。このとき、ナップサックに入れられる荷物の組み合わせの中で最も価値が大きくするにはどのように入れる物を選べばよいでしょうか、というのがナップサック問題です。
定式化
ナップサックで運ぶことができる重さを 番目の物の価値と重さをそれぞれ とします。
バイナリ変数として、ii番目のものをナップサックに入れるとき 、入れないとき とします。
さらに以下のような2進数を表現するような補助バイナリ変数 を導入します。
原論文ではLucas, 2013, "Ising formulations of many NP problems"の定式化を用いています。しかし、Lucasの論文の定式化はスピン変数の数が多くなり、最適化が困難です。Lucas論文の定式化(One-hot encoding)を用いると、制約の数も増えます。これは一方を満たすと一方を満たさなくなるようなスピン状態を生みやすくなるため、制約が冗長です。我々はこの定式化が原因でナップサック問題がQAで解けないのではないかと考え、より効率の良いLog encodingによる数値実験を行いました。
制約: ナップサックで運ぶことができる重さ以上の物を入れてはならない
問題の定義から、ナップサックで運べない重さの物を詰め込むことはできません。よってそれを数理モデルとして考えると
ここで右辺を と置きましょう。そして以下の等式が成り立つように補助変数を用います。
はその定義から必ず0以上であるため、この等式を満たせば(1)式が満たされます。よってこの式を軸とした制約を考えると
目的関数: ナップサックに入れる物の価値を最大にする
最適化問題はある制約を満たしながら目的関数が最小となる解を探す問題です。よってナップサックに入れる物の価値の合計 を最大にするには
とすればよいことがわかります。
全ハミルトニアン
以上より、求めたい問題のハミルトニアンは、未定乗数 を用いて
となります。
未定乗数の決定
Lucasの論文と同様に、(3)式の制約項と目的関数の大きさ比較からA, Bを決定します。
1つの変数が変化したときに、目的関数部分の取りうる変化分の最大値は です。そして制約項部分の取りうる変化分の最小値は です。よって
を満たすようにA, Bを決定すれば、目的関数部分の変化よりも制約項部分の変化の方が大きくなります。これにより制約を満たす最低エネルギーの解を見つけることができます。実際には のようにして計算を行いました。
計算手法
量子アニーリング
量子アニーリングにはD-Wave 2000Q_6を用います。
古典解法
比較のために用いた古典ソルバーにはOpenJijのSimulated AnnealingとSimulated Quantum Annealingを用います。
インスタンスと最適解の確認
インスタンスは以下の4種類を用います。
| Instance | 物の数 | ナップサックの容量 | バイナリ変数の総数 |
| A | 4 | 11 | 8 |
| B | 4 | 20 | 9 |
| C | 5 | 26 | 11 |
| D | 7 | 50 | 13 |
計算結果
ハミング距離
計算結果を比較するために、この論文ではハミング距離
を導入しています。 は比較したい解のバイナリ変数列です。以下、全ての基準を最適解とし、最適解からのハミング距離を算出しています。
各手法の最悪解と最良解
以下の4つの図は各インスタンスにおいてSimulated Annealing(SA), Simulated Quantum Annealing(SQA)でTrotter数を4, SQAでTrotter数を8, Quantum Annealing(QA)を用いて計算繰り返し回数(num_reads)を1000としたときの、最悪解・最良解と最適解とのハミング距離です。0に近いほど最適解に近いことを意味します。
この図から、SAとSQAでは全てのInstanceで、QAではInstance A, B, Cで最適解を導くことに成功しています。元論文では「全てのインスタンスにおいて、SA・QAの両手法とも最適解を導くことに失敗した」とありましたが、それとは異なる結果を得ました。
各手法の比較をしてみましょう。各インスタンスにおいて、QAでの最悪解ハミング距離はSAでのそれに比べて大きくなっています。またInstance DではQAでの最良解ハミング距離はSAでのそれに到達できていません。このことから、QAはSAに比べて良い解を導けていないことがわかります。
平均値と標準誤差
上図は各インスタンスで、その手法を用いたときのハミング距離計算結果の平均値を表示しています。エラーバーは標準誤差を表しています。この図からも、QAがSAよりも劣っているという結果を得ました。
SQAの場合、Trotter数だけレプリカを用意して計算を行っています。そのためSAと比較するためにはSAにおいても同じだけのSAを用意し、その中からベストな解を選ぶことでフェアな比較と言えます。しかし、そのようにSAを並列実行することと、SQAをTrotter数だけ並列実行することでは、後者はレプリカ間に量子項に由来する相互作用が入っているためより良い解が見つけやすいことが期待されています。SQA(Trotter=8)のハミング距離平均値が低く抑えられているのはこのような理由と考えられます。
考察
ハミング距離による比較は最適な方法か?
ハミング距離によるSA, SQA, QAの比較は本当に正しいのでしょうか。それを考えてみましょう。今、仮に以下のような解法1, 2という2つで数値実験を行ったとします。
5回の繰り返しのうち、解法1では最適解は1回も求まりませんでしたが、ハミング距離が5回とも0.3であったとしましょう。するとこの解法1による平均ハミング距離は0.3になります。
しかし解法2では5回の繰り返しのうちに最適解が1回求まりました(ハミング距離が0)。しかしその他の4回の試行ではハミング距離が0.5だったとします。するとこの解法2による平均ハミング距離は0.4となります。
解法1, 2はハミング距離の平均値だけを見ると解法1の方が優れている、という結論になります。しかし、5回の繰り返しのうちに最適解が求まっているのは解法2なので、TTS(Time To Solution)などの別指標では解法2の方が優れているという結果になります。
このような単純な例からも分かる通り、ベンチマークを取るにはそれにふさわしい指標を決める必要があります。最悪解・最良解におけるハミング距離、そして平均値による比較も行いましたが、これらからQAはSA・SQAに比べて劣っていると断言できるかどうかはまだ議論の余地がありそうです。ここで行った比較は全ての計算時間を揃えていません。単に解の精度を見るだけでは、メタヒューリスティクスの比較としては不十分と言えるでしょう。
QAのハードウェア依存性
現在、QAはD-Waveマシンを用いて実行しています。しかし、このハードウェアはコヒーレンス時間が短いことやノイズの存在、そして埋め込みの問題があります。これらの影響でQAが理論的に理想的なアニーリングになっていません。QAの実行結果がハードウェアに依存していることが、SA・SQAに劣る要因になります。
SQAはQAの良い近似になっているか?
SQAはその名前の通り、QAの良い近似として知られています。しかし、今回の数値実験結果ではSQAが良い解を導けているのに対して、QAは悪くなっています。この原因は2つの手法がベースとしている理論背景に関連しています。SQAは統計力学的な手法を用いているのに対して、実際のQAは量子ダイナミクスに基づく手法です。よってSQAがQAの良い近似になるかどうかは、特に今回のような小さいインスタンスでは非自明です。
結言
元論文で"Adiabatic Quantum Optimization Fails to Solve the Knapsack Problem"としたのは、定式化の影響が大きかったからではないか
というのが本記事の結論です。