量子コンピュータって組み合わせ最適化問題解けないらしいな
admin量子コンピュータって組み合わせ最適化問題解けないらしいな
1:風吹けば名無し 2021/11/18(木) 22:52:10.163 ID:7bNTjIWf0
日系大企業が量子コンピュータ使って組み合わせ最適化問題を解決します！とか言ってるけど、あれ嘘なんかな
引用元: https://hebi.5ch.net/test/read.cgi/news4vip/1637243530/
12:風吹けば名無し 2021/11/18(木) 23:00:14.803 ID:7xiyWez60
>>1
普通のノイマン式コンピューターじゃほぼ実用的な期間で解ける可能性が無い
量子コンピューターならば今後ソフトウェア次第では解ける可能性が出てきている
あとは量子コンピューターに最適化されたソフトウェアとハード自体の最適化
普通のノイマン式コンピューターじゃほぼ実用的な期間で解ける可能性が無い
量子コンピューターならば今後ソフトウェア次第では解ける可能性が出てきている
あとは量子コンピューターに最適化されたソフトウェアとハード自体の最適化
14:風吹けば名無し 2021/11/18(木) 23:01:32.838 ID:7bNTjIWf0
>>12
少なくとも組み合わせ最適化問題に関しては量子コンピュータはそんなに得意じゃないらしいぞ
少なくとも組み合わせ最適化問題に関しては量子コンピュータはそんなに得意じゃないらしいぞ
2:風吹けば名無し 2021/11/18(木) 22:52:33.879 ID:wP+jI8mbM
解ける
5:風吹けば名無し 2021/11/18(木) 22:53:26.664 ID:7bNTjIWf0
>>2
解けないらしいぞ
解けないらしいぞ
3:風吹けば名無し 2021/11/18(木) 22:52:34.459 ID:8BIM3VQl0
お姉さんの話思い出した
6:風吹けば名無し 2021/11/18(木) 22:53:57.266 ID:ehtvazC00
>>3
あれなんなんだろうな
あれなんなんだろうな
4:風吹けば名無し 2021/11/18(木) 22:52:46.051 ID:k4291fjH0
DP法！？
7:風吹けば名無し 2021/11/18(木) 22:54:18.546 ID:7bNTjIWf0
>>4
組み合わせ最適化問題解きたかったら、量子コンピュータの専門家に頼むんじゃなくて、組み合わせ最適化問題の専門家に頼むべき
組み合わせ最適化問題解きたかったら、量子コンピュータの専門家に頼むんじゃなくて、組み合わせ最適化問題の専門家に頼むべき
8:風吹けば名無し 2021/11/18(木) 22:55:20.309 ID:7bNTjIWf0
大企業がお客様の組み合わせ最適化問題を量子コンピュータで解決します！とか言ってるけど、あれに相談するとどうなるんだろうな
9:風吹けば名無し 2021/11/18(木) 22:56:49.453 ID:aDlNCjaqa
普通に解けるが
10:風吹けば名無し 2021/11/18(木) 22:57:29.056 ID:7bNTjIWf0
>>9
解けないらしいぞ
10点の巡回セールスマン問題も解けないらしいぞ
解けないらしいぞ
10点の巡回セールスマン問題も解けないらしいぞ
11:風吹けば名無し 2021/11/18(木) 22:58:37.222 ID:aDlNCjaqa
>>10
どこから仕入れた情報かしらんが解けるぞ
量子ゲート式はあんまり向いてないけど
量子アニーリング式なら組み合わせ最適化解決にめちゃくちゃ向いてる
どこから仕入れた情報かしらんが解けるぞ
量子ゲート式はあんまり向いてないけど
量子アニーリング式なら組み合わせ最適化解決にめちゃくちゃ向いてる
13:風吹けば名無し 2021/11/18(木) 23:00:23.006 ID:7bNTjIWf0
>>11
少なくとも巡回セールスマン問題は全然だめらしいぞ
解けるって言うなら例えばどんな問題なら解けるの？
少なくとも巡回セールスマン問題は全然だめらしいぞ
解けるって言うなら例えばどんな問題なら解けるの？
17:風吹けば名無し 2021/11/18(木) 23:04:18.701 ID:aDlNCjaqa
>>13
ああ、たしかに巡回セールスマン問題は向いてないって話題になったな
量子アニーリングは、たとえば電車のダイヤ作成とか渋滞回避みたいな、Aの選択がBにも影響して順序によって最適解が変わるような問題が得意
巡回セールスマンみたいな複数の対象に相互作用の関係がない問題は向いてない
ああ、たしかに巡回セールスマン問題は向いてないって話題になったな
量子アニーリングは、たとえば電車のダイヤ作成とか渋滞回避みたいな、Aの選択がBにも影響して順序によって最適解が変わるような問題が得意
巡回セールスマンみたいな複数の対象に相互作用の関係がない問題は向いてない
20:風吹けば名無し 2021/11/18(木) 23:07:08.571 ID:7bNTjIWf0
>>17
巡回セールスマン問題も順序によって最適解変わるんじゃね？
巡回セールスマン問題も順序によって最適解変わるんじゃね？
15:風吹けば名無し 2021/11/18(木) 23:02:20.127 ID:v4godfX10
へえそうなんだ
16:風吹けば名無し 2021/11/18(木) 23:02:57.847 ID:7bNTjIWf0
>>15
そうらしいぞ
そうらしいぞ
25:風吹けば名無し 2021/11/18(木) 23:10:48.540 ID:v4godfX10
>>16
ちょっとググってみたけど面白いな
量子コンピュータすごいすごいとしか聞かないからこういう何ができないみたいな視点は新鮮
ちょっとググってみたけど面白いな
量子コンピュータすごいすごいとしか聞かないからこういう何ができないみたいな視点は新鮮
28:風吹けば名無し 2021/11/18(木) 23:13:29.591 ID:7bNTjIWf0
>>25
俺も最近知ってびっくりしたわ
日系大企業たちはみんな一生懸命量子アニーリングで組み合わせ最適化問題解けますって言って仕事取ってるみたいだけど、相談に来た企業にどんなコンサルティングしてるんだろうな
俺も最近知ってびっくりしたわ
日系大企業たちはみんな一生懸命量子アニーリングで組み合わせ最適化問題解けますって言って仕事取ってるみたいだけど、相談に来た企業にどんなコンサルティングしてるんだろうな
18:風吹けば名無し 2021/11/18(木) 23:06:45.877 ID:Ac/tZ+bt0
どうしてそういう仕様なのか知らんけどアルゴリズムの問題じゃなくて？
22:風吹けば名無し 2021/11/18(木) 23:08:17.241 ID:7bNTjIWf0
>>18
量子コンピュータで組み合わせ最適化問題が解けますって言ってる企業は大抵、量子アニーリングの話ししてて、その量子アニーリングが組み合わせ最適化問題に向いてない
量子コンピュータで組み合わせ最適化問題が解けますって言ってる企業は大抵、量子アニーリングの話ししてて、その量子アニーリングが組み合わせ最適化問題に向いてない
19:風吹けば名無し 2021/11/18(木) 23:06:58.909 ID:aDlNCjaqa
そもそも巡回セールスマン問題は人間的な思考が必要な
コンピュータにとってはめちゃくちゃ難解な問題なんだけど
組み合わせ最適化の代表的な問題だから例に使われて
何故か「量子コンピュータは組み合わせ最適化に向いてない」って言われてただけだよ
コンピュータにとってはめちゃくちゃ難解な問題なんだけど
組み合わせ最適化の代表的な問題だから例に使われて
何故か「量子コンピュータは組み合わせ最適化に向いてない」って言われてただけだよ
例えるなら中華料理が得意な人が
炒飯を作るのが苦手だって判明したら
中華料理が苦手だとか言われだしたようなもん
23:風吹けば名無し 2021/11/18(木) 23:09:08.888 ID:7bNTjIWf0
>>19
巡回セールスマン問題は人間的思考が必要？
何言ってるの？
巡回セールスマン問題は人間的思考が必要？
何言ってるの？
21:風吹けば名無し 2021/11/18(木) 23:07:31.890 ID:k4291fjH0
LP法使えればいいよ
24:風吹けば名無し 2021/11/18(木) 23:09:47.177 ID:7bNTjIWf0
>>21
線形計画問題はすぐ解けるじゃん
線形計画問題はすぐ解けるじゃん
27:風吹けば名無し 2021/11/18(木) 23:12:40.456 ID:k4291fjH0
>>24
量子コンピュータで解けるの
量子コンピュータで解けるの
30:風吹けば名無し 2021/11/18(木) 23:14:30.004 ID:7bNTjIWf0
>>27
量子コンピュータで解く必要がない
量子コンピュータで解く必要がない
33:風吹けば名無し 2021/11/18(木) 23:18:54.947 ID:k4291fjH0
>>30
解くのに数日かかるMILP問題あるけど
解くのに数日かかるMILP問題あるけど
35:風吹けば名無し 2021/11/18(木) 23:22:55.333 ID:7bNTjIWf0
>>33
離散値の最適解なら…
うーん出来るかも？
離散値の最適解なら…
うーん出来るかも？
36:風吹けば名無し 2021/11/18(木) 23:23:54.878 ID:k4291fjH0
>>35
変数約1億個とか書いてあった
変数約1億個とか書いてあった
37:風吹けば名無し 2021/11/18(木) 23:25:36.061 ID:7bNTjIWf0
>>36
実デバイスだと2000個とかだね
2000個って言っても2000ビットなので、非常に少ない…
実デバイスだと2000個とかだね
2000個って言っても2000ビットなので、非常に少ない…
39:風吹けば名無し 2021/11/18(木) 23:26:40.501 ID:k4291fjH0
>>37
実デバイスってなに
実デバイスってなに
42:風吹けば名無し 2021/11/18(木) 23:28:06.853 ID:7bNTjIWf0
>>39
シミュレーションじゃなくて実際の量子ビットをコントロールするデバイスのこと
シミュレーションじゃなくて実際の量子ビットをコントロールするデバイスのこと
29:風吹けば名無し 2021/11/18(木) 23:13:38.222 ID:DUGVhUJY0
おまえらが何言ってるか全然わからん
31:風吹けば名無し 2021/11/18(木) 23:15:01.980 ID:7bNTjIWf0
>>29
日系大企業が言ってる量子コンピュータは全て誇大広告のガラクタだった…って話ですね
日系大企業が言ってる量子コンピュータは全て誇大広告のガラクタだった…って話ですね
32:風吹けば名無し 2021/11/18(木) 23:17:06.312 ID:aDlNCjaqa
すげー簡単に言うと
量子コンピュータは巡回セールスマン問題みたいな条件が厳密なスタートからゴールまでの完璧な最適解となる組み合わせを導き出せって言われると苦手（というより、別に早くない）なんだけど
量子コンピュータは巡回セールスマン問題みたいな条件が厳密なスタートからゴールまでの完璧な最適解となる組み合わせを導き出せって言われると苦手（というより、別に早くない）なんだけど
例えばタクシーの巡回網みたいな
短期的な（条件が厳しくない）組み合わせの中から交通量とか同時に移動している他のタクシーの情報を組み込んで
その時その時の最適解を導き出すのが得意
34:風吹けば名無し 2021/11/18(木) 23:22:27.551 ID:7bNTjIWf0
>>32
そもそも量子アニーリングは、厳密な最適解も見つけるものではないぞ
苦手というより出来ないが正しい
そもそも量子アニーリングは、厳密な最適解も見つけるものではないぞ
苦手というより出来ないが正しい
そして、量子アニーリングは条件が複数あると厳しくなるから、タクシーの巡回網も難しいと思うよ
38:風吹けば名無し 2021/11/18(木) 23:26:00.537 ID:aDlNCjaqa
>>34
量子アニーリングは複数の作用対象がある問題がめちゃくちゃ得意だから
別に複数条件つけられても早いよ
難しいのは複数解を許さない厳密な条件だよ
量子アニーリングは複数の作用対象がある問題がめちゃくちゃ得意だから
別に複数条件つけられても早いよ
難しいのは複数解を許さない厳密な条件だよ
40:風吹けば名無し 2021/11/18(木) 23:27:31.156 ID:7bNTjIWf0
>>38
メチャクチャ得意ってどのレベルで言ってる？
古典コンピュータのアルゴリズムに勝てるって言ってる？
メチャクチャ得意ってどのレベルで言ってる？
古典コンピュータのアルゴリズムに勝てるって言ってる？
44:風吹けば名無し 2021/11/18(木) 23:28:47.699 ID:aDlNCjaqa
>>40
タクシーの例なら余裕だね
曖昧な、常に変化する選択肢が一番得意だから
タクシーの例なら余裕だね
曖昧な、常に変化する選択肢が一番得意だから
49:風吹けば名無し 2021/11/18(木) 23:32:57.971 ID:7xiyWez60
去年、巡回セールスマン問題に関する新しいアルゴリズムが発表されて
44年ぶりにブレイクスルーが起こるって発表されたじゃないか？
44年ぶりにブレイクスルーが起こるって発表されたじゃないか？
50:風吹けば名無し 2021/11/18(木) 23:34:44.576 ID:7bNTjIWf0
>>49
それ古典のアルゴリズムの話しでしょ
それ古典のアルゴリズムの話しでしょ
51:風吹けば名無し 2021/11/18(木) 23:39:56.049 ID:G5Nq2CSpa
巡回セールスマン問題は出発から終点までの最適解を求める＝総当たりになるから時間がかかるってだけで
例えばセールスマンが5人いて、早いもの勝ちでルートを選んで、他の人に使われたルートは使えないみたいな状態で
次の地点、次の次の地点までの最小コストのルートを選んで
最終的におよそ最適解に近い近似値を導き出す、みたいな実用的な話になると量子コンピュータは早いよ
例えばセールスマンが5人いて、早いもの勝ちでルートを選んで、他の人に使われたルートは使えないみたいな状態で
次の地点、次の次の地点までの最小コストのルートを選んで
最終的におよそ最適解に近い近似値を導き出す、みたいな実用的な話になると量子コンピュータは早いよ
