今回は、前回（１）でも述べた量子アニーリング型コンピュータ（別名、イジングマシン）の実機を使い、少し現実味のある例題に取り組みます。全く新しいタイプのコンピュータの利用ですから、これから大学で卒研を始める人にも、参考になれば嬉しいです。私も卒研生にかえったつもりで書いていますので、フルスペックの解答は示していません！？（単なる言い訳か。）
[*]その後の検討の結果、以下の論理には一部欠陥があることに気づきました。後日、改訂版を書きますが、本記事はそのまま（検討過程の経緯として）残します。→ 改訂版はこちらです。
■課題：卒研発表会プログラムの作成
図１は、ある大学の情報工学科の卒研発表会の実データである。図1(a)のように、19の研究室に４名〜10名の発表者がいる。５つの教室で並列に行われ、一人当たりの持ち時間は11分（=１スロット）、研究室入れ替えに１スロット、昼休みは５スロット分とする。全体をできるだけ短い時間で終わらせたい。
これは単なる箱詰め問題ではなく、さらに、図１(b)のような研究室間の依存性もある。すなわち、教員は自分の研究室の発表にはもちろん参加するが、指導（評価）する他の研究室の発表も聞く必要があるからだ。
この課題のフルスペックの解答は、従来の数理計画法でも可能だろうが、ここではそれは置いておき、新しい量子アニーリング型コンピュータを如何に利用するのかに焦点を当てる。Fixstars Amplify で提供されている、D-Wave（量子回路）、日立CMOSアニーリングマシン、Fixstars AEなどを選択して使うことができる。以下で段階的に検討する。
■レベル１：練習（全体終了時間を短くする配置）
できるだけ全体の終了時間を短くする配置は、箱詰め問題のようである。これを量子アニーリングにかけるためのイジングモデルは以下のようになる。
（１）エネルギー関数A（目的関数）：
各教室で9:30に一斉に開始する。決定された割り当てに対して、各教室の終了時間のバラツキを示す関数Aを作る。この値を最小化するのが目標だ。前回述べたFixstars AmplifyのSDKを利用すれば、イジング変数（またはQUBO変数）の多項式として、そのような関数を（シンボリックに）イジングモデルへ与えることができる。
（２）制約関数X：
当然ながら、各研究室がいずれかの教室に必ず１回だけ配置されること。このような制約は、各研究室ごとに、全ての教室に対応するQUBO変数の総和がちょうど１となる関数をシンボリックに作成すればよい。
■レベル２：昼休みを入れた配置とする
レベル１では、昼休みがないので現実的でない。これを入れた配置にするため、午前と午後に分けて考える。以下では、午前の部について述べる。例えば、どの教室も12:10頃には一斉に終了するようにする。
（１）エネルギー関数A（目的関数）：
各教室の終了のバラツキをできるだけ小さくするという意味で、レベル１の場合と同じ。
（２）制約関数X'：
これは、レベル１の制約関数Xを緩和したもの。すなわち、各研究室がいずれかの教室に、0回（配置されない）または１回配置されること。
（２）制約関数Y：
どの教室の終了時間も12:10をこえないこと。すなわち、スケジュール長が一定のスロット数以下であることを示す。これもエネルギー関数の場合と同様に、QUBO変数の多項式からなる不等式をシンボリックに作成して与えることができる。
■レベル３：手作業での配置との協調
これまでは自動配置だったが、例えば、研究室L13には特殊事情があり、午前中に教室0へ手作業で配置したい、という場合がある。残りの配置は上記の通り自動で行う。実はこれは簡単にできる。QUBO変数を定数にすることも可能だからである。その実現例を図４に示す。
■レベル４：研究室間の依存を考慮した配置
まず、確認しておきたいことがある。それは、上記のようなアニーリングの結果は、「研究室をどの教室へ配置するか」だけを決めるのであって、教室内での順序は決まらないことだ。図１〜図４での配置順序は一例に過ぎない。
図１(b)に示したような研究室間に依存性がある場合は、ちょっと厄介だ。最初からこのような依存関係を含む自動配置を求めるのではなく、レベル１での様々な配置結果を参考に、手動で依存関係を満たすように再配置するという選択肢もあるだろう。
しかし、どうしても自動配置が必要ならば、依存関係を十分条件として満たすような、QUBO変数の多項式や不等式による制約の生成も可能である。だが、それは（スケジュールが決まる前に設計するので）過剰な制約となり、結果としてスケジュール長を伸ばす恐れがある。これに関しては、次回以降に再度検討したい。
■従来のプログラミングとの比較
量子アニーリング利用の最大の特徴は、解きたい問題毎の解法手順を与える必要がないことだ。これは、ディープラーニングに似たところでもある。必要なのは、問題を表現するエネルギー関数と制約関数の生成だけである。（"だけ"と言うな！そこが難しい。）Fixstars Amplifyを利用する場合は、それを通常のPython関数として与えるのではなく、数式としてシンボリックにイジングモデルへ渡すことになる。このあたりが、従来のプログラミングと異なる。
しかしながら、従来型のプログラミングの必要性は、実はさらに高まってきたと言えるのだ。なぜなら、入力データの整形やFixstars Amplify SDK利用にはPythonが欠かせない。さらに、アニーリングの結果は、特殊なオブジェクトで返ってくるので、それをPython型に変換したり、分かりやすいプロット図やグラフ表示にもPhthon機能が不可欠なのである。
■情報源：まだ少ないが増えてきた
このためのプログラミング関連情報源はまだ多くはないと思う。そんな中で、特筆すべきものが出た。CQ出版「インタフェース」2022年６月号である。「Pythonで体験！量子コンピュータ：ゲート方式&アニーリング方式」という、全115ページに渡る大特集記事が掲載されている。量子コンピュータの基本原理や、上記で述べたFixstars Amplify SDK利用による量子アニーリングアプリの詳細解説まで載っている！我々にも、一気に量子コンピュータ時代がやってきた感がある！
0 件のコメント:
コメントを投稿