量子コンピューターの一種で渋滞緩和を目指す。都市全体の信号機制御を最適化

　すべての信号機の青信号の時間を、交通量に合わせて最適化できれば、渋滞をもっと緩和できると思ったことはないだろうか。実はすでに一部の信号機は、周辺の交通量を把握し、状況に合わせて青信号の点灯時間を変えている。さらに都市全域で最適なタイミング制御ができるようになれば、交通の流れがよりスムーズになるのは間違いない。

　しかしその実現には、技術的な困難さが立ちはだかる。その理由は、制御するためには数学の「組み合わせ最適化問題」が必要となるからである。組み合わせ最適化問題は、条件によっては、最新のスーパーコンピューターで延々と計算しても終わらないという、膨大な計算処理が必要な問題なのだ。

「巡回セールスマン問題」でわかる組み合わせ最適化問題の”クセモノ”ぶり

　組み合わせ最適化問題を理解するには、その代表である「巡回セールスマン問題」がわかりやすい。これはセールスマンが、たとえば5つの都市を1回ずつ訪問して出発地の都市に戻るとき、複数あるルートの中から、どういう順序で都市を回っていけば最短距離となるのかを選び出す問題のことだ。

　都市の数が少ないうちは一見すると簡単に見える。しかし都市をどの順序で回るかという組み合わせの数は、見た目に反したところがあり、計算してみるとその大変さがわかる。都市間の距離などはひとまず置いておき、単純にルートが何通りあるか計算すると、5都市の場合は5×4×3×2×1=120通りとなる。そして120通りすべての距離を算出し、どれが最も短距離かを比較して見極めれば最短ルートがわかるというわけだ。この程度の数なら、パソコンでも計算できるだろう。

　しかし、これが10都市だとどうだろうか。10×9×…2×1=362万8800通りとなる。都市の数は2倍になっただけだが、組み合わせは3万240倍だ。3倍の15都市だとどうなるか。なんと、1兆3076億7436万8000通りとなる。都市の数は3倍に過ぎないが、組み合わせの数は108億9728万6400倍である。このように、組み合わせが爆発的に増えていくのが特徴で、実際に計算してみないとその大変さが分かりづらいところが、”クセモノ”なのである。

　そしてどのルートが最短距離なのかを算出するには、実際に1兆3076億7436万8000通りの全ルートの距離を算出して比較する必要がある。仮に1ルートの距離を算出するのにかかる時間が0.0001秒だとしても、15都市の全ルートを算出するには4年以上もかかってしまう計算だ。

　都市圏全体の信号機をまとめて制御するということは、単純に考えると、巡回セールスマン問題の都市の数を信号機に置き換えればよい。厳密には、どの信号機を通るかというルートの話ではないのだが、組み合わせ最適化問題で扱うことが可能だ。しかし、信号機の数が増えれば増えるほど、計算に膨大な時間を必要とすることは同じである。

　まして信号機制御の演算は、リアルタイム性を求められることから、可能なら毎秒、遅くても10秒に1回程度は交通状況の取得と計算を行うのが望ましいはずだ。そうすると、ひとつの組み合わせにかけられる時間は、信号が15しかないとしても、1307億6743万6800分の1秒しかない（厳密には比較などの時間もあるので、もっと早く計算する必要がある）。信号機の数がひとつ増えるだけで、組み合わせの数は1桁増えたりするので、50、100と増えていったら、1回の計算にかけられる時間はとてつもなく短くなっていく。つまり、これまでは都市全体の信号機を制御したくても、できないというのが実情だったのである。

量子コンピューターなら膨大な計算もお手のもの

　そうした中、豊田中央研究所 数理工学研究領域の井上大輔研究員、同・岡田明久研究員、同・松森唯益研究員、同・吉田広顕研究員、そして東大の特別教授兼名誉教授で東大ニューロインテリジェンス国際研究機構の副機構長も務める合原一幸氏の共同研究チームが今回着目したのが、従来のコンピューターとは異なる仕組みで動作する量子コンピューターだ。

　量子コンピューターと従来のコンピューターでは、扱う情報単位がまず異なる。通常のコンピューターの1ビットは、コンピューターが扱う2進数のうち、0か1のどちらかを表す。別のいい方をすれば、0か1のどちらかしか表わせない。しかし量子コンピューターの扱う1量子ビットは、量子の特性を利用することで0と1の両方を「重ね合わせて」表すことができる。難解だが、0と1の両方を並行して計算できてしまうのである。0でもあると同時に1でもあるという、まるでパラレルワールドのような不思議な原理が利用されているのだ。

　この原理を利用することで、とても大まかな表現ではあるが、何台ものコンピューターを同時に扱うような計算力を実現できるといわれている。つまり、膨大な計算を必要とする組み合わせ最適化問題でも、実用的な時間内に答えを出せると期待されているのである。ただし、汎用的な量子コンピューターはまだごく初期のレベルであり、IBMやGoogleなどの民間企業を始め、米国、中国などが開発に力を入れているが、実用化にはまだ時間がかかりそうだ。

　今回はその量子コンピューターの一種といわれ、組み合わせ最適化問題に特化したカナダ・D-Wave社製の商用量子アニーリングマシン「D-Wave2000Q」（画像1）が計算に用いられた。同マシンは当初、量子コンピューターか否かで意見が割れたことがあったが、「量子ゆらぎ」と呼ばれる量子力学的な物理現象を利用することから、現在ではその一種として扱われている。ただし組み合わせ最適化問題に特化しているとはいっても、今回のような大規模かつ複雑な問題を解くには、近似や変数変換などの工夫が必要だったという。

画像1。カナダ・D-Wave社製の商用量子アニーリングマシン「D-Wave2000Q」。2011年に発売され、のちにNASAとGoogleが共同購入したことでも知られる。2019年には、フォルクスワーゲンも交通最適化プロジェクトのためにD-Wave社製量子アニーリングマシンを利用。画像出典:D-Wave社Webサイト

道路網や車両群の走り方をシンプル化して計算を実施

　今回の研究では、量子アニーリングマシンで扱えるようにするため、シンプル化した上で計算が行われた。まず道路網を縦横に直交する格子で表現。そして道路網上の交通は一定の確率で右左折する車両群を用いることで表された（画像2）。このようにした上で解析が行われたところ、交通流の偏りを最小化できる信号の色の組み合わせを決めることが可能であることが判明したという。

画像2。今回は道路網は碁盤の目とされ、道路網を走る車両群は一定の確率で右左折するという設定で計算された。画像出典：東京大学プレスリリースPDF

　さらに共同研究チームは、50×50の格子状の道路で構成された仮想都市の信号機を、一斉に制御する数値実験を実施。交通流の偏りの大きさを表す評価関数の値について、今回の量子アニーリングマシンを用いる手法と従来手法とで比較を行った。すると、従来手法と比べて評価関数の値を約10%小さくできることが確認されたのである。つまり、10%の交通流の改善ができるということだ。

　また今回の計算は、従来のコンピュータで「焼きなまし法」などの最適化手法を用いても求解することが可能だという。そこで、今回の量子アニーリングマシンによる手法に加え、従来のコンピューターを用いた焼きなまし法および局所的制御の3種類による比較が行われた。

　すると、車の直進率がおおよそ0.6～0.85ぐらいまでの間は、焼きなまし法が若干評価関数値が低い（つまり交通の流れがいい）ことが判明。ただし直進率が上がってくると、今回の量子アニーリングマシンを用いた手法の方が評価関数値が、値がよくなる（値が低くなる）ことが確かめられた（画像3）。

画像3。今回の量子アニーリングマシンを用いた手法と、従来のコンピューターを用いた焼きなまし法と局所的制御の3種類の比較。画像出典：東京大学プレスリリースPDF

　共同研究チームは、将来的に量子コンピューターが発展し、期待されている性能を実際に発揮できるレベルになれば、今回の手法は現実の都市の信号機群を都市全体の交通状態に応じて、高速かつ効率的に制御するための基盤技術となる可能性があるとしている。