@yuichirominato 2018.06.14更新

D-waveの量子コンピュータとGoogle Maps APIで実際に使える交通最適化ウェブアプリ(羽田空港から新国立競技場の道路混雑緩和)を作ってみた

D-Wave QUBO イジング 交通流最適化 量子アニーリング

はじめに

カナダのベンチャー企業D-Wave社の量子アニーリングを基本原理に採用したマシンを使って組合せ最適化問題の社会実装をフォルクスワーゲン社(以下VW社)が行いました。北京の市内から空港までの交通混雑状況をD-Waveを使用した組合せ最適化問題で混在解消するという社会実験です。下記の図の左側の混雑状況が右側のように緩和されます。

引用:https://www.dwavesys.com/media-coverage/automotive-it-vw-cio-technology-being-readied-address-real-issues

その交通最適化のアプリケーションの構築方法が資料として色々公開されていますので、簡単な例題として実装して見たいと思います。ちなみに実際にD-Waveを使って事前にアルゴリズムを解いて見た記事もありますので、そちらも参照してください。今回はフロントエンドのアプリケーションを含むより詳しい実際に使えるアプリケーションとして構築します。

「D-WaveでVW社の交通最適化アプリケーションの実装を解く」
http://blog.mdrft.com/post/176

使用するマシンはカナダのD-Wave社のマシンで、自社で借りている本物を使用しました。

参考にした資料は下記です。

「Quantum Computing at Volkswagen:
Traffic Flow Optimization using the D-Wave Quantum Annealer」
引用:https://www.dwavesys.com/sites/default/files/VW.pdf

D-Waveやイジングモデル、量子アニーリングやQUBOなどについての一般的な資料

今回は社会実装のアプリケーションで結構色々な知識が出てきます。細かい個別の話はそれぞれ理解する必要がありますので、下記のところから参照して学んで見てください。

イジングモデルや量子アニーリングについては過去の記事
「量子アニーリング、イジングモデルとフレームワーク」
http://blog.mdrft.com/post/6

一般的なイジングモデルのNP問題の解法はこちら
「NP問題のイジング」
http://blog.mdrft.com/post/42

D-Wave社とVW社が行なった実装手順のおさらい

まずは、論文や資料で公表されている手順は下記の通りです。論文中のchaper2から引用しました。既存計算機を「古典計算機」と表現しています。

Classical: Pre-process map and GPS data.
(古典計算機)地図とGPSデータからデータの準備をする。

Classical: Identify areas where traffic congestion occurs.
(古典計算機)次に混雑が起こっている場所を特定する。

Classical: Determine spatially and temporally valid alternative routes for each car in the dataset, if possible.
(古典計算機)データセット内の自動車に対して代替ルートを提案する

Classical: Formulate the minimization problem as a QUBO (to minimize congestion in road segments on overlapping routes).
(古典計算機)混雑が緩和するような組合せ最適化問題に落とし込む。その際のQUBOと呼ばれる形式を採用する。

Hybrid Quantum/Classical: Find a solution that reduces congestion among route assignments in the whole traffic graph.
(古典計算機・量子コンピュータハイブリッド)問題を古典計算機による分割と量子コンピュータによる最適化を繰り返す。

Classical: Redistribute the cars based on the results.
(古典計算機)上記の得られた答えから自動車の位置を再配置する。

Iterate over steps 2 to 6 until no traffic congestion is identified.
上記のステップを混雑が緩和されるまで繰り返し計算する。

引用:https://arxiv.org/pdf/1708.01625.pdf

##次に今回実装するアプリケーションの見込みをつける。
今回実装したアプリケーションは主にhtmlベースのウェブアプリケーションとD-Waveをつなげます。その際に注意すべき点や実装手段を1つずつ確認していきます。

使用したツールは下記です。
・Google Maps API (Javascript)
・JQuery
・AWS lambda nodejs

1つずつ確認していきます。

Google Maps API

今回は交通最適化ですので地図を使いたいです。普通はOpen Street Mapなどの無料のOSSを使用しますが、今回は簡略化のために便利なGoogle Mapをつかいます。APIが公開されており、自分のアカウントからAPIを使用できますので、それを利用しました。

https://developers.google.com/maps/?hl=ja

また、今回は交通混雑を表現するのに、ヒートマップを利用しました。見た目にどこが混雑しているのか一目でわかります。ヒートマップについてはGoogle Maps APIにヒートマップレイヤーと呼ばれるものが用意されていますので、それを使用します。

ヒートマップレイヤーの使い方は、座標を設定しながらヒートマップ表現したいところを連続してうっていきます。下記はサイトに載ってる例です。


/* Data points defined as a mixture of WeightedLocation and LatLng objects */
var heatMapData = [
  {location: new google.maps.LatLng(37.782, -122.447), weight: 0.5},
  new google.maps.LatLng(37.782, -122.445),
  {location: new google.maps.LatLng(37.782, -122.443), weight: 2},
  {location: new google.maps.LatLng(37.782, -122.441), weight: 3},
  {location: new google.maps.LatLng(37.782, -122.439), weight: 2},
  new google.maps.LatLng(37.782, -122.437),
  {location: new google.maps.LatLng(37.782, -122.435), weight: 0.5},

  {location: new google.maps.LatLng(37.785, -122.447), weight: 3},
  {location: new google.maps.LatLng(37.785, -122.445), weight: 2},
  new google.maps.LatLng(37.785, -122.443),
  {location: new google.maps.LatLng(37.785, -122.441), weight: 0.5},
  new google.maps.LatLng(37.785, -122.439),
  {location: new google.maps.LatLng(37.785, -122.437), weight: 2},
  {location: new google.maps.LatLng(37.785, -122.435), weight: 3}
];

var sanFrancisco = new google.maps.LatLng(37.774546, -122.433523);

map = new google.maps.Map(document.getElementById('map'), {
  center: sanFrancisco,
  zoom: 13,
  mapTypeId: 'satellite'
});

var heatmap = new google.maps.visualization.HeatmapLayer({
  data: heatMapData
});
heatmap.setMap(map);

前処理とJquery

今回は膨大な前処理が発生します。サーバーサイドの処理を最低限にするためにほとんどをフロントエンドでアルゴリズムを処理してしまい、最適化計算だけをD-Waveに投げるようにします。その際にフロントエンドのアプリケーションなので処理はすべてjavascriptで行う必要があります。

javascriptで行うべき処理は、前述のVW社の論文中の道路の混雑を取得するところや代替ルートの提案、組み合わせをD-Waveに投げるajax通信や戻ってきた処理結果を用いて、Google Maps APIで処理をするところなど全般に渡ります。

便利なのでJqueryを使います。

デザインについて

当初はbootstrapを使用しようかと思っていましたが、結局Google Maps APIでほとんどの表現が終わってしまうので、デザイン部分においてはライブラリなどは使用しませんでした。

データについて

今回は手元で作っていて、実際の交通データは手に入っていないので、ダミーデータで行います。ただ、今回の交通最適化に関してはアルゴリズムの特性上ダミーデータで十分であると思います。順を追って解説していきます。

早速実装に入っていきます。

ステップ1:全体の取りうる経路を設計する

VW社の論文や参考資料から、アルゴリズムは最初に取りうる経路を決めておく必要があります。例えば下記の資料や以前別の記事で解いた問題に関しても、スタート地点Aとゴール地点Bがあるとき、2×2のグリッドで12のセグメント道路からなる簡易的な経路を設定しています。


引用:https://www.dwavesys.com/sites/default/files/VW.pdf

今回も複雑にしすぎないようにまずは2×2のグリッドから12のセグメントに分けた問題を用意します。

シチュエーションも考えて見て、2020年のオリンピックを想定して羽田空港から新国立競技場までの混雑ルート提案を行なって見ます。

最初に行うのは、羽田空港から新国立競技場までの12のセグメントを選んでルートを決めるところです。

羽田空港から新国立競技場まで2×2のグリッドの模式図を作って見ました。スタート地点が右下からになっているのに注意。

ここで必要なのは、道路が12本と交差点が5つです。今回はそれぞれをGoogleMap上で選んで見ます。ちょっとGoogleMapで検索して見ました。首都高速中央環状線経由というルートを選んで見ましたが、実際にはやはり都内で混雑するようです。今回はアプリを作るのが目的なので、経由地や道路はエイヤ!で決めます。

経路を決めるのに苦労しましたが、決めました。

これを早速Google Mapでやっていきます。
12本の経路をスプライン表示でウェブアプリの上に表示していきます。

ステップ2:Google Maps API上で表現をする

Google Maps APIの具体的な仕様の方法は、下記のサイトを参照してください。
特に今回はウェブアプリなのでJavascriptを使用しました。

https://developers.google.com/maps/documentation/javascript/?hl=ja

では、実際にhtmlファイルを用意して、上記の手順通りマップを用意します。表現はかっこいいので衛星写真にしました。何も入れていないので、プレーンな状態がブラウザ全体に広がります。

名称未設定.jpeg

次にルートを設定していきます。この地図上にルートを表現するにはルートのスプライン情報をえて、それを渡してあげる必要があります。先ほど決めたルートのスプライン情報をえて、Google Map上に重ねます。

GoogleMapは取得したスプラインを配列の形で格納できます。


ついでにオシャレにマーカーを配置しました。

確認したところ、結構いい感じでモデルとあってる気がします。

ステップ3:自動車の配置を考える

次に自動車の配置を考えます。自動車は4台程度にして見ます。
配置はいい感じに入れて見ます。セグメント道路に入れて見て、実際の後ほど行う代替ルート提案は近隣の交差点からやります。

せっかくなので、2台はスタート地点から、のこり2台はそれぞれの途中地点に入れて見ます。

こんな感じです。

ステップ4:各自動車に対して目的地までのルート提案3ルートずつをつくる

各自動車に対して取りうるルートを3つずつ提案し、そのうちの1つを採用していることにします。
自動車#1と自動車#2はスタート地点からで同じルートを選んでいることにします。
自動車#3と自動車#4についても提案ルートを作ります。

エクセルで作って見ました。

図で表すとこんな感じです。

ステップ4:道路混雑を取得する

VW社の論文によると、道路混雑状況はこの自動車の配置から割り出します。先ほどの経路提案からその中に含まれるセグメントの道路の数を全て道路ごとにカウントします。その際に出てきた道路を経路提案の表記で表します(Q11とか)。こちらもとりあえずエクセルでやって見ました。

トータルの混雑状況はコスト26と出ています。このコストを量子コンピュータによって下げて混雑解消します。具体的に手作業で別ルートを選んで見てコストが下がるかどうかを検証した結果は下記の記事から見て見てください。今回は一般式を使って実装を進めます。

「D-WaveでVW社の交通最適化アプリケーションの実装を解く」
http://blog.mdrft.com/post/176

ステップ5:混雑計算の一般式をQUBOでつくる

QUBOとはバイナリの値{0,1}をつかって、ハミルトニアンと呼ばれる数式を作ります。今回ハミルトニアンで必要になるのは、

1、混雑量を計算するコスト関数
2、自動車1台について代替ルート提案を1ルートだけ選ぶ制約条件

の2つになります。まず前者からやってみます。交通混雑のコストは前述の各セグメントの混雑を全て足し合わせたものです。一般的な表記を残したまま、全てを足して見ます。

$
H = (Q_{11}+Q_{12}+Q_{21}+Q_{22})^2 + (Q_{12}+Q_{22}+Q_{43})^2 + (Q_{13}+Q_{23})^2 + (Q_{11}+Q_{21}+Q_{43})^2
+ (Q_{12}+Q_{22}+Q_{43})^2 + (Q_{13}+Q_{23}+Q_{32}+Q_{33})^2 + (Q_{11}+Q_{21}+Q_{33}+Q_{41})^2 + Q_{31}^2
+ (Q_{13}+Q_{23}+Q_{32}+Q_{42})^2 + (Q_{11}+Q_{12}+Q_{21}+Q_{22}+Q_{33}+Q_{41}+Q_{43})^2 + Q_{31}^2
+ (Q_{13}+Q_{23}+Q_{31}+Q_{32}+Q_{42})^2
$

つぎにこれをすべて展開します。今回は勉強のためにコツコツ展開しますが、さすがに数が多いので、sympyを使って式展開をpythonで自動化しました。


from sympy import *

Q11,Q12,Q13,Q21,Q22,Q23,Q31,Q32,Q33,Q41,Q42,Q43 = symbols("Q11 Q12 Q13 Q21 Q22 Q23 Q31 Q32 Q33 Q41 Q42 Q43")
f = (Q11+Q12+Q21+Q22)**2 + (Q12+Q22+Q43)**2 + (Q13+Q23)**2 + (Q11+Q21+Q43)**2 + (Q12+Q22+Q43)**2 + (Q13+Q23+Q32+Q33)**2 + (Q11+Q21+Q33+Q41)**2 + Q31**2 + + (Q13+Q23+Q32+Q42)**2 + (Q11+Q12+Q21+Q22+Q33+Q41+Q43)**2 + Q31**2 + (Q13+Q23+Q31+Q32+Q42)**2

print(expand(f))

そうすると自動的に展開できました。


4*Q11**2 + 4*Q11*Q12 + 8*Q11*Q21 + 4*Q11*Q22 + 4*Q11*Q33 + 4*Q11*Q41 + 4*Q11*Q43 + 4*Q12**2 + 4*Q12*Q21 + 8*Q12*Q22 + 2*Q12*Q33 + 2*Q12*Q41 + 6*Q12*Q43 + 4*Q13**2 + 8*Q13*Q23 + 2*Q13*Q31 + 6*Q13*Q32 + 2*Q13*Q33 + 4*Q13*Q42 + 4*Q21**2 + 4*Q21*Q22 + 4*Q21*Q33 + 4*Q21*Q41 + 4*Q21*Q43 + 4*Q22**2 + 2*Q22*Q33 + 2*Q22*Q41 + 6*Q22*Q43 + 4*Q23**2 + 2*Q23*Q31 + 6*Q23*Q32 + 2*Q23*Q33 + 4*Q23*Q42 + 3*Q31**2 + 2*Q31*Q32 + 2*Q31*Q42 + 3*Q32**2 + 2*Q32*Q33 + 4*Q32*Q42 + 3*Q33**2 + 4*Q33*Q41 + 2*Q33*Q43 + 2*Q41**2 + 2*Q41*Q43 + 2*Q42**2 + 4*Q43**2

そして、式を得ます。

$
H = 4Q_{11}^2 + 4Q_{11}Q_{12} + 8Q_{11}Q_{21} + 4Q_{11}Q_{22} + 4Q_{11}Q_{33} + 4Q_{11}Q_{41} + 4Q_{11}Q_{43} + 4Q_{12}^2 + 4Q_{12}Q_{21} + 8Q_{12}Q_{22} + 2Q_{12}Q_{33} + 2Q_{12}Q_{41} + 6Q_{12}Q_{43} + 4Q_{13}^2 + 8Q_{13}Q_{23} + 2Q_{13}Q_{31} + 6Q_{13}Q_{32} + 2Q_{13}Q_{33} + 4Q_{13}Q_{42} + 4Q_{21}^2 + 4Q_{21}Q_{22} + 4Q_{21}Q_{33} + 4Q_{21}Q_{41} + 4Q_{21}Q_{43} + 4Q_{22}^2 + 2Q_{22}Q_{33} + 2Q_{22}Q_{41} + 6Q_{22}Q_{43} + 4Q_{23}^2 + 2Q_{23}Q_{31} + 6Q_{23}Q_{32} + 2Q_{23}Q_{33} + 4Q_{23}Q_{42} + 3Q_{31}^2 + 2Q_{31}Q_{32} + 2Q_{31}Q_{42} + 3Q_{32}^2 + 2Q_{32}Q_{33} + 4Q_{32}Q_{42} + 3Q_{33}^2 + 4Q_{33}Q_{41} + 2Q_{33}Q_{43} + 2Q_{41}^2 + 2Q_{41}Q_{43} + 2Q_{42}^2 + 4Q_{43}^2
$

これをmatrixの形にします。まずエクセルでやってみました。縦横12量子ビットずつのmatrixにいれこみます。

ステップ6:QUBOをイジングに直す

式変換を使ってイジングに直していきます。詳しい内容は下記の記事を参照してください。

「D-WaveでVW社の交通最適化アプリケーションの実装を解く」
http://blog.mdrft.com/post/176

なおしたmatrixはこちらです。

ただ、こちらだけでは一般式は完成ではありません。1台の車が取りうる代替ルートの制約条件をつけます。

ステップ7:制約条件をつける

詳しくはまた上記の記事を参照していただいて、制約条件をつけます。つける条件は、

$
H = K*(Q_{11}+Q_{12}+Q_{13}-1)^2+K*(Q_{21}+Q_{22}+Q_{23}-1)^2+K*(Q_{31}+Q_{32}+Q_{33}-1)^2+K*(Q_{41}+Q_{42}+Q_{43}-1)^2
$

こちらを展開して、

$
KQ_{11}^2 + 2KQ_{11}Q_{12} + 2KQ_{11}Q_{13} – 2KQ_{11} + KQ_{12}^2 + 2KQ_{12}Q_{13} – 2KQ_{12} + KQ_{13}^2 – 2KQ_{13} + KQ_{21}^2 + 2KQ_{21}Q_{22} + 2KQ_{21}Q_{23} – 2KQ_{21} + KQ_{22}^2 + 2KQ_{22}Q_{23} – 2KQ_{22} + KQ_{23}^2 – 2KQ_{23} + KQ_{31}^2 + 2KQ_{31}Q_{32} + 2KQ_{31}Q_{33} – 2KQ_{31} + KQ_{32}^2 + 2KQ_{32}Q_{33} – 2KQ_{32} + KQ_{33}^2 – 2KQ_{33} + KQ_{41}^2 + 2KQ_{41}Q_{42} + 2KQ_{41}Q_{43} – 2KQ_{41} + KQ_{42}^2 + 2KQ_{42}Q_{43} – 2KQ_{42} + KQ_{43}^2 – 2KQ_{43} + 4K
$

これを再度QUBOの形式に直すと、
ee.jpeg

さらにここからイジングに直します。
test.jpeg

この式を先ほどの一般式と組み合わせます。
tt.jpeg

あとは、この式にKを決めて代入し、D-Waveに入れることで計算が最適化できます。

ステップ8:自動車のリストをフロントに表示してみる
一方でウェブアプリのフロントの表示の方も進めていきます。
わかりやすくするため、自動車のリストとそれに対応する提案ルートを表示させて見ます。
また、自動車をクリックしたらルートを表示させて見ます。


とりあえずなんとなくできてきました。
自動車のリストから提案ルートをクリックしてルートが表示されます。


function drawpoly(seg){
 let request = {
  origin: seg[0],
  destination: seg[1],
  travelMode: "DRIVING",
 };

 directionsService.route(request, function(response,status) {
  if (status === google.maps.DirectionsStatus.OK) {
   var polypath = new google.maps.DirectionsRenderer({
    preserveViewport: true,
    map: map,
    directions: response,
    suppressMarkers: true
   });

   drArr.push(polypath);

  }
 });
};

ステップ9:混雑をヒートマップで表現

こちらはGoogle Mapのヒートマップレイヤというものを使いました。上記のルートを取得した上、ルートに即した形でヒートマップを用意して表現することができました。

https://developers.google.com/maps/documentation/javascript/heatmaplayer?hl=ja
下記のような例題を改造して今回に適用しました。


/* Data points defined as an array of LatLng objects */
var heatmapData = [
  new google.maps.LatLng(37.782, -122.447),
  new google.maps.LatLng(37.782, -122.445),
  new google.maps.LatLng(37.782, -122.443),
  new google.maps.LatLng(37.782, -122.441),
  new google.maps.LatLng(37.782, -122.439),
  new google.maps.LatLng(37.782, -122.437),
  new google.maps.LatLng(37.782, -122.435),
  new google.maps.LatLng(37.785, -122.447),
  new google.maps.LatLng(37.785, -122.445),
  new google.maps.LatLng(37.785, -122.443),
  new google.maps.LatLng(37.785, -122.441),
  new google.maps.LatLng(37.785, -122.439),
  new google.maps.LatLng(37.785, -122.437),
  new google.maps.LatLng(37.785, -122.435)
];

var sanFrancisco = new google.maps.LatLng(37.774546, -122.433523);

map = new google.maps.Map(document.getElementById('map'), {
  center: sanFrancisco,
  zoom: 13,
  mapTypeId: 'satellite'
});

var heatmap = new google.maps.visualization.HeatmapLayer({
  data: heatmapData
});
heatmap.setMap(map);

これだけだとちょっとわかりづらいので、googlemap上に混雑状況を表示させ、ヒートマップと連動させて見ます。かつ、なんの処理をしているのかわかりやすくするために、左側にコンソールもつけて見ました。

本当はルート提案も自動化したいところですが、今回は大変なので一旦決め打ちで。自動車ごとに代替ルートを設定しました。自動車ごとに配列で3つの経路提案が格納されています。この配列内のルートの数をカウントしていきます。


var N = 4;
var cars = new Array(N);
cars[0] = [[0,3,6,9],[0,1,4,9],[2,5,8,11]];
cars[1] = [[0,3,6,9],[0,1,4,9],[2,5,8,11]];
cars[2] = [[7,10,11],[5,8,11],[5,6,9]];
cars[3] = [[6,9],[8,11],[3,1,4,9]];

var selected = [0,0,0,0];//それぞれの車のどの経路提案が現在選択されているか明示

上記でselectedで選ばれている配列の道路をカウント、それを二乗したものが道路の混雑コスト

var Ns = 12;//セグメント数
var ccc = new Array(12);//カウントを格納する配列
for(var i=0;i<Ns;i++){//初期化
 ccc[i] = 0;
}

for(var i=0;i<N;i++){
 for(var j=0;j<3;j++){
  if(selected[i] == j){//選ばれてれば
   for(var k=0;k<cars[i][j].length;k++){
    ccc[cars[i][j][k]]++;//カウント
   }
  }
 }
}

console.log(ccc);

きちんととれてました。この各成分を二乗して使います。

(12) [2, 0, 0, 2, 0, 0, 3, 1, 0, 3, 1, 1]

画面の右側に道路のトータルの混雑状況と各道路の混雑のコストを表示。前に計算したエクセルの表とも合致しています。

そして、この得られた混雑に関してヒートマップに重み付けをしながら混雑を地図上に表現。道路の混雑コストの閾値によって混雑の表現が変わりました。たとえば、閾値を9にしてみる(つまり、自動車が3台以上通る)としてみると、

競技場付近がとても混雑しています。また、閾値を下げて4(つまり自動車が2台以上通る)にしてみると、

こんな感じで、特定のルートが混雑しているのがわかりました。とりあえず表現できることはしました。次はいよいよD-Waveの量子コンピュータと接続する部分を用意します。

すみません、スクリプトを改造してもう少しヒートマップをみやすくしてみました。

ステップ10:D-Waveにつなぐサーバーサイドスクリプトを作成

D-Wave社はSAPIと呼ばれるSolverAPIを用意しているので、そのエンドポイントに投げればジョブを投入できます。ジョブスケジューラが動いているようなので、ジョブの投入をしてからレスポンスの中に含まれるジョブIDを持って、再度計算結果を取得する必要があります。

マイクロ秒単位出処理されているので、大体はほぼリアルタイムで処理されますが、今回はとりあえずフロントからジョブを投げて、フロントで再度結果を回収するというスクリプトを書きます。環境は下記のD-Wave社のサイトを参考にしてください。

引用:https://www.dwavesys.com/software

さてリクエストを投げたいのですが、投げるリクエストは前にエクセルで作った方をベースにしますが、お決まりでNo ‘Access-Control-Allow-Origin’のためフロントのアプリから直接ajax+jsonではリクエストを投げられません。JSONPでもだめでした。

ということで、おとなしくサーバーサイドのスクリプトを用意して、D-Waveと繋ぐ必要があります。APIはRESTの仕様がドキュメントとして載っていますので、参考にするか配布されているライブラリなどを利用します。

今回はジョブを投げるためだけにサーバー立ち上げるの面倒なので、awsでサーバーレス環境を使って、lambda+nodejsで独自にスクリプトを書いて見ました。管理が簡単です。

参考:https://aws.amazon.com/jp/serverless/

特に外部公開は予定していないのでaws-sdkからlambdaを操作します。
はい、できました。サンプルのデータを実機に投げて見て無事結果が戻っています。

ちなみにライブラリいれるのめんどいので標準モジュールでやりました。
ヘッダーに認証情報入れるなど仕様上色々必要です。
参考:https://qiita.com/r-yanyo/items/3ef153dac12e69a2c46c

ステップ11:フロントからサーバーサイドを叩いてD-Waveに問題を送り、結果を回収

上記で準備はできましたので、いよいよつなげます。必要なlambdaのnodejsファイルはジョブ投入と結果回収の2種類です。

lambdaでのジョブの投入は普通のlambdaをaws-sdkから。
参考:https://qiita.com/studio-kakky/items/3791ba5f383f1797f73f



今回投入するのは12量子ビットの完全結合で考えるので、上記のQUBOmatrixをキメラグラフに落とし込みます。今後は回路はなるべく一般化してアプリとして使いやすくします。

まずは12量子ビットの完全結合をキメラグラフで一般化。
下記のように結合を決めます。同じ色が強結合で擬似的に1論理量子ビットとして考えて、完全結合を構成しています。

論理回路へ落とし込み、量子ビットの番号を控えて、これをAPIサーバーに送ります。
最終的に得たい答えは$q_i=\\{q_0,q_1,q_2,q_3,q_8,q_9,q_{10},q_{11},q_{16},q_{17},q_{18},q_{19}\\}$の量子ビットを見れば良いことになります。

サーバーサイドの処理は少し工夫しましたが、基本的にはフロントからデータが送れています。参考に特定の問題を送る時のlambdaはこんな感じです。base64の処理やバイナリ値はサーバーサイドで処理していますので、フロントエンドは比較的シンプルに。


 var lambda = new AWS.Lambda();

 var params = {
  FunctionName:"dwave",
  Payload : JSON.stringify({"jij":"2048 2\n 0 0 -1\n0 4 -1"}),
 };

 lambda.invoke(params,function(err,data){
  if(err){
   console.log(err,err.stack);
  }else{
   var res = data.Payload;
   res = JSON.parse(res);
   res = JSON.parse(res.Payload);
   console.log(res);
  };
 });

ステップ12:得られた結果からコストを再計算して混雑が解消されたことを確認

得られた結果を使って再度道路混雑の計算を再計算し、ヒートマップを書き直して下記のように終了です。きちんとコストが下がり、交通混雑が解消されているのが確認できます。お疲れ様でした。

あわせて読みたい