20190806：量子アニーリング 組み合わせ最適化処理の高速化、高度化を目指して

GRIPSで開催されたNPO法人ナレッジプールのオープンセミナーに参加。

内容は早稲田　田中宗先生の「量子アニーリング　組み合わせ最適化処理の高速化、高度化を目指して」

【概要】

• 組合せ最適化問題を高速・高精度に処理することが重要。
• 量子アニーリングをはじめとしたイジングマシンが世界各地で開発されている。
• イジングマシンとは自然現象に着想を得た計算原理に基づく計算ハードウェア
• ハードウェアだけでなくソフトウェア・アプリケーションの探索といった様々なレイヤの協力連携が不可欠。

【量子コンピューティングの超概要】

• ゲート式量子コンピュータは1990年代から知られていて、暗号の元となる素因数分解を高速に解く計算原理が提案された。SFの観点からも注目を集めた。
• アルゴリズムはできるが、実際のマシンを作ることが極めて難しいのが問題だった。難しいけれど出来たら凄いというものだった。
• 素因数分解だけでなく、様々なアルゴリズムが知られている。現在でも活発に探索が進んでいる。
• IBM、googleなど巨大IT企業やスタートアップ企業がハードウェア開発を活発にしている。
• 量子アニーリングは組み合わせ最適化問題（膨大な選択肢から制約をみたしてベストな選択肢を見つけること）に特化したコンピュータ
• 1998年に理論物理学者が理論的提案をし、2011年にカナダのD-Waveがハードウェア化して発売された。3m四方の箱の中に冷却装置が何重にも入っていて、最も奥に小指の先ほどの大きさのチップがある。温度は-273℃で冷却されている。
• 超電導を使った量子ビットを使っているので、冷やさないといけない。NECがもともと作った技術。今は色んな会社が作っている。AIや材料シミュレーションにも応用を検討されている。

【組合せ最適化問題】

• 組合せ最適化問題とは、制約条件を満たしている中でベストな解を探す必要のある問題のこと。
• 巡回セールスマン問題：訪問すべき場所がn箇所あって、全ての箇所を1回は行かなくてはならないという制約がある。その中で、コスト最小の巡回ルートを探索する。
• シフト表作成問題：各自の出勤時間帯の都合・労基法律遵守の制約の中で、混む時間には店員を多めに配置して処理を回すなどのパフォーマンスを最大化させる。
• 配送計画問題：配送先・配送時間の指定・生鮮品なら冷蔵対応などの制約のもとで、どのトラックにどの荷物を載せてどのタイミングで配送するかという問題。
• 選択肢が激増するため、関与する要素の数が増える。困難さを「組合せ爆発」と呼ぶ。
• ベストが良いが、ベターでも良いという考えもある。精度の高いベターな解を高速に得る計算技術ニーズも向上している。ザ・ベストを求めるのではなく、ベターの中でも結構高いベターを求める。
• 組み合わせ問題自体は昔からあったが、データがたくさんあってサイバー空間で処理する時代になった。これまで組合せ最適化問題として見ていなかった問題が顕在化してきた。今ある問題を解くだけでなく、さまざまなデータが取れるようになったことで、組合せ最適化問題が顕在化してきた。
• ビジネスで使おうというスタンスが重要。技術を1から100まで知らなければ問題が解けないというわけではない。どういうところにビジネス課題があるのか、それを着実に取り組んで出していく。
• 高速道路の動画を見ていても、至る所に解かなくてはいけない問題が見える。渋滞解消問題や、渋滞があっても荷物を時間どおりに届ける最適効率配送ルート探索、ガソリンスタンドの出店計画などもあるだろう。
• 「こういう問題を解いたら面白いのではないか？」という企業からの提案
• デジタル広告配信最適化はいつ、誰に、何を届けるか？ユーザーとクライアントにとって最適化させる。
• ネットワーク構造の分析：着目する構造の一部が入っているかどうかの確認　化学結合のパターンがふくまれているかどうか。異常回路の検知など
• マルチモーダル交通システム：経路と使うモビリティの探索

【イジングマシンの計算原理と使い方】

• ちなみにイジングとは人の名前を取っている。意味はない。
• 自然現象を用いた（模倣した）計算で「エネルギーの低い状態＝安定状態」という物理の原理を用いている。組合せ最適化問題はコストが低い解を探すので、最もエネルギーは低い状態を探索する。イジングモデルの規定状態＝組み合わせ問題の最適解
• 組合せ最適化問題はF(x)の中で最も低いところの座標を求める問題。F(x)の全景を見ることはできない状況で、入力に対して出力を答えてくれる。最小値を探そうとしても、関数の形によって、最小化ではなくて極小化に落ち着いてしまうこともある。そのときに、ときどき上昇することも許可して探索させてやると、最小点にたどり着ける。たまに上に行くのを許すのがイジングマシン。
• 社会課題から組み合わせ問題に持っていき、機械に入力すれば勝手に答えを出してくれる。
• 金融業界のポートフォリオ最適化問題・オンライン広告最適化と同じ。リスク分散と利益率の最大化。
• マテリアルデザインでは、合成技術が発達してナノ構造を容易に作ることができるようになった。計算側は負荷がでかい。どの元素を、どの割合で混ぜて、どのような構造にすればよいか？を計算する。賢くどの構造をすれば良いですよと教えてくれるシミュレーターが必要とされている。
• 何か既存の計算機を置き換えることはとても大変。大学の研究者はコスト感覚を考えなくても良い立場であるが、新しいシミュレータが提案されたとしてもすぐに乗り込める人もあれば、乗り込めない人も多い。今あるものを置き換える人はいない。
• フォルクスワーゲンは北京市内と空港を結ぶルートが渋滞していることから、混雑度合いを減らす組み合わせ問題を解いてみせた。スマート工場内の無人走行車のルート提案にもつながるアイディア。
• 新しい計算は使ってなんぼ。新しいものは良いものという先入観がある。実はそうではない。既存技術の延長線上にあるものは新しいものが良いものだが、別ベクトルのものは良いものとは限らない。