量子アニーリングでは「数独」も「会議スケジューリング」も同じ

　新しい手法にはメリットとデメリットがある。しかし、量子アニーリングを検討し始めた現時点では、まず、メリットを追求するのが良い。その実績を積めば、次第に問題点にも気づき、改善提案もできるかもしれない。

（以下の３つの例題では、Fixstars AmplifyのWebページにあるデモプログラムを利用、または参考にさせていただいた。そのURLは、図４の中に示した。本記事の内容は、当方が独自に調査・試行した結果に基づいている。）

■量子アニーリングを用いた解法とは
　量子アニーリングを用いた解法の最大のメリットは、「問題毎に固有の解法アルゴリズムを考えなくて良い」ことだろう。それを明確するため、ここでは「数独」と簡単な「会議スケジューリング」、および「グラフ彩色問題」の３つを例に、これらがほとんど同じ問題として扱えることを述べたい。

　パズル数独は、よく知られたいくつかの制約条件のもとで、9 x 9 のマスに入れる数字を決める問題である。また、ここで扱う会議スケジューリングは、いくつかの制約条件のもとで（その仕様詳細はここに示したが）午前中に６つの会議を３つの会議室で行うために、各会議の開始時間を決める問題となる。３番目は、４色定理に基づくグラフ頂点彩色問題（典型的には地図の色塗り分け）である。

　量子アニーリングを行うためには、問題の仕様を、目的関数 and/or 制約条件として表現すれば良いのである。問題固有の解法アルゴリズム（解法手順）は与える必要がない。これは、現代の数理計画法からの影響を受けているとも言えよう。今回の例題はいずれも、目的関数は与えずに、制約条件だけを設定すればよいケースとなっている。ただし（この言葉がよく出るのだが）、実際にはSDKが、制約条件を反映した目的関数（エネルギー関数）を生成していると言える。イジングによる処理は本質的にそういうものだ。

　実際、図１に示した通り、これら３つの問題の構造はほとんど同じに見える。ただし、(a)と(b)では３次元QUBO配列、(c)は実質２次元QUBO配列となるが、その違いは問題ではなく、うまく行きそうだ。

■量子アニーリングによる解法の実行
　制約条件設定の詳細は略すが、３つの問題とも、Fixstars Amplify SDKを利用した短いPythonプログラムを作成することになる。その主要部は、制約条件を設定するために、QUBO変数（またはイジング変数）の一次または二次多項式による等式または不等式を生成するものだ。それを与えて量子アニーリングを実行し、その結果を得ることができた。図２〜図４に示す通り、数独、会議スケジューリング、グラフ頂点彩色とも極く短時間で正解が得られた。

■量子アニーリングのインパクト

　この結果を眺めていると、量子アニーリングが与えるインパクトは、段々に広く認知されると感じるのである。つまり、従来のプログラミング技術をあまり習得していない、いわゆる文系型の人々にも、組合せ最適化問題を解くことができる手段を与えることに繋がると思われる。問題を正確に表現するための制約条件の設定は、それほど容易ではなかろうが、問題毎の解法アルゴリズムを設計するのに比較すれば、格段に敷居は下げられる。

　一方、個々の問題については、従来コンピュータ上で動く高性能な解法を考案することに生きがいを感じる人もいるだろう。小生も実はその一人であった。人間による洗練されたアルゴリズムは、このような量子アニーリングによる「一般的解法」よりもはるかに（必要な演算回数という尺度での）性能が高い場合が多いだろう。

　しかし、量子アニーリングの利用は、（人間の貴重な時間を考えた場合の）実務における効率化や、必ずしもIT専門家に頼らなくても良いことを示唆する。もちろん、（この期待も大きいのだが）場合によっては、処理時間の観点からも、人間のアルゴリズムをはるかに凌駕する高性能を発揮するだろう。その期待が高まるのである。