Jij Tech Blog

Jij inc.の開発日記です

「ナップサック問題が量子アニーリング(QA)で解けない」は本当か?

ナップサック問題

概要

ここにいくつかの物があります。

Objects 価値(100万円) 重さ(kg)
1 13 11
2 8 15
3 25 19
4 11 12
5 13 21

そしてナップサックは最大で26kgまで荷物を運ぶことができるとします。このとき、ナップサックに入れられる荷物の組み合わせの中で最も価値が大きくするにはどのように入れる物を選べばよいでしょうか、というのがナップサック問題です。

定式化

ナップサックで運ぶことができる重さを W, i番目の物の価値と重さをそれぞれ v_i, w_iとします。

バイナリ変数として、 i番目のものをナップサックに入れるとき x_i = 1、入れないとき x_i = 0とします。

さらに以下のような2進数を表現するような補助バイナリ変数 y_iを導入します。

 \displaystyle{
Y = \sum_{i=0}^{\lfloor \log_2(W-1) \rfloor} 2^i y_i
}

原論文ではLucas, 2013, "Ising formulations of many NP problems"の定式化を用いています。しかし、Lucasの論文の定式化はスピン変数の数が多くなり、最適化が困難です。Lucas論文の定式化(One-hot encoding)を用いると、制約の数も増えます。これは一方を満たすと一方を満たさなくなるようなスピン状態を生みやすくなるため、制約が冗長です。我々はこの定式化が原因でナップサック問題がQAで解けないのではないかと考え、より効率の良いLog encodingによる数値実験を行いました。

制約: ナップサックで運ぶことができる重さ以上の物を入れてはならない

問題の定義から、ナップサックで運べない重さの物を詰め込むことはできません。よってそれを数理モデルとして考えると

 \displaystyle{
W \geq \sum_{i=0}^{N-1} w_i x_i \tag{1}
}

ここで右辺を \mathcal{W}と置きましょう。そして以下の等式が成り立つように補助変数を用います。

 \displaystyle{
W = \mathcal{W} + Y
}

 Yはその定義から必ず0以上であるため、この等式を満たせば(1)式が満たされます。よってこの式を軸とした制約を考えると

 \displaystyle{
\left( W - \sum_{i=0}^{N-1} w_i x_i - \sum_{i=0}^{\lfloor \log_2(W-1) \rfloor} 2^i y_i\right)^2 \tag{2}
}

となります。より詳しくはOpenJijチュートリアル8章 Solving Knapsack Problem with PyQUBOをご覧ください。

目的関数: ナップサックに入れる物の価値を最大にする

最適化問題はある制約を満たしながら目的関数が最小となる解を探す問題です。よってナップサックに入れる物の価値の合計 \sum_{i=0}^{N-1} v_i x_iを最大にするには

 \displaystyle{
{\rm obj} = - \sum_{i=0}^{N-1} v_i x_i
}

とすればよいことがわかります。

全ハミルトニアン

以上より、求めたい問題のハミルトニアンは、未定乗数 A, Bを用いて

 \displaystyle{
H = -B \sum_{i=0}^{N-1} v_i x_i + A \left( W - \sum_{i=0}^{N-1} w_i x_i - \sum_{i=0}^{\lfloor \log_2(W-1) \rfloor} 2^i y_i\right)^2 \tag{3}
}

となります。

未定乗数の決定

Lucasの論文と同様に、(3)式の制約項と目的関数の大きさ比較からA, Bを決定します。
1つの変数が変化したときに、目的関数部分の取りうる変化分の最大値は B \max(v_i)です。そして制約項部分の取りうる変化分の最小値は Aです。よって

 \displaystyle{
A > B \max(v_i)
}

を満たすようにA, Bを決定すれば、目的関数部分の変化よりも制約項部分の変化の方が大きくなります。これにより制約を満たす最低エネルギーの解を見つけることができます。実際には A = \max(v_i) + 1のようにして計算を行いました。

計算手法

量子アニーリング

量子アニーリングには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

インスタンス生成には論文で引用されているPisinger, D. "David Pisinger's optimization codes"を用いました。

さらに最適解の確認にはこのリンクにあるPythonスクリプトを用いました。

計算結果

ハミング距離

計算結果を比較するために、この論文ではハミング距離

 \displaystyle{
d_H ({\bf a}, {\bf b})=\frac{\sum_i^{バイナリ変数の総数} |a_i -b_i|}{(バイナリ変数の総数)}
}

を導入しています。 {\bf a}, {\bf b}は比較したい解のバイナリ変数列です。以下、全ての基準を最適解とし、最適解からのハミング距離を算出しています。

各手法の最悪解と最良解

以下の4つの図は各インスタンスにおいてSimulated Annealing(SA), Simulated Quantum Annealing(SQA)でTrotter数を4, SQAでTrotter数を8, Quantum Annealing(QA)を用いて計算繰り返し回数(num_reads)を1000としたときの、最悪解・最良解と最適解とのハミング距離です。0に近いほど最適解に近いことを意味します。

The best and worst solution for each method in Instance A
Instance Aでの各手法ごとの最良解・最悪解
Same figure as above, but in Instance B
Instance Bでの各手法ごとの最良解・最悪解
Same figure as above, but in Instance C
Instance Cでの各手法ごとの最良解・最悪解
Same figure as above, but in Instance D
Instance Dでの各手法ごとの最良解・最悪解

この図から、SAとSQAでは全てのInstanceで、QAではInstance A, B, Cで最適解を導くことに成功しています。元論文では「全てのインスタンスにおいて、SA・QAの両手法とも最適解を導くことに失敗した」とありましたが、それとは異なる結果を得ました

各手法の比較をしてみましょう。各インスタンスにおいて、QAでの最悪解ハミング距離はSAでのそれに比べて大きくなっています。またInstance DではQAでの最良解ハミング距離はSAでのそれに到達できていません。このことから、QAはSAに比べて良い解を導けていないことがわかります。

平均値と標準誤差

Comparison of humming distance for each method
各手法のハミング距離比較

上図は各インスタンスで、その手法を用いたときのハミング距離計算結果の平均値を表示しています。エラーバーは標準誤差を表しています。この図からも、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"としたのは、定式化の影響が大きかったからではないかというのが本記事の結論です。

文責

中村翔、株式会社 Jij
Sho K. NAKAMURA, Jij Inc.
憂いの篩 -Pensieve-

※ 疑問点や間違いなどございましたら、お気軽にブログ上でご質問ください。