「量子」と組合せ最適化に関する怪しい言説 ―とある研究者の小言―
最近，量子コンピュータの話題をニュースや新聞で見かけることが増えてきました．
その中で気になってきたのが，組合せ最適化と量子コンピュータ（特に量子アニーリング）に関する怪しい言説．私自身は（古典コンピュータでの）組合せ最適化の研究をやってきて，量子コンピュータを研究しているわけではないのですが，さすがにこれはちょっと・・・と思う言説を何回か見かけてきました．
最近の「量子」に対する過熱ぶりは凄まじいので，こういう怪しい言説が広まるのは困りものです．すでにTwitter上には，“組合せ最適化は今のコンピュータでは解けない”とか“でも量子なら一瞬で解ける”という勘違いをしてしまっている人が多数見られます*1．
さすがに危機感を覚えてきたので，この場できちんと指摘しておくことにしました．
今北産業(TL;DR)
- “古典コンピュータは組合せ最適化を解けない” → 古典コンピュータで組合せ最適化を解く方法はちゃんとあります．量子じゃないと解けない訳ではありません．あと，量子アニーリングはヒューリスティクスなので厳密解の意味では解いてません．
- “巡回セールスマン問題(TSP)は古典コンピュータでは時間がかかりすぎて解けないが，量子だと一瞬で解ける” → TSPは組合せ最適化で古くから研究されてきた問題で，比較的大規模でも解ける部類の問題です．古典コンピュータで85,900頂点のTSPの厳密解を求めた記録があります．一方，現在の量子アニーリングは数十頂点で限界が来ます．
怪しい言説① 古典コンピュータでは組合せ最適化問題は解けない/苦手
これは色んな所で見ますね．
量子計算機の活用で頻繁にうたわれるのが、「組み合わせ最適化問題」への適用だ。これは現代コンピューターが苦手とする領域であり、さまざまな条件下で多数の選択肢から最適解を選ぶ問題のことを指す。
（実現迫る“量子コンピューター” 組み合わせ「最適化問題」を解く | 科学技術・大学 ニュース | 日刊工業新聞 電子版より引用．強調は筆者）
まず，一口に組合せ最適化問題が「解ける」と言っても，その意味するところは様々です．
- 厳密解（目的関数が最小/最大の解）が得られる場合（総当り法やGurobi, CPLEXなどの整数計画ソルバーはココ）
- 近似比保証のある解（近似解）が得られる場合（いわゆる近似アルゴリズム）
当たり前ですが，これらは解の保証や計算量が異なります．時間をかけて厳密解が欲しい場合もあれば，それなりの解を高速に求めたい場面もあり，完全にケースバイケース．重要なのは，どの意味で「解ける」と言っているのかということです．たとえば，厳密解法とヒューリスティクスの比較は，出力解の保証が異なるアルゴリズムを比較していることになるので注意が必要です．
量子アニーリングの怪しい言説は，これらの階層の異なる「解ける」概念を混同していることがあります．しかも何故か古典コンピュータの計算量評価がガバガバです．
以下のスライドでは，巡回セールスマン問題(TSP)の解の個数（≒総当り法の計算量）を例示し，組合せ最適化問題は「現代のデジタルコンピュータでは事実上解けない」としています．
（無償公開される、スパコンより高速な「量子ニューラルネットワーク計算機」とは何なのか ～NTT、QNN計算装置実機見学会レポート - PC Watchより引用）
実際には古典コンピュータで厳密解を得られる組合せ最適化問題も数多くあります．しかも，最も愚直な総当りの計算量$O(n!)$を示して古典コンピュータの計算量を見積もるのはまったくのガバガバです．例えば，Held-Karpのアルゴリズムを使うと$O(2^n n^2)$まで落ちます．他にも分枝限定法などの洗練されたアルゴリズムもあるわけで，これらを全て無視して総当りの計算量だけ示すのはいかがなものかと．さらに，古典コンピュータでは厳密解の意味で「解ける」話をしていたはずなのに，この後量子アニーリングの話をするときには，ヒューリスティックの意味で「解ける」にすり替わっているのもかなりミスリーディングですね．
怪しい言説② TSPはスパコンでも時間がかかりすぎて解けないが量子だと一瞬で解ける
どうもこの界隈ではTSPが大人気のようです．
「巡回セールスマン問題」など数々の難問を一瞬で解き性能はスーパーコンピュータの9000兆倍に──。夢の計算機、量子コンピュータの研究が世界で急加速している。IBMとグーグルなどの米国勢は試作機を公開。欧州連合や中国政府も研究開発に巨額を投じている。
（量子超越性、米IT大手が一番乗り競う | 日経クロステック（xTECH）より引用）
現在のコンピュータでは手も足も出ないような，とんでもない難問であると認識されているようですね．
量子アニーリングはD-waveが有名ですが，日本企業もこぞって量子アニーリング*2に参入してます．富士通のデジタルアニーラは，ズバリ「「組合せ最適化問題」を実用レベルで解ける唯一のコンピュータ」だそうです．
「組合せ最適化問題」とはまた大きく出ましたね．たとえばGoogleマップやYahoo!路線検索は，日々大量の経路探索問題をまさに「実用レベル」で解いていると思うのですが，その辺はどう考えているのでしょう？
開発部門のインタビュー記事では，30頂点のTSPはスパコンでも解くのに「8億年かかる」と主張しています．
ここで言う「8億年かかる計算」とは、コンピュータ科学の領域では有名な「巡回セールスマン問題」のことだ。
（中略）
巡回する都市の数が増えると計算対象は指数関数的に増えていき、30都市なら実に1京×1京通り以上の計算が必要になる。これは、1秒間に1京回の演算ができる富士通のスーパーコンピュータでも、8億年かかる計算量である。デジタルアニーラは、こうした1京×1京通り以上もの「組み合わせ最適化問題」を1秒以内に解いてしまうのである。（8億年分の計算を1秒で処理── 量子のパワーをデジタルに転換した 「デジタルアニーラ」の衝撃 - CNET Japanより引用．強調は筆者．）
皮肉なことに，TSPは組合せ最適化の中でも古くから徹底的に研究されている問題で，しかもかなり大規模問題まで解ける問題です．すでに2006年の時点で85,900頂点のTSPインスタンスの厳密解が求められています．さらに近似解まで含めると，1,904,711頂点のTSPインスタンスで，ほぼ最適解（最適値とのギャップが0.0471%以下）が見つかってます．もちろん，量子コンピュータは使っていないはず（たぶん）．
以下の動画では，普通のパソコンで2392頂点のTSPの厳密解を1分もかからず求める様子を見ることが出来ます．実際にルートが求まっていく様子は，なんだか見ていて楽しいですね！
www.youtube.com
お分かりの通り，30頂点のTSPが量子で「解けた」と「衝撃」を受けている場合ではないです．「8億年かかる計算」とは一体．
まぁまぁ，30頂点TSPが8億年というのは話の枕であって，本当は量子アニーリングでもっともっと大規模な問題が解けるんでしょ？と思うことでしょう．ところがどっこい，（デジタルアニーラではなく東芝のマシンですが）実際に試してみたレポートによると，なんと本当に数十頂点で限界がくるようです．
qiita.com
正直，ここまで性能がアレだと普通に量子アニーリングはTSP苦手なのでは？という気がしてきます・・・
怪しい言説③ 量子アニーリングは古典コンピュータより優れた解を高速に求める
世の中，TSPのように知見が豊富な組合せ最適化問題ばかりとは限りません．現実の問題を定式化すると，大抵は汚い制約だらけのゴチャゴチャした最適化問題になります．なので，時にはヒューリスティクスが必要な場面も出てきます．量子アニーリングは（他のアニーリング手法と同様）ヒューリスティクスの一種としては有用です．
ただし，「量子」だからといって古典のアルゴリズムやヒューリスティクスより常に優れているとは限りません．実際の問題例に適用してみて性能評価することが肝要です．ところが，量子アニーリングの怪しい言説には，古典のアルゴリズム・ヒューリスティクスと比較をしておらず，「量子」を使うことが目的になっているとしか思えないものがあります．
特に富士通に恨みがあるわけではないのですが，やたら検索で引っかかるので再びデジタルアニーラの事例．
この事例では，配送経路設計の問題に対して量子アニーリングを使用したようです．まず気になるのが「300万以上のルートのうち、最も物流コストが小さくなるルートを算出します」という部分．そもそも解の個数が100万($10^6$)のオーダーであれば，そもそも総当りが十分可能な規模なのでは？という気がします*3．それを置いても，配送経路設計はオペレーションズ・リサーチの定番といっていい問題で，性能面で優れていない限りわざわざ量子を使う必要があるかは疑問です．残念ながら「従来手法と比較して約2～5％のコスト削減」とあるだけで，詳細は書かれていませんでした．
もちろん，古典アルゴリズムとの比較をきちんと行った研究もあります．こちらは，東北大・デンソーが工場内の配送問題にアニーリングマシンを適用した事例．大学のプレスリリースと立派な動画もありました．
www.tohoku.ac.jp
www.youtube.com
プレスリリースにある元論文を見てみると，量子アニーリングと商用MIPソルバーGurobiとの計算時間の比較のグラフが載っていました．なかなか親切な論文ですね．
（Ohzeki et al., "Control of Automated Guided Vehicles Without Collision by Quantum Annealer and Digital Devices", Front. Comput. Sci., 2019.より引用．縦軸は計算時間，横軸は問題サイズ．赤■と青●がアニーリング，緑△がGurobi．）
あれれ，ごく小規模のインスタンスを除いて，Gurobiのほうが1桁速い！というか，量子アニーリングのプロットはGurobiが余裕で動いている規模よりだいぶ手前で途切れてしまってます．論文によるとTLEしたそうです．いずれにせよ，厳密解法がヒューリスティクスより速く，しかも問題規模でも負けているという不思議な結果に．
他手法との比較結果をきちんと論文に載せて議論しているのは誠実な態度ですし，量子アニーリングの実力を把握する上での実証研究としての価値はあると思います．ただ，MIPソルバーの方が速いのは事実なので，私が工場の担当者なら「量子」じゃなくてもいいやと感じると思いますね．論文ではかなり冷静に量子アニーリングの課題と現状評価を行っているのに，プレスリリースや動画ではそういう面がバッサリ削られてしまった所に，きっと色んな事情があるんだろうなぁ・・・．
もちろん，量子アニーリングでMIPソルバーより高速に良い解が求められる場合も当然あるでしょう．とはいえ，MIPソルバーは厳密アルゴリズムであって，ヒューリスティクスである量子アニーリングとの実行時間を比較すれば，量子アニーリングがそもそも有利です．さらに，MIPソルバーは双対ギャップなど量子アニーリングでは得られない追加的情報も得られる利点があることも注意しておく必要があります．
まとめ
以上，「量子」と組合せ最適化に関する怪しい言説について，ネチネチ「小言」を書いてきました．
繰り返しますが，量子アニーリング自体のヒューリスティクスとしての価値を否定する訳ではないです．もしかすると，ディープラーニングのように，近い将来量子アニーリングが最強ヒューリスティクスとして君臨し，コンテストで上位独占という未来もあるかもしれません．
ただ，現状では量子アニーリングの優位性は明白ではないです．にもかかわらず，古典への優位性を強調したいあまり，ミスリーディングな言説があるのは残念です．また，量子を使うこと自体が目的と化し，「それって本当に量子要ります？」と言いたくなるような，古典的なオペレーションズ・リサーチの問題に適用している事例もあります．*4
個人的に一番イヤなのが「量子じゃないと組合せ最適化は解けない」というデマが広まることです．量子アニーリングは宣伝ほど万能ではない事実に，遅かれ早かれユーザーは気づくはずですが，量子じゃないと組合せ最適化は解けないと思いこまされていると，そこで諦めてしまうのではないかと心配です．もしかしたら普通のコンピュータをちゃんと使えば解けるかもしれないのに！
また，「組合せ最適化は量子で解けるんだから，古典アルゴリズムの研究は時代遅れ」というのも困りものです．上で見たように量子アニーリングはヒューリスティクスに過ぎず，厳密解法の代用にはなりません．また，高速に解ける組合せ最適化問題の探求など，古典アルゴリズムの範囲でもやることはまだまだあります．
最後に，組合せ最適化問題に対する量子アニーリングの性能に関して，NSSOL*5のオペレーションズ・リサーチチームが冷静に分析していたので，紹介します．
私たちも各社の製品を調査しました。各社とも特徴が少しずつ違いますが、特定の問題に絞れば従来の方法に匹敵する性能が出ることもあることがわかりました。ただ組合せ最適化問題全般を解けるわけではなくまだ実用段階ではないと考えています。
（中略）
量子アニーラのツールを否定するわけではないんですが、それも含めていろんなアルゴリズムがあって、それをどういう問題にどう当てるのか、そのノウハウを持っていないと組合せ最適化問題はうまく解けません。（進化する最適化技術 VOL.2～最適化問題を解決に導くNSSOLの技術と実績 －量子アニーリングは万能ではない－～｜TO THE FUTURE｜日鉄ソリューションズより引用．強調は筆者）
さすが，実務と長年真面目に向き合ってきたチームの評価は的確ですね．
いち研究者として，組合せ最適化に対するヘンな誤解がこれ以上広まらないことを祈っています．
*1:巡回セールスマン 量子 - Twitter Searchとかでいくらでも見つかります
*2:正確には，「量子アニーリングに着想を得た」古典アニーリングのマシンを開発している企業が多いようです．だが，組合せ最適化に関して言説が怪しいのは変わらないので，ここではまとめて「量子アニーリング」と呼ぶことにしました．中身が本当の量子効果だろうが何だろうが，エンドユーザーは興味ないでしょうし．
*3:すごく好意的に解釈すると，本当はもっと大量の実行不能解があって，実行可能解だけ数えたら100万のオーダーとかでしょうか？いずれにせよ詳細は不明．
*4:とはいえ，量子がセンセーショナルに登場するまで，古典的な問題ですら社会・企業に認識されてなかった点は，オペレーションズ・リサーチ側の広報の失敗・・・
*5:NSSOLの親会社，日本製鉄はオペレーションズ・リサーチをいち早く導入した企業として知られる
