IBM Quantum(ゲート型量子コンピュータ)をFixstars Amplifyから使ってみた

　これまでに、Fixstars Amplify SDKを利用して、いくつかの小さな組合せ最適化問題を解きました。これらは、全て、量子アニーリング型マシンを用いたものでしたが、先日、この SDKがゲート型量子コンピュータ（IBM Quantum）にも対応したとのニュースがありました。すなわち、これまでとほぼ同じインタフェース（Pythonプログラム）で、組合せ最適化問題をIBM Quantumで解ける！のですから、ビッグニュースです。まだまだ、課題はありますが、以下にそのミニ体験を記します。

■まず例題を準備する
　ちょっと前置きですが、ここで用いる例題を示します。図１はすでに報告した「最小頂点カバー問題」を日立CMOS Annealingマシンで解いた状況です。スマホアプリにしてしまったところが憎いですね。イジング模型を使います。図の上部にそのエネルギー関数があります。今回は、できるだけ問題を小さくするため、図右側のノード数５のケースを扱います。

　一方、図２は、これをQUBO模型に人手変換して、Fixstars Amplify AEで解いた様子です。数秒以内に、５個ある最適解が全て求まっています。これまでやってきた通りで、特に問題ありません。

■ゲート型量子コンピュータで組合せ最適化問題を解くとは
　上の例は、量子アニーリングマシンで解くためのものでした。今回改訂されたFixstars Amplify SDKでは、ほとんど従来のプログラム記述で（図２のような）、ゲート型量子コンピュータIBM Quantumに適用できるとのことです。これは素晴らしい！

　早速試してみました。確かにその通り、IBM Quantumが動き始めました。しかし、新しいものは何でもそうですが、一筋縄には行きません。第一に、IBM Quantumは物凄い人気らしく、無料枠で解放されている機種では、実行待ちが30分とか１時間、場合によっては数時間以上となり、なかなか実行されません。下図は、（遠慮気味に選択した）量子ビット少なめのマシンibm_quitoを使った例ですが、現在キューの７番目にあり、約20分後に実行開始の見込み、となっています。（IBM Quantumは量子ビット数の異なる20台ほどが稼働しており、そのうちの数台に無料枠が設定されている模様）

　第二に、ゲート型量子コンピュータで組合せ最適化問題を解くために、QAOAと呼ばれるアルゴリズムが使われます。Amplify SDKではこれをユーザが意識しなくてもよいようにしています。しかし、このQAOAでは、一定回数（上図のshotsの値、1024）だけ、ユーザプログラムに対応した量子回路を実行してその結果を観測しますが、まだ解は出ません。その観測を最大shots回だけ自動的に内部jobとして繰り返して最終的な解を求めるとのことです。その各job毎にまた、上記の待ちが発生してしまいます！ですから、おそらく、１日たっても最終解は得られないでしょう。

■それでも試したIBM Quantumマシン
　こんなに長大な待ち時間（有料ユーザになれば別かもしれないが）の中、何とか、求解の途中の断面を見ることはできました。図３にその様子を示します。この「最小頂点カバー問題」の最適解は５つあり、そのうちの一つの最適解（10011）に対するprobabilityがダントツに大きくなっています。これが最終解ではないのですが、段々にこうして最適解が求まって行くらしいことを実感できます。

■感想
　「初めてのゲート型量子コンピュータ」という感じでした。組合せ最適化問題を解く場合、現時点では、まだまだ、量子アニーリング型マシンを使う方が現実的だ、ということを感じました。しかし、ハードウェアメーカの研究開発がさらに進み、Fixstars Amplifyなどのミドルウェア、ライブラリも進歩し、エンドユーザも少しは量子コンピュータの仕組みを勉強してから使う、ということが重なれば、近々、驚くべき進展があるように思える。ともに頑張りましょう！

量子アニーリングにおける制約条件の強さの扱い（続）

　前回に引き続き、エネルギー関数と制約条件を合体させる場合に、制約条件に掛ける係数の影響を観察する。また、今回の例題では目的関数が２種類あり、それぞれをどの程度重視するかを決める係数についても見る。

■例題：シフト最適化
　以下に公開されているFixstars Amplifyのセミナー・トレーニング「シフト最適化」を利用させていただいた。
　https://amplify.fixstars.com/ja/news/seminar
　３つの生産ラインへ15名の従業員を５名づつ割り当てる。各従業員はそれぞれのラインに対するスキル値を持つ。全ラインのスキル値の合計をできるだけ大きくしたい。同時、各ラインのスキル値のばらつき（分散）を小さくしたい。そこで、目的関数と制約条件を図１のようにする。（より詳細は上記URLを参照されたい。）

　目的関数が２つあるので、それぞれをどの程度重視するかを決める係数γを設定する。また、前回と同様に、制約条件も２つあり、目的関数に対するそれらの制約条件の強さを示す係数δを設定する。

■制約条件の強さを表す係数δのアニーリングへの影響
　このmodel（イジング模型）を、係数δの値を変えて実行した結果は表１のようになった。係数δの値が、0.2〜10.0の広い範囲で、目的関数の一つである全ラインのスキル値合計を高くできている。（ただし、その値は係数γの値により異なる。）実際には、係数δに従業員のスキル値の最大値を掛けている。すなわち、大雑把に言って、制約条件に掛ける重みの係数は、従業員のスキル値の最大値付近（数分の１から数倍程度）が良いようである。

　一方、もう一つの目的関数である各ラインのスキル値の分散を小さくすることは、係数γの値の調整で可能であることが確認できた。すなわち、あくまで合計スキル値を最高にすることにこだわるのか（γ=0.6）、それとも、ライン毎のスキル値の分散を限りなく小さくすることに固執するのか（γ=0.4）を選択できる。

　今回の観察結果から、種々の問題における係数δの決め方の一般的な方法が得られたわけではない。しかし、このような観察を多数のイジング模型の解法で実施することは、経験的に良い値を設定することに繋がるだろう。

ポルトガル語版になった私のAndroidアプリ（ハミルトン閉路）

💌この小さな物語、ご覧いただければ嬉しいです。

　ブラジルのフロンテイラ・スー連邦大学（the Federal University of Fronteira Sul）のProf. Carlos Françaという教授からメールがあり、小生が以前開発した下記のAndroidアプリをポルトガル語版に変換して、学生らに提供したいとのお申し出をいただきました。もちろん、快諾です。

●Enjoy finding out Hamiltonian Cycles

https://sparse-dense.blogspot.com/2021/02/enjoy-finding-out-hamiltonian-cycles.html

　Carlos França教授はコンピュータサイエンス教育において、スマホアプリの活用が極めて有効との信念を持っており、これまでに、数学系/情報科学系のAndroidアプリを70件ほど開発 or 収集して学生らに供しています。そのライブラリに、今回、小生のこのハミルトン閉路を追加したいとのことでした。このアプリは、MIT App Inventor of the Monthを受賞したニュースから知ったようです。

　ポルトガル語版になった小生のアプリはこちら：
http://www.profcarlosfranca.com.br

　小生の英語版のアプリのGUIとドキュメント（説明文）を完璧にポルトガル語に変換されています。そして、ポルトガル語による約15分の解説（内容説明と操作方法）を入れたビデオをYoutubeに公開していただきました。ブラジルと日本との思わぬ教育研究交流ともなりました。感激です！

　小生は、MIT App Inventorの有用性を当初から確信して、これまで１０年以上続けて取り組んできました。それが、遠く離れた対蹠地（地球のほぼ裏側）のブラジルの大学で思わず小さな花を一輪咲かせた。そんな思いに浸っています。
　でも、なんだか、ちょっと感傷的すぎるんじゃないのか！

量子アニーリングにおける制約条件の強さの扱い

　これまで、量子アニーリングを利用して種々の組合せ最適化問題を学んできた。一般にエネルギー関数（目的関数、あるいはコスト関数とも呼ぶ）と制約条件をイジングマシンに与えて解く。この時、エネルギー関数と制約条件を単に合体させるのではなく、制約条件にある係数をかけてその強さを調整することが重要であることが分かった。だが、適度な係数値を決める方法は自明ではない。ここでは、「最適生産計画作成」を例に、その係数の値が最適化にどのように影響するかを観察する。

■例題：生産計画最適化
　以下に公開されているFixstars Amplifyのセミナー・トレーニング「生産計画最適化」を利用させていただいた。
　https://amplify.fixstars.com/ja/news/seminar
　3台の製造装置で3品種、合計45個を生産する。各品種毎の生産台数、生産時間、及び、生産する品種を切り替えるための段取り時間が定められている。全ての製品の生産にかかる総所要時間が少なく、総段取り時間も少ない、最適な生産計画を作成する。（詳細仕様は上記URLを参照願いたい。）

　制約１：各装置は同時には１品種のみを製造
　制約２：各品種の生産数は規定通りにする
　目的１：製造総所要時間（これを最小化する）
　目的２：総段取り時間（これを最小化する）

イジングマシンに与えるmodelを以下のようにする。ここで、係数kは制約条件の強さを意味する：
　model ← （目的1と目的2の併合）と（ k* (制約1と制約2の併合)）を合体

■制約条件の強さを表す係数kのアニーリングへの影響
　このmodelを、係数kの値を変えて実行した結果、表１のように目的関数値（=製造総所要時間と総段取り時間の和）を得た。利用したイジングマシン（Fixstars Amplify AEとHiroshima Univ. /NTT DATA ABS）によって多少異なるが、目的関数の値が最小となる、係数kの値の最小値は20〜50位であることが分かった。また、係数kはかなり大きな値で良いらしい。上記セミナー資料では（算出法の明記は無いが） k=35となっていた。さすがである。

　もちろん、ここで得たkの値はこの問題に特有なものだろう。しかし、上記の表からkの値の広がり具合が何となく掴める。この漠然とした感触が別の新たな問題に取り組む時に拠り所になりそうに思うのである。

■制約条件の強さを表す係数kの値の見積もり
　係数kの適切な値は、コスト関数に依存すると考えられる。これらの見積もり方法はいくつか提案されているが、ヒューリスティックか、機械学習によるもののようだ。以下の２つの説明は、上記の実行結果からも納得が行くと感じた。

説明１：
以下のオンラインデモ&チュートリアル「巡回セールスマン問題」の説明：
　https://amplify.fixstars.com/ja/demo
「ここで制約条件の強さに注意を要する必要があります。適切な制約条件の強さはコスト関数に依存し、十分に大きな値にする必要があるからです。しかし一方で、制約の強さを可能な限り小さくすることで、イジングマシンが出力する結果が改善する傾向にもあります。」

説明２：
インタフェース誌 2022年6月号の記事pp.129-131にある説明の要点：
実行可能解を制約条件を全て満たす解、そして実行不可能解を制約条件が満たされていない解と定義する。

• 係数kが小さい場合、実行不可能解のエネルギーが小さくなり、そこへ到達する可能性が生ずる。
• 係数kが十分大きい場合、実行不可能解のエネルギーが大きくなるため、よりコスト関数値の小さな実行可能解へ移動する傾向となる。
• 係数kが大きすぎる場合、実行不可能解のエネルギーがあまりにも大きいため、ある実行可能解に達しても、さらに別の実行可能解への移動がしにくくなり、結果として最適解に到達しにくい。

（何となく補足）
　最近、「量子コンピュータによるAI」というのを見かけることがあります。ちょっと違和感ありますね。従来不可能だった何を解きたいのか、何に応用したいのか、それを示唆する簡潔な表現が欲しいですね。そうでないと、「量子コンピュータ」という言葉に流された空疎なアナウンスにしか聞こえない。小生の場合、ゲートウェイ型であれアニーリング型であれ、量子コンピューティングでどんな問題が解けるのかを、基本的な例題にひとつづつ当たって丹念に調べるという段階にあります。今回の記事もその一環のつもり。