量子アニーリング

とても勉強になるサイトがあります。なるほど、整数計画もSATを介してイジングモデルに変換できるのですね。　組合せ最適化に対する新しいアプローチです。

今までの組合せ最適化のアプローチは、大きく分けて次の３つです。

■MIP
　Simplex・内点法をベースとした線形ソルバをベースにCuttingPlaneで整数化を図る古典的なアプローチです。Cplex/Gurobi等、商用ソルバが圧倒的に強い分野です。

■SAT
　SATソルバーベースのアプローチです。

■Simulated　Annealing
  に代表されるメタヒューリスティクス的アプローチです。

これに量子アニーリングが加わることになるのでしょう。ハードウェアの並列性を生かした解法
と認識しています。

全ての問題を一つのソルバが凌駕するということには、恐らくならないと思います。例えば、ブランク数独は、SATの独壇場で100x100でも難なく解けますが、MIPやメタヒューリスティクスでは、そうではないでしょう。1000人のナーススケジューリングという問題がもしあったとしたら、私ならMIPやSATは使わず、Simulated　Annealingを採るでしょう。（というよりも、まともに解けない規模です。）　ということで、問題分野・規模で、採るべきソルバーは変わってくると思います。