[爆卦] 電腦科學家證明MIP*=RE

看板Gossiping作者 (jack)時間4年前 (2020/03/06 22:03), 4年前編輯推噓240(253推 13噓 58→)
留言324則, 297人參與, 4年前最新討論串1/4 (看更多)
https://arxiv.org/pdf/2001.04383.pdf 五位學者發表了標題為MIP*=RE的論文.從計算複雜性的角度來說,等式被證明成立也表示 我們能用多方量子交互式證明來驗證圖靈停機問題.可說是計算複雜性理論四十多年來最 為深刻的結果之一 多方量子交互式證明系統(MIP*) 學過貝爾不等式就知道兩方的量子相關 (quantum correlation)能取到古典相關取不到的 值.若從交互式證明的角度來看,糾纏的兩方對應兩個玩家(即證明者),量子相關中的局部 可觀測量可以看成兩個玩家對裁判(即驗證者)提出的問題所採取的的策略,而且玩家和裁 判之間的通信是古典的.這樣的non-local game就是一個MIP*協議 遞迴可列舉/圖靈可識別語言(RE) 任何算法都可以寫成一個圖靈機.那麼要怎麼判斷一個圖靈機能否停機呢?一種方法是先看 看一步時會不會停,再看兩步時會不會停,以此類推,如果圖靈機能停機,那麼總有一步會停 下來.當然也可能停不下來,這樣一步一步嘗試的過程對應的複雜度就是RE MIP*=RE的意義 1.否定Tsirelson問題 前面的non-local games中,把貝爾不等式中的情形一般化得到的是張量積模型,也就是說 兩個玩家的量子策略分別作用於自己拿到的那部分糾纏態所在的量子位元,以及自己手上 的量子位元.但是也可以考慮另一種一般化-即兩個玩家除了自己手上的量子位元外還有一 部分量子位元是公共的,他們的策略可以作用在公共部分和自己的部分上,而且兩個玩家 選取不同策略的順序不會影響結果 (即對易),這稱作對易算符模型 Boris Tsirelson在1980年代問了一個問題:張量積模型和對易算符模型定義的非局域性 (non-locality)是否等價? 這篇論文給出了反例:存在一個non-local game,它在對易算符模型下的最優獲勝概率是1, 但是在張量積模型下的最優獲勝概率至多是1/2. 2.推翻 Connes 嵌入猜想 從算子代數的角度說,等式推翻了Connes嵌入猜想,該猜想由菲爾茲獎得主Alain Connes提 出:對於具有無限多個可測量變量量子系統,是否可以通過具有有限數量的簡單系統近似？ 對物理學家來說,這表示兩個曾被認為是等價的獨立數學對象在解釋測量糾纏系統時,實際 上是不等價的,某些從無限到有限的近似也將不再像物理學家曾經設想的那樣奏效 證明過程 如果把求解張量積模型的non-local games的最大獲勝概率的圖靈機寫成一個non-local game並不斷應用間隙不變壓縮技術的話.如果圖靈機停機,則最大獲勝概率是1;如果圖靈機 不停機,則最大獲勝概率不超過1/2.這就證明了MIP*的RE下界,而且MIP*的平凡上界也是RE (因為列舉玩家間共享的糾纏態的維度),從而導出 MIP*=RE 此外為了給出Tsirelson問題的否定回答.必須考慮對易算符模型下的non-local game的SDP hierarchy,即通過逐漸增加玩家們共享的糾纏態維度來判斷最大獲勝概率是不是小於1.把 求解這個SDP hierarchy的圖靈機用上述間隙不變壓縮技術不斷壓縮,如果這個圖靈機不會 停機,那麼得到的non-local game在對易算符模型下的最大獲勝概率是1,但是在張量積模型 下的最大獲勝概率不超過1/2(否則需要兩個玩家之間共享無窮維度糾纏) -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.192.157.138 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1583503398.A.94A.html
推
03/06 22:03, 4年前 , 1F
快推以免被發現我看不懂
03/06 22:03, 1F
推
03/06 22:03, 4年前 , 2F
？
03/06 22:03, 2F
→
03/06 22:03, 4年前 , 3F
嗯嗯！！樓下也想到了
03/06 22:03, 3F
推
03/06 22:03, 4年前 , 4F
恩 好喔
03/06 22:03, 4F
推
03/06 22:03, 4年前 , 5F
恩恩 和我上禮拜推導的結果差不多
03/06 22:03, 5F
推
03/06 22:03, 4年前 , 6F
跟我想的差不多 給推
03/06 22:03, 6F
推
03/06 22:03, 4年前 , 7F
嗯嗯我也是這樣想
03/06 22:03, 7F
推
03/06 22:03, 4年前 , 8F
嗯 跟我想的一樣
03/06 22:03, 8F
→
03/06 22:04, 4年前 , 9F
恩恩 Imotucc也是這樣想
03/06 22:04, 9F
推
03/06 22:04, 4年前 , 10F
是不是偷看我的筆記本啊
03/06 22:04, 10F
→
03/06 22:04, 4年前 , 11F
唉..明明中文比較多 沒有一句看得懂
03/06 22:04, 11F
噓
03/06 22:04, 4年前 , 12F
可憐
03/06 22:04, 12F
噓
03/06 22:05, 4年前 , 13F
沒人在意
03/06 22:05, 13F
推
03/06 22:05, 4年前 , 14F
可惜我的筆記本已經寫不下了.....
03/06 22:05, 14F
推
03/06 22:05, 4年前 , 15F
Baum–Connes conjecture是錯的???
03/06 22:05, 15F
推
03/06 22:06, 4年前 , 16F
恩恩，之前就猜到了，只是沒寫下來
03/06 22:06, 16F
推
03/06 22:06, 4年前 , 17F
...
03/06 22:06, 17F
推
03/06 22:07, 4年前 , 18F
我大便就有猜想了
03/06 22:07, 18F
推
03/06 22:07, 4年前 , 19F
我以為大家都知道
03/06 22:07, 19F
推
03/06 22:07, 4年前 , 20F
跟我想得差不多
03/06 22:07, 20F
推
03/06 22:07, 4年前 , 21F
P≠NP？
03/06 22:07, 21F
→
03/06 22:07, 4年前 , 22F
P-NP問題解決了叫我
03/06 22:07, 22F
推
03/06 22:08, 4年前 , 23F
所以能幹麼?
03/06 22:08, 23F
→
03/06 22:08, 4年前 , 24F
其實差不多 只是有幾句表達可以更白點 讓
03/06 22:08, 24F
→
03/06 22:08, 4年前 , 25F
更多人懂更好
03/06 22:08, 25F
推
03/06 22:08, 4年前 , 26F
.................
03/06 22:08, 26F
→
03/06 22:08, 4年前 , 27F
好複雜
03/06 22:08, 27F
推
03/06 22:08, 4年前 , 28F
我的研究被搶發了
03/06 22:08, 28F
推
03/06 22:08, 4年前 , 29F
土條一定早就想過這個了
03/06 22:08, 29F
推
03/06 22:09, 4年前 , 30F
恩恩 果然跟我之前想的一樣
03/06 22:09, 30F
推
03/06 22:09, 4年前 , 31F
沒有我的參與還是證明出來了嗎...
03/06 22:09, 31F
→
03/06 22:09, 4年前 , 32F
真廢 之前我早寫出來 只是紙不夠長
03/06 22:09, 32F
推
03/06 22:09, 4年前 , 33F
其實理論是錯的 但打字太麻煩了我不打
03/06 22:09, 33F
→
03/06 22:10, 4年前 , 34F
我只知道PV=nRT
03/06 22:10, 34F
→
03/06 22:11, 4年前 , 35F
哩共蝦
03/06 22:11, 35F
推
03/06 22:11, 4年前 , 36F
公鯊小啦，不就銅板人頭或字最大2分之一
03/06 22:11, 36F
推
03/06 22:11, 4年前 , 37F
沒錯我就知道是這樣
03/06 22:11, 37F
推
03/06 22:12, 4年前 , 38F
嗯 看不懂
03/06 22:12, 38F
推
03/06 22:13, 4年前 , 39F
沒錯，果然如此 嗯嗯
03/06 22:13, 39F
還有 246 則推文
還有 1 段內文
推
03/07 08:08, 4年前 , 286F
看不懂……應該正常吧…
03/07 08:08, 286F
推
03/07 08:12, 4年前 , 287F
我以為大家都知道的說
03/07 08:12, 287F
推
03/07 08:13, 4年前 , 288F
嗯嗯我也是這麼想的
03/07 08:13, 288F
推
03/07 08:20, 4年前 , 289F
我有更簡單的證明，可是推文寫不下
03/07 08:20, 289F
推
03/07 08:39, 4年前 , 290F
不懂
03/07 08:39, 290F
→
03/07 08:46, 4年前 , 291F
推，我早就覺得是這樣
03/07 08:46, 291F
※ 編輯: jackliao1990 (123.192.157.138 臺灣), 03/07/2020 08:47:41
推
03/07 09:29, 4年前 , 292F
這是中文我怎麼看不懂
03/07 09:29, 292F
推
03/07 09:43, 4年前 , 293F
早就知道是這樣
03/07 09:43, 293F
推
03/07 09:53, 4年前 , 294F
講中文
03/07 09:53, 294F
推
03/07 10:01, 4年前 , 295F
嗯 我也曾經想過 如今得到驗證
03/07 10:01, 295F
推
03/07 10:06, 4年前 , 296F
推翻 Connes 嵌入猜想這件事情比較大條
03/07 10:06, 296F
→
03/07 10:07, 4年前 , 297F
，近似法被受限的消息對於理論物理不是
03/07 10:07, 297F
→
03/07 10:07, 4年前 , 298F
好事情
03/07 10:07, 298F
推
03/07 10:10, 4年前 , 299F
放八卦幹啥呢
03/07 10:10, 299F
噓
03/07 10:21, 4年前 , 300F
你中文有夠爛
03/07 10:21, 300F
推
03/07 10:33, 4年前 , 301F
跟我想的差不多
03/07 10:33, 301F
推
03/07 10:43, 4年前 , 302F
跟我想的差不多
03/07 10:43, 302F
推
03/07 10:47, 4年前 , 303F
我早就知道了
03/07 10:47, 303F
推
03/07 10:53, 4年前 , 304F
哈 我也這麼覺得
03/07 10:53, 304F
推
03/07 11:42, 4年前 , 305F
這是中文？
03/07 11:42, 305F
推
03/07 12:36, 4年前 , 306F
沒一句看得懂==
03/07 12:36, 306F
推
03/07 13:06, 4年前 , 307F
我高中上音樂就想到了 太廢不想發
03/07 13:06, 307F
推
03/07 13:33, 4年前 , 308F
推
03/07 13:33, 308F
→
03/07 13:47, 4年前 , 309F
你lag了哦
03/07 13:47, 309F
噓
03/07 14:05, 4年前 , 310F
寫英文好嗎？ 中文看不懂
03/07 14:05, 310F
推
03/07 14:30, 4年前 , 311F
"演"算法，甚麼算法 支那用語
03/07 14:30, 311F
→
03/07 15:12, 4年前 , 312F
看不懂
03/07 15:12, 312F
推
03/07 15:14, 4年前 , 313F
確實是這樣
03/07 15:14, 313F
推
03/07 15:15, 4年前 , 314F
嗯 跟我想的一樣
03/07 15:15, 314F
推
03/07 15:29, 4年前 , 315F
你講的是中文嗎
03/07 15:29, 315F
推
03/07 17:14, 4年前 , 316F
論文本來想寫這個的，但太簡單被教授打槍
03/07 17:14, 316F
推
03/07 17:29, 4年前 , 317F
太多專有名詞了,這樣寫鄉民怎麼看得懂
03/07 17:29, 317F
噓
03/07 18:47, 4年前 , 318F
記者怎麼不抄這個呢
03/07 18:47, 318F
推
03/07 21:15, 4年前 , 319F
重開機XD
03/07 21:15, 319F
推
03/07 23:17, 4年前 , 320F
講人話
03/07 23:17, 320F
推
03/08 00:21, 4年前 , 321F
嗯嗯，我認同這篇文章 （字看得懂，連起
03/08 00:21, 321F
推
03/08 00:21, 4年前 , 322F
來不認得）
03/08 00:21, 322F
推
03/08 02:49, 4年前 , 323F
呀巴哩…
03/08 02:49, 323F
推
03/08 14:34, 4年前 , 324F
輕鬆啊
03/08 14:34, 324F
‣ 更多 jackliao1990 的文章
文章代碼(AID): #1UObWcbA (Gossiping)
‣ 更多 jackliao1990 的文章
文章代碼(AID): #1UObWcbA (Gossiping)