量子アニーリングによる渋滞解消のための信号制御

【要旨】数日前に、日立製作所のCMOSアニーリングマシン利用に関するwebサイト[1]に、「渋滞解消のための信号制御最適化」という解説が公開されました。テスト用のPythonソースコードも提供されていますので、早速試してみました。

●渋滞解消のための信号制御最適化

　この課題は、古くから取り組まれています。車の自動運転技術も注目されていますが、今のところ、交通渋滞解消を目指すものではないでしょう。しかし、交通渋滞解消の技術は注目されるべきものです。それによる現代社会での経済的、社会的効果は計り知れません。

　従来は、車の台数や速度、車間距離、青信号の点灯時間と切り替えタイミング、交差点での進行方向等々を時間変化で捉えて微分方程式モデルを作り解くこともあるようです。しかし、今回の手法は、そういう要素を明示的に使わずに、「交差点をつなぐ道の上にいる車の量」を「青信号の点灯」と関連付けた画期的なモデルだと思われます。参考文献[2]の豊田中央研究所と東大による論文に基づいているとのことです。

●量子アニーリングによる信号制御最適化

　詳細は参考文献[1] [2]をご覧いただきたい。非常に丁寧な解説が[1]にあります。「各交差点で待機している垂直方向や水平方向の車の台数を信号制御によって均一化する」という観点から、イジングモデルを組み立てる考え方と具体的な手順が説明されています。もちろん、交差点に入る車の直進、右折、左折の割合や時間変化も考慮されています。そして最終的に、各交差点を量子のスピンに対応させて、スピン間の相互作用係数と外部磁場係数を使ったエネルギー関数（コスト関数）を導いています。

　私が気にしていたのは、いくつかの制約条件をどのようにコスト関数に組み入れるのか、でしたが、例えば、隣り合う信号が相反する場合にペナルティを与えることなどをうまく取り入れています。

●実際に動かして試してみよう

　原理的なことを一通り理解した上で、日立のCMOSアニーリングマシンを動かして、動きを確かめます。Pythonソースコードが公開されていますので、誰でもできます。ただし、日立から、無料のAnnealing Cloud Web用のAPIキーを取得する必要があります。

　動かしてみると、なかなか素晴らしい！解説も分かりやすいのでとても勉強になります。各信号は量子スピンに対応するので、アニーリングの結果として、エネルギー関数を最小化するスピンの向き（北極、南極）のセットが返ってきます。すなわち、その時点では、北極ならその信号器の水平方向を青色に、南極なら垂直方向を青色にするのが最適だ、ということです。

　ただ、最適化の結果を見やすくしたい。とうことで、信号の青点灯と交差点での渋滞の度合いを可視化するアニメーションアプリを作成しました。図１にそれを示します。

●感想

　色々なことが思い浮かぶのですが、この結果をみると、初期状態でかなり渋滞していても、この最適化で、青信号の点灯方向が変わり、急速に渋滞が解消に向かうことがわかります。その後は、信号の切り替えは穏やかになり、渋滞は徐々に減少します。もちろん、初期状態での車の量や、交差点での直進、右折、左折の割合などで状況は変わるでしよう。また、どこかのスピンが故障して、ある確率で方向が反転してしまう場合に、最適性はどのように失われるのでしょうか。（パリティチェックみたいな機構が付いているのかもしれませんが。）
　今回のこの解説は、今後、種々のアイディアを独自に試す場合の非常に重要な拠り所になりそうです。

参考文献

[1] CMOS Annealing Cloud Web News

https://annealing-cloud.com/ja/index.html

[2] Daisuke Inoue, Akihisa Okada, Tadayoshi Matsumori, Kazuyuki Aihara, Hiroaki Yoshida: "Traffic Signal Optimization on a Square Lattice with Quantum Annealing"

[Submitted on 17 Mar 2020 (v1), last revised 1 Feb 2021 (this version, v2)]

https://arxiv.org/abs/2003.07527

量子コンピューティング国際会議Q2B22 Tokyo参加レポート

　この会議名Q2Bから連想されるとおり、開催趣旨は、"Toward the practical use of quantum computing".　以下のような講演タイトルは、私を参加へ駆り立てるのに十分でした。（下記を含め合計55件の講演がありました。）

・コヒーレントな量子アニーリング：西森秀稔（東工大特任教授）

・量子コンピュータが導く最適な配送ルート：井手貴範（アイシン）

・量子アニーリングで何ができるのか、自ら検証すべき理由：香月諒大（NTTデータ）

・日立CMOSアニーリングの概要と開発状況：山岡雅直（日立）

・Quantum in the Enterprise：Hossein Sadeghi Esfahani (D-Wave)

・Defining the Quantum Accelerated Supercomputing Platform：Tim Costa (nDIVIA)

・IBM Quantum：Stefan Erlington (IBM Quantum)

・Quantum Computing on AWS and Amazon Braket：宇都宮聖子（Amazon Web Service）

・Theoretical Foundations of Quantum Advantage：Francois Le Gall（名大教授） 

■東京での開催となった実用量子計算国際会議Q2B22

　量子コンピューティングの（製造、素材、自動車、金融等々での）実用を議論する国際会議Q2B-Practical Quantum Computingは、2017年から米国で毎年開催されてきた。６回目を迎えた今年は日本での対面開催（The Westin Tokyo, July 13-14, 2022, Exclusively In-Person, Co-hosted by QCWARE & Qunasys）となった。２日間の会議において、この業界を代表する日米欧の研究者、ユーザー企業、行政機関、量子ベンダから55件の講演があった。小生は、量子コンピューティング（特に量子アニーリング）が、企業などでどのように実用されているのか、そしてその課題は何かを直に知る絶好の機会ととらえて参加した。また、IBM Qurantum、Amazon Braket等、ゲート型量子コンピュータの動向についても高い関心を持って臨んだ。

　海外のホテルでの国際会議では普通だが、早朝（８時台）からの開始となった。スポンサーとして、IBM 、D-Wave、nDIVIA等有名どころが名を連ねているためか、参加費は比較的低額に抑えられた。参加者は約1,000名という盛況であった。

　以下に、小生が特に関心を持った幾つかの講演について簡単に記す。この会議では、講演名と講演者のリストがWebの載っているだけで、アブストラクトも予稿も全く掲載されていない。ただ、会場での講演スライドのスマホによる撮影は許容されたので、それも活用し、メモをとりながら聴いていた。
　ある程度詳細にレポートしようかと思ったが、著作権上の問題があるかも知れないので（ファスト映画みたいなことにはならぬだろうが）、タイトルと極く短いコメントに留める。（本記事よりも３倍くらい詳しいレポートも作成してあります。もしも、ご入用であればご連絡ください。）

■Welcome to Q2B22 Tokyo -----

　この会議のホストの一つである先進企業QunaSysのTennin Yan（CEO）の挨拶。非常に有益な考察が示されていて感心した。以下のような項目に関してである。

（１）A lesson from classic computer history：2021年12月に東大にIBM Quantum System One実機が導入され話題となった。日本で気象予報のために最初に（1959年）導入されたコンピュータも下図のIBM704マシンだった。当時は、周辺システムもなく、誰がどんな計算をいつ行うか、そのスケジュールも全て、紙と鉛筆によっていた。しかし、そこから、利用のノウハウが蓄積され、そこで仕事をしたり遊んだりしていた人々が羽ばたいて技術を広め発展した。量子コンピュータの場合も、古典コンピュータの黎明期のように、実機を利用することでユースケースを増やし、ノウハウを蓄積して発展して行くのではないか。（２）Impact of real quantum device、（３）Learning from industrial revolution

■コヒーレントな量子アニーリング：西森秀稔教授（東工大）

　西森教授は、世界で初めて量子アニーリングを提案した物理系学者。現在の量子コンピュータNISQ（Noisy Intermediate-Scale Quantum Computer）は、ノイズ等の問題により、このままでは、「量子の死の谷」（Quantum Chasm）に陥ることが懸念されるとのこと。それをなんとか盛り上げて、誤り耐性量子コンピュータへ発展させるべく、研究開発を進めなければならない。さらに、量子アニーリングの目的、現在の量子アニーリングマシン（D-Wave）の課題と解決の方向（の一つ）、量子アニーリングの基礎研究の急速な発展に関する見解が述べられた。

■富士通における量子コンピューティングへの取り組み：佐藤信太郎（同社量子研究所長）

（１）量子ゲート方式の現状と課題、（２）デジタルアニーラを量子インスパイアード技術として先行的に推進、（３）進展中の応用などに関する説明。

■InQuanto - A Quantum Computational Chemistry Platform ：山本憲太郎（Quantinuum）

　量子化学計算による新材料の開発は、いろいろ適用分野がある中で、最も注目されるものの一つだろう。このQuantinuum社以外にも、三菱ケミカル、JSR Corp.、QunaSys、京都大学などからも、古典的量子化学計算と量子コンピューティングの融合に関して発表があり、注目分野であることを強く認識させられた。

■量子コンピュータが導く最適な配送ルート：井手貴範（アイシン）

　物流をテーマに量子コンピュータアプリ（特に量子アニーリング）を紹介した。多数の仕入れ先、数は少ない物流センター、多数の工場、多数の顧客先を結ぶトラックの最適ルートを計画することである。トータルコスを最適化する最適な配送ルート、最適なトラック台数を求める。実例での量子アニーリングの効果が示された。

■Evaluating the Potential of Quantum Annealing for your Business Apps：香月諒大（NTTデータ）

　「スポーツの開催スケジューリング」が示された。サッカー試合を、どの開催地でどの組み合わせで、いつ行うかはかなり複雑な問題となる。これを目的関数と制約条件に落とし込む。当然、興行収益を最大化するためだ。D-Waveで極く短時間で適切な解が得られた。

■感想

「習うより、慣れろ」というのがある。小生からかなり遠い分野であっても、たくさん聴いているうちに、だんだん「分かった」「判った」「解った」気になってくるから不思議である。小生は、まだ、量子アニーリングの初歩的な応用に取り組んでいるに過ぎないが、今回の参加をきっかけに、シュレーディンガー方程式の（あまり深いレベルではなく）基礎から復習して、ゲート型量子コンピュータの動作原理を把握した上で、IBM QuantumやAmazon Braketなどの環境を次第に深く利用して行こうという気になった。

　以前、小生のブログに、「量子コンピュータは商用化されているが、実用化されているとは言えない」などと勝手なことを書いた。ある面ではそれは間違いではないだろう。しかし、今回、２日間で55件の講演の約６割を実際に会場で聴いてみて、理解がだいぶ深まった気がしている。「実用化されていない」ではなく、「実用化に向けた試行や工夫がまさに盛んに行われており、急速にそのインパクトを与えつつある」と訂正したい。そして、その波は、産業界のみならず、大学のような教育研究機関へも遠くない将来、必ず押し寄せる。量子コンピュータ従事者が、現在のコンピュータのことを勝手に「古典コンピュータ」と呼んでいることもそれを示唆するように思われる。

【続編】このレポートを書いた翌日に、印象に残った講演がまだ他にあったことを思い出し、こちらに追記しました。

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

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

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

多少リアルな搬送経路最適化を量子アニーリングで（続）

　前回の「公園56ヶ所への花壇配送のための搬送経路最適化」の続編。配送先の公園の間の道が何らかの理由で通行止めの場合に、うまく対応できるだろうか？

　実はこれは簡単そうだ。なぜなら、量子アニーリングでは、エネルギー関数（目的関数）の値が最低になる経路が求められるのだから、通行止めのある場合はエネルギー関数の値がぐんと大きくなるように設計すればよい。この例題では、公園を巡る総走行距離をエネルギー関数にしているので、通行止め区間の距離を仮想的に大きくすれば、その区間を含む経路は最適解として出てこないだろう。

　果たして、それでうまくいくのか？
Yes、結果は以下の図の通りである。このケースでは、地蔵橋公園(#52)と常盤公園(#53)の間が通行止めになったと仮定した。トラック２台、４台使用の場合を示したが、いずれも、量子アニーリング結果として、この通行止め区間を避けた最適経路（の近似解）が得られた。

ちょっと勇気づけられる結果だ。

多少リアルな搬送経路最適化を量子アニーリングで

　前回の記事では、TSP（巡回セールスマン問題）は量子アニーリングのための良い例題であることを述べた。今回は、これをもう一歩進めた、多少現実味のある搬送経路最適化問題を量子アニーリングで解いてみた。Fixstars Amplifyの無料オンラインセミナーの資料を参考にさせていただいた。

■課題：公園56ヶ所への花壇配送計画    
　これは筆者が勝手に設定した架空の問題である。区役所「緑と水の課」では区内の公園56ヶ所に、新たにミニ花壇を１セットづつ配送することにした。配送トラック（最大４台）は、「楓川久安橋公園」から出発し、配送後ここへ戻る。それらの総走行距離が最小になるようにしたい。また、できるだけ短時間に配送を完了することを念頭に、各トラックの訪問先の公園数は均等にする。 

　この問題、なんだか多少リアルっぽい（あり得る）ように思いませんか！

　図１には、全56ヶ所の公園の位置と、トラック１台を使った場合の最適配送経路の算出結果を示した。１台の場合は、明らかに、前回のTSPと同一の問題となる。出発地の「楓川久安橋公園」を除いて、残りの55の公園に配送することになる。

■トラック複数台を使った搬送経路の最適化
　複数台のトラックを使用する場合には、通常のTSPの解き方を若干変更した。まず、複数台のトラックが出発点からスタートしてここへ戻るため、経路の順番毎、および、公園毎のone-hot制約を外す必要がある。すなわち、トラックの台数分に応じて、該当するQUBO変数を1または0に定数化する。さらに、トラック毎の走行距離を得るために、制約条件の対象範囲を調整する必要がある。しかしながら、これらは微々たる変更なので特段の問題はないだろう。 

　実際、図２に示す量子アニーリング結果は、トラック2台と４台を使った場合の最適経路（に近いもの）になっているはずだ。図1、図２の上部にあるenergyの値は、総走行距離に相当する。（ただし、経度と緯度をスケーリングしているため、実際の距離ではないが。）トラック台数が増えるに従って、総走行距離は増えるが、台数分に応じた配送時間の短縮が得られるのである。

　これ以外にも興味深い近似解が得られたので以下に示す。（トラック３台、４台の場合）

■感想
　現実味のあるこのような配送計画（搬送経路最適化）が、量子アニーリングにより、かなり容易に解ける（最適解に近いものが得られる）ことを体験できた。量子アニーリングでは、一般に、短時間で大量の近似解が得られる。Google Maps上に結果を描画することも難しくないので、それを眺めれば、それらの中から真に実用的な解を見出せるだろう。

　一方、実際の配送計画問題では、以下のような制約も含まれるので、それらにも挑戦したい。コストとして、次の公園までの距離に加算できる制約であれば取り扱いは容易だ。

• 通行止め区間がある。
• 通過できる経路が定められている
• トラックの積載量に制限がある
• 配達先ごとに到着時間の制限がある
• 各配達先で作業時間が異なる
• 工場内のAGVでは、交差点制御、衝突回避なども考慮

　一例として、「通行止め区間がある場合」の検討結果はこちら。

-------------------

量子アニーリング（イジングモデル）で卒研発表会をスケジュール(2)

【要旨】スケジュール(1)の続編です。その記事の末尾に書いた[別法]を具体的に示します。Fixstars Amplify SDKで提供される、量子アニーリング向けの様々な制約の与え方に関するメモでもあります。

■例題：いくつかの制約のある会議のスケジューリング

　今回は、図１に示すような会議スケジューリングを行います。人手でも解ける簡単な例題ですが、量子アニーリングにおける様々な制約を与える上で参考にして戴けるかと思います。

　６つの会議（A〜F）を３つの会議室（K0、K1、K2）で、9:00 - 11:50の間に行うとします。どの会議をどの会議室で行うかは、図の通りに予め決まっています。問題なのは、参加者の都合と一つの会議室では（当然ですが）同時に複数の会議はできないことから、時間帯が重なることが許されない会議が図のように決まっていることです。なお、同一会議室での会議の入替え、および、参加者が移動する会議間には10分間の余裕が必要とします。これらを全て満たすスケジュールを、量子アニーリングで求める問題です。

■量子アニーリングによるスケジューリングの結果

　離散化した時間の個数（10分単位）と会議の数の積の個数分のQUBO変数を用意しました。そのQUBOを変数を用いて、図１に示された制約の全てを表現できます。今回は、Fixstars Amplify SDKの関数penalty、sum、sum_poly、equal_toなどを利用しました。

　結論を先に示します。図２(a)は、これらの制約を与えた量子アニーリングの実行結果です。会議毎に１つだけ存在する、北向きの赤い矢印のセットが（一つの）解を示しています。図２(b)はこれを見やすく可視化したものです。図１(a)の赤矢印は、会議の開始時刻を示していますので、それが図２(b)では赤丸で表現されています。

■penalty関数を用いた制約の与え方

　上で与えた制約のうち、「所定の会議同士の時間帯の重複を許さない」という制約を、penalty関数で表現する方法を図３に示しました。

　これ以外に、「各会議のQUBO変数は、必ずただ一つの時間点において１となる」というone-hot制約は、sum_poly関数とequal_to関数を用いて表現できます。penalty関数による制約とこれらの制約を全て加算した形の最終的な制約を量子アニーリングに与えることができました。

■別解もたくさん得られるのがいいところ

　この解法では、たくさんの解が短時間で得られるのが良いところです。例えば、図２の解の場合、会議Eの出席者で「朝、会議前にもうちょっとコーヒータイムが欲しい」という人が多いとします。しかし、単に会議Eを遅らせると、その終了が会議Aの開始と重なってしまうので、まずい。でも、図４のような別解ならOKですね！

　この別解では、EとDが入れ替わっていますが、同時にAとBもこのように入れ替える必要がありました。今回は演習用のため問題が簡単すぎたかも知れませんが、今後、もっと複雑な問題で本領を発揮できるでしょう！

■所望の解を得るには何度かの試行が必要

　この規模のスケージューリングでも、解が得られない（制約条件を全ては満たせない）状況になることもあります。その場合は、アニーリングのタイムアウトを長めにすることで上手く行くことがあります。日立CMOS Annealing マシンを利用する場合は、タイムアウトをアニーリングの温度パラメータ（初期値、ターゲット値、下降ステップ数、ステップ長）の調整で行えます。（こちらにある、イジングエディタの左欄詳細設定の温度設定の解説図が分かりやすいです。）

　しかしながら、タイムアウトは一つの要因に過ぎず、制約条件をどのように与えるかも効いてきます。この例では、会議の長さに応じて、これ以降の時刻では開始できないという制約があるのですが、それをpenalty関数で上記のように与えるか、それとも、その時刻領域のQUBO変数を定数(0)とするかで、解への収束状況が異なることも分かりました。まだまだ未知の部分があります。