あらまめ2ch

【RSS】PCメイン記事上ワイド1

量子コンピュータって組み合わせ最適化問題解けないらしいな

2024/06/12

0コメント





1: 2021/11/18(木) 22:52:10.163 ID:7bNTjIWf0.net
日系大企業が量子コンピュータ使って組み合わせ最適化問題を解決します！とか言ってるけど、あれ嘘なんかな



2: 2021/11/18(木) 22:52:33.879 ID:wP+jI8mbM.net
解ける



3: 2021/11/18(木) 22:52:34.459 ID:8BIM3VQl0.net
お姉さんの話思い出した



4: 2021/11/18(木) 22:52:46.051 ID:k4291fjH0.net
DP法！？



5: 2021/11/18(木) 22:53:26.664 ID:7bNTjIWf0.net
>>2
解けないらしいぞ



6: 2021/11/18(木) 22:53:57.266 ID:ehtvazC00.net
>>3
あれなんなんだろうな



7: 2021/11/18(木) 22:54:18.546 ID:7bNTjIWf0.net
>>4
組み合わせ最適化問題解きたかったら、量子コンピュータの専門家に頼むんじゃなくて、組み合わせ最適化問題の専門家に頼むべき



8: 2021/11/18(木) 22:55:20.309 ID:7bNTjIWf0.net
大企業がお客様の組み合わせ最適化問題を量子コンピュータで解決します！とか言ってるけど、あれに相談するとどうなるんだろうな



9: 2021/11/18(木) 22:56:49.453 ID:aDlNCjaqa.net
普通に解けるが



10: 2021/11/18(木) 22:57:29.056 ID:7bNTjIWf0.net
>>9
解けないらしいぞ
10点の巡回セールスマン問題も解けないらしいぞ





11: 2021/11/18(木) 22:58:37.222 ID:aDlNCjaqa.net
>>10
どこから仕入れた情報かしらんが解けるぞ
量子ゲート式はあんまり向いてないけど
量子アニーリング式なら組み合わせ最適化解決にめちゃくちゃ向いてる



12: 2021/11/18(木) 23:00:14.803 ID:7xiyWez60.net
>>1
普通のノイマン式コンピューターじゃほぼ実用的な期間で解ける可能性が無い
量子コンピューターならば今後ソフトウェア次第では解ける可能性が出てきている
あとは量子コンピューターに最適化されたソフトウェアとハード自体の最適化



13: 2021/11/18(木) 23:00:23.006 ID:7bNTjIWf0.net
>>11
少なくとも巡回セールスマン問題は全然だめらしいぞ
解けるって言うなら例えばどんな問題なら解けるの？



14: 2021/11/18(木) 23:01:32.838 ID:7bNTjIWf0.net
>>12
少なくとも組み合わせ最適化問題に関しては量子コンピュータはそんなに得意じゃないらしいぞ



15: 2021/11/18(木) 23:02:20.127 ID:v4godfX10.net
へえそうなんだ



16: 2021/11/18(木) 23:02:57.847 ID:7bNTjIWf0.net
>>15
そうらしいぞ



17: 2021/11/18(木) 23:04:18.701 ID:aDlNCjaqa.net
>>13
ああ、たしかに巡回セールスマン問題は向いてないって話題になったな
量子アニーリングは、たとえば電車のダイヤ作成とか渋滞回避みたいな、Aの選択がBにも影響して順序によって最適解が変わるような問題が得意
巡回セールスマンみたいな複数の対象に相互作用の関係がない問題は向いてない



18: 2021/11/18(木) 23:06:45.877 ID:Ac/tZ+bt0.net
どうしてそういう仕様なのか知らんけどアルゴリズムの問題じゃなくて？



19: 2021/11/18(木) 23:06:58.909 ID:aDlNCjaqa.net
そもそも巡回セールスマン問題は人間的な思考が必要な
コンピュータにとってはめちゃくちゃ難解な問題なんだけど
組み合わせ最適化の代表的な問題だから例に使われて
何故か「量子コンピュータは組み合わせ最適化に向いてない」って言われてただけだよ

例えるなら中華料理が得意な人が
炒飯を作るのが苦手だって判明したら
中華料理が苦手だとか言われだしたようなもん



20: 2021/11/18(木) 23:07:08.571 ID:7bNTjIWf0.net
>>17
巡回セールスマン問題も順序によって最適解変わるんじゃね？



[ad_fluct2]



21: 2021/11/18(木) 23:07:31.890 ID:k4291fjH0.net
LP法使えればいいよ



22: 2021/11/18(木) 23:08:17.241 ID:7bNTjIWf0.net
>>18
量子コンピュータで組み合わせ最適化問題が解けますって言ってる企業は大抵、量子アニーリングの話ししてて、その量子アニーリングが組み合わせ最適化問題に向いてない



23: 2021/11/18(木) 23:09:08.888 ID:7bNTjIWf0.net
>>19
巡回セールスマン問題は人間的思考が必要？
何言ってるの？



24: 2021/11/18(木) 23:09:47.177 ID:7bNTjIWf0.net
>>21
線形計画問題はすぐ解けるじゃん



25: 2021/11/18(木) 23:10:48.540 ID:v4godfX10.net
>>16
ちょっとググってみたけど面白いな
量子コンピュータすごいすごいとしか聞かないからこういう何ができないみたいな視点は新鮮



27: 2021/11/18(木) 23:12:40.456 ID:k4291fjH0.net
>>24
量子コンピュータで解けるの



28: 2021/11/18(木) 23:13:29.591 ID:7bNTjIWf0.net
>>25
俺も最近知ってびっくりしたわ
日系大企業たちはみんな一生懸命量子アニーリングで組み合わせ最適化問題解けますって言って仕事取ってるみたいだけど、相談に来た企業にどんなコンサルティングしてるんだろうな



29: 2021/11/18(木) 23:13:38.222 ID:DUGVhUJY0.net
おまえらが何言ってるか全然わからん



30: 2021/11/18(木) 23:14:30.004 ID:7bNTjIWf0.net
>>27
量子コンピュータで解く必要がない



31: 2021/11/18(木) 23:15:01.980 ID:7bNTjIWf0.net
>>29
日系大企業が言ってる量子コンピュータは全て誇大広告のガラクタだった…って話ですね






32: 2021/11/18(木) 23:17:06.312 ID:aDlNCjaqa.net
すげー簡単に言うと
量子コンピュータは巡回セールスマン問題みたいな条件が厳密なスタートからゴールまでの完璧な最適解となる組み合わせを導き出せって言われると苦手（というより、別に早くない）なんだけど

例えばタクシーの巡回網みたいな
短期的な（条件が厳しくない）組み合わせの中から交通量とか同時に移動している他のタクシーの情報を組み込んで
その時その時の最適解を導き出すのが得意



33: 2021/11/18(木) 23:18:54.947 ID:k4291fjH0.net
>>30
解くのに数日かかるMILP問題あるけど



34: 2021/11/18(木) 23:22:27.551 ID:7bNTjIWf0.net
>>32
そもそも量子アニーリングは、厳密な最適解も見つけるものではないぞ
苦手というより出来ないが正しい

そして、量子アニーリングは条件が複数あると厳しくなるから、タクシーの巡回網も難しいと思うよ



35: 2021/11/18(木) 23:22:55.333 ID:7bNTjIWf0.net
>>33
離散値の最適解なら…
うーん出来るかも？



36: 2021/11/18(木) 23:23:54.878 ID:k4291fjH0.net
>>35
変数約1億個とか書いてあった



37: 2021/11/18(木) 23:25:36.061 ID:7bNTjIWf0.net
>>36
実デバイスだと2000個とかだね
2000個って言っても2000ビットなので、非常に少ない…



38: 2021/11/18(木) 23:26:00.537 ID:aDlNCjaqa.net
>>34
量子アニーリングは複数の作用対象がある問題がめちゃくちゃ得意だから
別に複数条件つけられても早いよ
難しいのは複数解を許さない厳密な条件だよ



39: 2021/11/18(木) 23:26:40.501 ID:k4291fjH0.net
>>37
実デバイスってなに



40: 2021/11/18(木) 23:27:31.156 ID:7bNTjIWf0.net
>>38
メチャクチャ得意ってどのレベルで言ってる？
古典コンピュータのアルゴリズムに勝てるって言ってる？



42: 2021/11/18(木) 23:28:06.853 ID:7bNTjIWf0.net
>>39
シミュレーションじゃなくて実際の量子ビットをコントロールするデバイスのこと



[ad_fluct4][記事中固定リンク4]

44: 2021/11/18(木) 23:28:47.699 ID:aDlNCjaqa.net
>>40
タクシーの例なら余裕だね
曖昧な、常に変化する選択肢が一番得意だから



49: 2021/11/18(木) 23:32:57.971 ID:7xiyWez60.net
去年、巡回セールスマン問題に関する新しいアルゴリズムが発表されて
44年ぶりにブレイクスルーが起こるって発表されたじゃないか？



50: 2021/11/18(木) 23:34:44.576 ID:7bNTjIWf0.net
>>49
それ古典のアルゴリズムの話しでしょ



51: 2021/11/18(木) 23:39:56.049 ID:G5Nq2CSpa.net
巡回セールスマン問題は出発から終点までの最適解を求める＝総当たりになるから時間がかかるってだけで
例えばセールスマンが5人いて、早いもの勝ちでルートを選んで、他の人に使われたルートは使えないみたいな状態で
次の地点、次の次の地点までの最小コストのルートを選んで
最終的におよそ最適解に近い近似値を導き出す、みたいな実用的な話になると量子コンピュータは早いよ



転載元:http://2ch.sc/test/read.cgi/news4vip/1637243530




関連記事