「量子」と組合せ最適化に関する怪しい言説 ―とある研究者の小言― - むしゃくしゃしてやった，今は反省している日記

最近，量子コンピュータの話題をニュースや新聞で見かけることが増えてきました． その中で気になってきたのが，組合せ最適化と量子コンピュータ（特に量子アニーリング）に関する怪しい言説．私自身は（古典コンピュータでの）組合せ最適化の研究をやってきて，量子コンピュータを研究しているわけではないのですが，さすがにこれはちょっと・・・と思う言説を何回か見かけてきました． 最近の「量子」に対する過熱ぶりは凄まじいので，こういう怪しい言説が広まるのは困りものです．すでにTwitter上には，“組合せ最適化は今のコンピュータでは解けない”とか“でも量子なら一瞬で解ける”という勘違いをしてしまっている人が多数見られます*1． さすがに危機感を覚えてきたので，この場できちんと指摘しておくことにしました． 今北産業(TL;DR) “古典コンピュータは組合せ最適化を解けない” → 古典コンピュータで組合せ最適化を解

[Ho-oTo]

量子アニーリングを言い出したのが日本人だったせいで日本企業が変にアニーリング大好きになってしまって、真に重要な「普通の」量子コンピュータに使うべきリソースが奪われている、というのが外野から見た印象だが

[Sephy]

たしかになんちゃって解説が多いね。IBM Q Experienceが登場したころに少し触ったけど一意の答えを求めて喜ぶものじゃなくて、時間や環境変数に左右される問題の予測、つまるところ確率を求める道具なんだなと感じた

[rgfx]

ありがてえ。。

[peketamin]

“GoogleマップやYahoo!路線検索は，日々大量の経路探索問題をまさに「実用レベル」で解いていると思うのですが，その辺はどう考えているのでしょう？” それです！

[mbr]

「論文ではかなり冷静に量子アニーリングの課題と現状評価を行っているのに，プレスリリースや動画ではそういう面がバッサリ削られてしまった」のが個人的にはツボだった。とりあえず論文はまともっぽくて良かった。

[fujixe]

量子アニーリング法（というアルゴリズム）と、量子アニーラの現時点での力量は区別すべき。D-Waveだって量子ビット数が数千程度で結合も大したことないんだから、そりゃ実用は無理ってもんだよ。

[gfx]

"個人的に一番イヤなのが「量子じゃないと組合せ最適化は解けない」というデマが広まることです"

[urandom]

成熟する前に株価対策のバズワードとして広まってしまった技術ではありがち。大学の研究者まで資金調達の便法として乗っかったりしてさらにカオスに。

[kota2009]

良い記事。古くはファジー理論、最近だとAIなどと同じで、新技術への期待感を煽る上で旧技術をディスるのは定番論法。視聴者は必殺技が好きだからね。分かり易いし。日本政府は量子技術に注力しているので要注意。

[ghrn]

国内のは量子とは言って無くて、ただのアニーリングHW。それと解説記事を混ぜて量子を主張していると誤読して揚げ足取ってるだけにも見える。量子アニーリングHWはスケールこれからだけど、ノイズが大きな壁。

[maghrib]

“Held-Karpのアルゴリズム”

[coherent_sheaf]

"数十頂点で限界がくるようです"

[kiririmode]

量子アニーリングは厳密解を求めるわけではなくヒューリスティック、有用だが現時点では適用範囲は限られる。TSPでは従来アルゴリズムの方が適用範囲が広そう

[hasiduki]

勉強になる!

[TakayukiN627]

個人的に一番イヤなのが「量子じゃないと組合せ最適化は解けない」というデマが広まることです．

[candidus]

“いち研究者として，組合せ最適化に対するヘンな誤解がこれ以上広まらないことを祈っています”

[itochan]

おお、みごとに騙されてた。買わないから被害はなかった。

[tick2tack]

量子アニーリングはヒューリスティックな解を求めるものなのね。

[filtermap]

MIPソルバー便利ですよ。勤務表自動作成ソフトの試作に利用しました。 https://github.com/filtermap/pulp-scheduling

[medihen]

この手のバズワード・プロレスは、なんらかのベンチマーク・ランキングが出だしてからが本番ではなかろうか。

[northlight]

“近似比保証”

[uzuky]

ディープラーニングでこの流れもうみたというか、既存の製品で十分使えるやつがたくさんあるのに、[2021最新版]みたいなことが書いてあるよくわからないやつ買っちゃうのと同じ構造でしょ

[call_me_nots]

“最も愚直な総当りの計算量O(n!) を示して古典コンピュータの計算量を見積もるのはまったくのガバガバです．他にも分枝限定法などの洗練されたアルゴリズムもあるわけで”

[filinion]

「愚直にやったら8億年かかるだろうが、アルゴリズムを使えばすぐ厳密解が出る」…「フカシギの数え方」で見たやつだ。おねえさぁーん！。／アニーリングの話が多いのは技術的に容易だったからでは。D-WAVEとか。

[uzusayuu]

「古典コンピュータでは厳密解の意味で「解ける」話をしていたはずなのに，この後量子アニーリングの話をするときには，ヒューリスティックの意味で「解ける」にすり替わっているのもかなりミスリーディングです」

[omega314]

ディープラーニングとかいう間違った成功体験があるからなあ。

[fubar_foo]

なるほど、勉強になった。 ところでYahoo!路線は最短経路問題だとしたら組合せ最適と全然違う気がするけど、私の勘違い？

[mkusunok]

量子アニーリングを分かった気になってる人たち、だいぶ危なっかしいとは思っていたけれども、これは良記事。それはそれでこんな可能性はあるんだけどねって補足もあると良かったんだけれど

[takilog]

さすがプロの目線

[ma38su]

全くそう。

[sc3wp06ga]

こんなに

[alyya]

TSPは分かりやすいからよく広告塔になることが多いけど、TSPは特定条件下における二次割当問題（QAP）のうちの１つなので、QAPにもっと注目して欲しい。

[hirakawahanzo]

勉強します

[hiromi_ayase]

量子技術研究開発機構 でググるとわかるけど中身は放射線と核融合研究だったりするので、何でも量子ってつけておけば予算が下りる体制になってしまってる。この界隈、純粋な研究じゃなくてビジネスの世界になってる

[kagioo2uma]

わかりやすい解説。