看板 Gossiping作者 jackliao1990 (jack)標題 [爆卦] 電腦科學家證明MIP*=RE時間 Fri Mar 6 22:03:13 2020
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 (臺灣)
※ 文章代碼(AID): #1UObWcbA (Gossiping)
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1583503398.A.94A.html
推 XXXXHAY: 快推以免被發現我看不懂1F 39.9.232.153 台灣 03/06 22:03
推 rogerno1: ？2F 118.166.7.228 台灣 03/06 22:03
→ pinhanpaul: 嗯嗯！！樓下也想到了3F 211.76.54.132 台灣 03/06 22:03
推 laughing: 恩 好喔4F 220.129.48.39 台灣 03/06 22:03
推 kuochuwon: 恩恩 和我上禮拜推導的結果差不多5F 175.181.152.253 台灣 03/06 22:03
推 pouttuiqoy: 跟我想的差不多 給推6F 42.74.239.252 台灣 03/06 22:03
推 as8644731: 嗯嗯我也是這樣想7F 223.139.107.143 台灣 03/06 22:03
推 joumay: 嗯 跟我想的一樣8F 114.24.2.231 台灣 03/06 22:03
→ Imotucc: 恩恩 Imotucc也是這樣想9F 140.112.245.226 台灣 03/06 22:04
推 Matz: 是不是偷看我的筆記本啊10F 122.116.159.149 台灣 03/06 22:04
→ louic: 唉..明明中文比較多 沒有一句看得懂11F 1.170.41.116 台灣 03/06 22:04
噓 XXXXLINDA: 可憐12F 223.138.104.248 台灣 03/06 22:04
噓 deepdish: 沒人在意13F 220.134.89.190 台灣 03/06 22:05
推 kd1523: 可惜我的筆記本已經寫不下了.....14F 112.104.107.177 台灣 03/06 22:05
推 b10485762000: Baum–Connes conjecture是錯的???15F 36.230.69.2 台灣 03/06 22:05
推 rhox: 恩恩，之前就猜到了，只是沒寫下來16F 111.240.87.64 台灣 03/06 22:06
推 b389b1c: ...17F 111.82.39.161 台灣 03/06 22:06
推 AlianF: 我大便就有猜想了18F 101.136.213.152 台灣 03/06 22:07
推 em4: 我以為大家都知道19F 110.26.126.213 台灣 03/06 22:07
推 b10213044: 跟我想得差不多20F 61.231.245.52 台灣 03/06 22:07
推 bye2007: P≠NP？21F 111.83.138.44 台灣 03/06 22:07
→ ykes60513: P-NP問題解決了叫我22F 173.251.98.246 美國 03/06 22:07
推 purplebfly: 所以能幹麼?23F 36.227.17.86 台灣 03/06 22:08
→ wintxa: 其實差不多 只是有幾句表達可以更白點 讓更多人懂更好24F 101.12.66.86 台灣 03/06 22:08
推 DM1984: .................26F 101.8.205.91 台灣 03/06 22:08
推 djyunjie: 我的研究被搶發了28F 125.230.23.118 台灣 03/06 22:08
推 mig: 土條一定早就想過這個了29F 180.177.109.41 台灣 03/06 22:08
推 Kao0502: 恩恩 果然跟我之前想的一樣30F 140.112.240.247 台灣 03/06 22:09
推 aggressorX: 沒有我的參與還是證明出來了嗎...31F 36.231.41.213 台灣 03/06 22:09
→ minicoke: 真廢 之前我早寫出來 只是紙不夠長32F 101.137.48.109 台灣 03/06 22:09
推 Gigo0419: 其實理論是錯的 但打字太麻煩了我不打33F 46.125.250.57 奧地利 03/06 22:09
→ tananadishow: 我只知道PV=nRT34F 223.141.113.241 台灣 03/06 22:10
→ kaodio: 哩共蝦35F 114.43.86.64 台灣 03/06 22:11
推 dear0106: 公鯊小啦，不就銅板人頭或字最大2分之一36F 36.239.108.190 台灣 03/06 22:11
推 panda04056: 沒錯我就知道是這樣37F 1.162.44.194 台灣 03/06 22:11
推 Mihoko927: 嗯 看不懂38F 114.47.0.81 台灣 03/06 22:12
推 as6633208: 沒錯，果然如此 嗯嗯39F 123.241.176.171 台灣 03/06 22:13
推 chucky: 跟我想的差不多40F 180.217.147.176 台灣 03/06 22:13
推 Bigbotin: 公鯊小....41F 122.121.105.230 台灣 03/06 22:13
推 sasa789: 跟我推算的結果差不多42F 114.27.106.63 台灣 03/06 22:13
推 sushi11: 跟我想的一樣43F 101.13.208.56 台灣 03/06 22:13
推 Peurintesa: 演算法菜雞請問這是一種NPC問題嗎==44F 1.165.164.219 台灣 03/06 22:14
推 qscgg: 我比較想知道你是真的懂還是覺得很厲害就貼46F 114.26.152.206 台灣 03/06 22:15
推 furnaceh: 我也是這樣想的47F 123.195.193.78 台灣 03/06 22:15
推 mingyu608: 嗯嗯 沒錯48F 39.9.44.127 台灣 03/06 22:15
推 Bansar: 我早就知道了49F 114.136.141.173 台灣 03/06 22:15
推 fyer: 畢業論文原本想做這個 可惜我是商科的= =50F 223.138.131.214 台灣 03/06 22:16
→ sowbm: ....對不起，我不懂51F 111.241.153.100 台灣 03/06 22:16
推 highwayshih: 跟我想的差不多 可惜沒空整理成論文52F 118.160.13.116 台灣 03/06 22:16
推 zxcasd848: 對不起 我拉低八掛板的素質了53F 1.200.51.60 台灣 03/06 22:16
推 sa0124: 就是在探討 張量積模型和對易算符模型定義的非局域性嘛54F 223.140.200.233 台灣 03/06 22:17
推 upeo: 優文56F 101.137.133.110 台灣 03/06 22:17
→ tw15: 嗯嗯我也是這樣想57F 219.71.91.194 台灣 03/06 22:17
推 animad: 跟我想的一樣58F 36.228.11.109 台灣 03/06 22:17
推 brad001: 跟我想的差不多 不錯59F 223.139.151.16 台灣 03/06 22:18
推 mack860120: 跟我想的一樣 推文寫不下而已60F 114.26.45.241 台灣 03/06 22:18
推 wahaha99: 看不懂給推61F 1.171.153.222 台灣 03/06 22:18
推 CostDown: 靠爸 這問題上面就有六十幾個鄉民都會62F 111.71.58.153 台灣 03/06 22:18
→ venomsoul: 等等，我到底要修科學還是國文才能懂63F 122.118.110.60 台灣 03/06 22:19
推 ohkokusa: 果然跟我想的一樣阿64F 101.8.211.248 台灣 03/06 22:19
→ henryyeh5566: 所以解決了PPAP問題了沒65F 61.223.16.149 台灣 03/06 22:19
推 upeo: 倒是很好奇 量子電腦的理論還在建立 怎麼就66F 101.137.133.110 台灣 03/06 22:19
推 paulabxz123: 樓下聽說你是甲甲 你覺得呢67F 42.73.66.218 台灣 03/06 22:19
→ upeo: 有實體出來？難道是逆向工程？68F 101.137.133.110 台灣 03/06 22:20
推 zaqimon: 所以哪支股票會漲？69F 219.91.9.86 台灣 03/06 22:20
推 panda816: 嗯嗯 跟我想的差不多70F 42.74.74.183 台灣 03/06 22:20
推 williamshia: 說中文好嗎 喔原來已經是中文了72F 1.172.145.237 台灣 03/06 22:21
→ cool911234: 3.7d re73F 101.14.160.40 台灣 03/06 22:21
推 gink: 嗯嗯，上次我也這麼說的74F 49.216.100.160 台灣 03/06 22:22
推 moonlind: 說中文75F 111.254.38.203 台灣 03/06 22:22
推 newti: 完全看不懂.....76F 114.137.206.151 台灣 03/06 22:22
推 frank72: 差不多結論 嗯77F 36.229.197.251 台灣 03/06 22:22
推 jej: 記者專業一點好嗎？ 看不下去了78F 223.137.50.199 台灣 03/06 22:23
推 proprome: 恩恩 果然跟我想的一樣79F 49.215.193.69 台灣 03/06 22:23
推 iuus: 跟我推的差不多80F 180.204.140.8 台灣 03/06 22:24
→ bodielu …
推 bodielu: 我之前不是說過了嗎81F 180.204.36.12 台灣 03/06 22:25
→ klm619: 3.7d -re82F 114.45.10.109 台灣 03/06 22:25
推 hirobumi: 跟我想的差不多麻83F 223.137.103.30 台灣 03/06 22:26
推 NewShiisDog: 大發現欸 太了不起了 謝謝你讓我學到了一課84F 180.217.195.248 台灣 03/06 22:26
推 ethan30213: 我不是說過了嗎86F 36.235.231.214 台灣 03/06 22:26
推 goldflower: 看不懂= =87F 49.214.162.197 台灣 03/06 22:26
→ eeccms …
推 eeccms: 跟我想的大致一樣88F 36.226.125.253 台灣 03/06 22:26
噓 benptt: 跟我的論文一樣，我自己都看不懂~89F 39.12.161.90 台灣 03/06 22:27
推 vehuo: 恩啊90F 125.224.98.175 台灣 03/06 22:27
推 lmf770410: 嗯嗯跟我想的一樣91F 223.137.224.45 台灣 03/06 22:27
推 xm3k0828: 我昨天才跟我爸分享我的成果92F 36.229.222.142 台灣 03/06 22:28
推 william806: 終於等到我的想法被證實的這天93F 39.13.100.188 台灣 03/06 22:30
推 dcoog7880: XD94F 114.137.234.73 台灣 03/06 22:32
推 Daface: 跟我想的一樣 差不多95F 36.229.83.21 台灣 03/06 22:35
推 CCMg: 我國小大便的時候就推出來了96F 42.77.142.237 台灣 03/06 22:36
推 WLR: 跨隆謀97F 59.127.250.13 台灣 03/06 22:36
推 supdoraking: 我早就想到超好的證明 只是筆記本寫98F 1.160.38.177 台灣 03/06 22:37
推 g5978gyy: 那有試過先重開機了嗎99F 223.137.4.156 台灣 03/06 22:37
推 a26515969: 沒一句看得懂==306F 49.216.100.31 台灣 03/07 12:36
推 southright: 我高中上音樂就想到了 太廢不想發307F 73.183.157.2 美國 03/07 13:06
推 lin212324: 推308F 42.74.144.30 台灣 03/07 13:33
→ nature1: 你lag了哦309F 42.77.245.96 台灣 03/07 13:47
噓 henry7448: 寫英文好嗎？ 中文看不懂310F 31.205.21.28 英國 03/07 14:05
--