量子互動式證明可以驗證停機問題嗎?

作者：由 Climber.pI 發表于攝影時間：2019-11-19

在 2020 年 1 月中旬的答案［11］是，我們可以給停機問題（Halting）設計一個

不需要很精確

的多方量子互動式證明（MIP* protocol）。這意味著

${\sf RE} \subseteq {\sf MIP^*}$

，即多方量子互動式證明可以驗證停機問題，以及對 MIP* 的完全刻畫。出人意料的是，這一量子計算複雜性理論的結果也對其他學科有深刻影響

在 2004 年前後，［12，13］分別定義了是用經典通訊和量子通訊的多方互動式證明，即 MIP* 和 QMIP*。時隔十五年後，我們終於得到了 MIP* （以及 QMIP*）的完全刻畫。關於 MIP* 的歷史回顧推薦閱讀 Thomas Vidick 的回憶文章（A Masters project）。

我在另一個回答中寫了關於這個結果的不太長的介紹：如何看待 MIP*=RE？。在這篇文章中我們會涉及更多的技術細節。

目前的答案是，如果有一個

非常精確的

多方量子互動式證明的話，那麼我們可以用多方量子互動式證明來驗證停機問題［3］。除此之外，我們甚至還能找到一個具有完美零知識證明（perfect zero-knowledge proof）性質的量子互動式證明系統［10］。

那麼如果用

正常的

多方量子互動式證明，即要麼玩家們一定獲勝，要麼玩家們獲勝機率小於 1/3），它能夠驗證停機問題（Halting）嗎？

注意到停機問題是

$\mathsf{RE}$

-complete 的（recursively enumerable），這意味我們需要證明

$\mathsf{RE} \subseteq \mathsf{MIP^*}$

。然而這一結果會推翻

運算元代數

中的 Connes‘ embedding conjecture。如果想知道更多細節的話， Thomas Vidick 寫的科普文（

https：//www。

ams。org/journals/notice

s/201910/rnoti-p1618。pdf

）是個很好的介紹。

在本文的剩餘章節，我會分別簡單解釋標題中的 “量子”， “互動式證明” 和 “驗證” 是在說什麼。

下面開始正文，本文亦發表於我的部落格：量子互動式證明可以驗證停機問題嗎？ - Complexity Meets Quantum。

從量子非局域性說起

通常當我們提及量子非局域性的時候，通常都會提及 Bell 不等式。如果用 non-local games 的形式［1］來寫的話，就是

Non-local game.

考慮兩個玩家和一個裁判的 non-local game

，裁判分別把問題

$(s,t)\in S\times T$

發給而玩家甲和乙，甲和乙分別回覆答案

$(a,b)\in A\times B$

，這裡取

$S=T=A=B=\{0,1\}$

，當

$V(a,b|s,t) = (a\oplus b = s\wedge t)$

的時候玩家們獲勝。當然，玩家們和裁判的問答的規模是多項式的。對於裁判和玩家之間的具體問題，玩家們勝利與否用謂詞

$V(a,b|s,t)\in\{0,1\}$

表示。可能的提問

$S\times T$

滿足分佈

$\pi$

。

那麼玩家們的最大獲勝概率刻畫如下：

玩家之間不能共享糾纏：

$\omega_c(G) = \max_{a,b}\sum_{s,t} \pi(s,t) V(a(s),b(t)|s,t)$

。

玩家之間共享糾纏態

$|\psi\rangle$

，玩家甲和玩家乙的策略分別為投影算符集合

$\{ X_s^a \}_{a\in A,s\in S}$

和

$\{Y_t^b\}_{t\in T,b\in B}$

，並且使得

$\sum_a X_s^a = I, \sum_b Y_t^b = I$

：

$w_q(G)=\sum_{(s,t)\in S\times T} \pi(s,t) \sum_{(a,b)\in A\times B} \langle \psi| X_s^a\otimes Y_t^b |\psi\rangle V(a,b|s,t)$

。

對於 CHSH game，不難證明

$\omega_c(G) = \frac{3}{4} < \frac{2+\sqrt{2}}{4} = \omega_q(G)$

。這裡的量子策略的優越性，通常被稱為違反 Bell 不等式。進一步介紹（譬如 selt-testing），見量子 PCP 猜想淺說（二）：量子糾纏的互動式證明驗證。

更一般地，考慮滿足某些結構的

$(|\psi\rangle, \{X_s^a\}_{s\in S, a\in A}, \{Y_t^b\}_{t\in T, b\in B})$

，可以定義對應的量子關聯的集合

$\mathcal{C}_{q}, \mathcal{C}_{qs}, \mathcal{C}_{qa}, \mathcal{C}_{qc}$

：

玩家甲和玩家乙分別有一個有限固定維度的 Hilbert space

$\mathcal{H}_1, \mathcal{H}_2$

，

$\{X_s^a\}, \{Y_t^b\}$

分別定義在

$\mathcal{H}_1, \mathcal{H}_2$

上，

$|\psi\rangle \in \mathcal{H}_1\otimes \mathcal{H}_2$

，那麼這樣的量子關聯的集合記作

$\mathcal{C}_q$

。

玩家甲和玩家乙分別有一個無限維度的 Hilbert space

$\mathcal{H}_1, \mathcal{H}_2$

，

$\{X_s^a\}, \{Y_t^b\}$

分別定義在

$\mathcal{H}_1, \mathcal{H}_2$

上，

$|\psi\rangle \in \mathcal{H}_1\otimes \mathcal{H}_2$

，那麼這樣的量子關聯的集合記作

$\mathcal{C}_{qs}$

。

對於一系列可數維度的 Hilbert space

$\mathcal{H}_1^{(l)}, \mathcal{H}_2^{(l)}$

，玩家甲和玩家乙均有分別定義在

$\mathcal{H}_1^{(l)}, \mathcal{H}_2 ^{(l)}$

上的策略

$\{X_s^a\}^{(l)}, \{Y_t^b\}^{(l)}$

，共享的糾纏態

$|\psi^{(l)}\rangle \in \mathcal{H}_1^{(l)}\otimes \mathcal{H}_2^{(l)}$

，那麼這樣的量子關聯的集合記作

$\mathcal{C}_{qa}$

。

玩家甲和玩家乙共享一個無限維度的 Hilbert space

$\mathcal{H}$

，

$\{X_s^a\}, \{Y_t^b\}$

和

$|\psi\rangle$

都定義在

$\mathcal{H}$

上，並且滿足

$\forall a,b,s,t, [X_s^a,Y_t^b]=0$

，這樣的量子關聯的集合記作

$\mathcal{C}_{qc}$

。

根據上述定義，不難看出

$\mathcal{C}_{q}\subseteq \mathcal{C}_{qs} \subseteq \mathcal{C}_{qa} \subseteq \mathcal{C}_{qc}$

。除此之外，也不難定義經典關聯構成的集合

$\mathcal{C}_{c}$

，玩家甲和玩家乙之間不共享糾纏態即可。 Boris Tsirelson 在上世紀八十年代提出的問題（和 Connes’ embedding conjecture 等價）可以表述為下述形式：

Tsirelson 問題

。

$\mathcal{C}_{qa}$

和

$\mathcal{C}_{qc}$

是否相等？

這一問題在最近五年有了一系列進展，即

$\mathcal{C}_{q} \subsetneq \mathcal{C}_{qs} \subsetneq \mathcal{C}_{qa} \subseteq \mathcal{C}_{qc}$

：

William Slofstra 在 2016 年證明了

$\mathcal{C}_{qs} \neq \mathcal{C}_{qc}$

［2］（即弱 Tsirelson 問題的否定答案），並在次年改進到了

$\mathcal{C}_{qs} \neq \mathcal{C}_{qa}$

［3］。

而 Jalex Stark 和 Andrea Coldangelo 在 2018 年證明了

$\mathcal{C}_{q} \neq \mathcal{C}_{qs}$

［4］。

目前仍然懸而未決的是 Tsirelson 問題。而這一問題的肯定答案，即

$\mathcal{C}_{qa}=\mathcal{C}_{qc}$

，會在量子計算複雜性理論中匯出令人驚訝的結果。

不同模型上的量子互動式證明

為什麼上面關於量子關聯的刻畫和計算複雜性有關呢？這裡需要稍費些筆墨介紹互動式證明，量子 PCP 猜想淺說（一）：當互動式證明遇上量子糾纏中介紹了相關的歷史，這裡只簡單提及相關的部分。

互動式證明說的是這麼一個東西，這裡有常數個證明者（prover），還有一個驗證者（verifier），通常驗證者的能力是經典機率多項式時間的，而證明者的能力不受限制（儘管同時他們也不受驗證者的信任），證明者和驗證者之間的通訊規模是多項式的。

互動式證明系統的能力與時間/空間複雜性的聯絡，可能是計算複雜性理論在上世紀八十年代末最大的觀念上的革新 —— 如果只有一個證明者，這樣的互動式證明系統（IP）完全刻畫了多項式空間（IP=PSPACE）；如果有多個證明者，這樣的互動式證明系統（MIP）完全刻畫了非確定性指數時間（MIP=NEXP）。

上述的 non-local games 可以看做互動式證明系統，於是我們可以定義三個對應的複雜性類：

MIP.

如果證明者之間沒有共享糾纏的話，即上一節中的集合

$\mathcal{C}_c$

那麼判定這樣的互動式證明系統的最大獲勝概率對應的複雜性類稱作

$\mathsf{MIP}$

。

MIP*.

上一節中在

張量積

模型（tensor product model）上定義的三個集合

$\mathcal{C}_{q},\mathcal{C}_{qs},\mathcal{C}_{qa}$

，即證明者之間可以共享任意的糾纏態，那麼判定這樣的量子互動式證明系統的最大獲勝概率的問題對應的複雜性類稱作

$\mathsf{MIP^*}$

。

如果最大獲勝概率至少是

$c \leq 1$

，或者至多是

$c \geq s \geq 0$

的話，對應的複雜性類記作

$\mathsf{MIP^*}(c,s)$

；如果

是常數，那麼

$\mathsf{MIP^*}=\mathsf{MIP^*}(c,s)$

。 Anand Natarajan 和 John Wright 今年的工作（FOCS 2019 最佳論文獎）證明了

$\mathsf{NEEXP} \subseteq \mathsf{MIP^*}$

［5］，這意味著

$\mathsf{MIP} \subsetneq \mathsf{MIP^*}$

。

MIP^co.

上一節中在對易算符模型（commuting operator model）上定義了

$\mathcal{C}_{qc}$

，對應的複雜性類記作

$\mathsf{MIP}^{co}$

，即證明者們共享同一個 Hilbert space，但是他們的策略是可對易的。

上述三個複雜性類的平凡（？）上界分別是

$\mathsf{MIP}\subseteq \mathsf{NEXP}$

，

$\mathsf{MIP^*}\subseteq \mathsf{RE}$

和

$\mathsf{MIP}^{co}\subseteq \mathsf{co\text{-}RE}$

。這裡的複雜性類 RE 是遞迴可列舉（recursively enumerable，或稱為 Turing recognizable），即解決這些問題的

圖靈機

會在接受情形（YES case）的時候停機，但是在拒絕情形（NO case）下則不一定會停機。停機問題（Halting）是

$\mathsf{RE}$

-complete 的。類似地，考慮能夠被只在 NO case 下保證一定停機的圖靈機解決的問題，這樣的複雜性類記作

$\mathsf{co\text{-}RE}$

。

首先給出經典互動式證明系統上界

#FormatImgID_69#

的證明。注意到驗證者可能的提問數量至多是

指數的

（因為證明者和驗證者之間的通訊複雜度至多是多項式的），對每個問題窮舉可能的答案就能找到證明者們的最優策略，即非確定性指數時間（NEXP）。

然後給出

張量積模型

（tensor-product model）上的量子互動式證明系統的上界

$\mathsf{MIP^*} \subseteq \mathsf{RE}$

的證明。注意到

$\mathcal{C}_{qa}$

定義在一系列可數維度

的序列上（Sum-of-squares hierarchy 可以給出更好的刻畫），那麼我們可以設計一個圖靈機，先考慮

的所有

量子策略

，再考慮

$l\leq 2$

的所有量子策略，以此類推。如果存在某個量子策略使得獲勝機率為 1 的話（YES case），那麼圖靈機停機並輸出接受，除此之外沒有任何保證，所以在 RE 裡。

最後是對易算符模型（commuting operator model）上的量子互動式證明系統上界

$\mathsf{MIP}^{co} \subseteq \mathsf{co\text{-}RE}$

的證明。類似上一段中提到的 Sum-of-squares hierarchy，這裡會用到類似的“對偶”層次，即 NPA hierarchy ［6］。 NPA hierarchy 大致定義如下，即考慮一個序列，第一個量子關聯的集合只涉及玩家甲和玩家乙的量子策略的對易關係中只涉及一個

量子位元

的，第二個集合只涉及玩家們的策略的對易關係中至多涉及兩個量子位元的，以此類推。更詳細的介紹可以參考 Jamie Sikora 的關於半正定規劃在量子資訊中的應用的講義。如果沒有用到所有的對易約束關係的玩家們的量子策略都不能使得最大獲勝概率為 1 的話，那麼顯然沒有這樣的量子策略，於是這裡的圖靈機在 NO case （最大獲勝概率小於 1）一定會停機，即在

$\mathsf{co\text{-}RE}$

裡。

Tsirelson 問題對計算複雜性理論意味著什麼?

如果 Connes‘ embedding conjecture 是正確的（即 Tsirelson 問題的肯定答案），那麼

$\mathcal{C}_{qa}=\mathcal{C}_{qc}$

，這會匯出

$\mathsf{MIP^*}=\mathsf{MIP}^{co}\subseteq \mathsf{RE}\cap\mathsf{co\text{-}RE}=\mathsf{R}$

。這意味著什麼呢？

由於

$\mathsf{MIP^*}$

的間隙

是常數的，即我們只需要判斷最大接受機率至少是

，還是至多是

。上界

$\mathsf{co\text{-}RE}$

意味著存在保證停機的圖靈機，可以逐步減少系統可用的糾纏，找到對應的

；上界

$\mathsf{RE}$

則意味著存在保證停機的圖靈機，可以逐步增加系統可用的糾纏，找到對應的

。因而可以看出

$\mathsf{R}$

（recursive）是可判定（decidable）語言對應的複雜性類。

於是 Connes’

embedding conjecture

正確會匯出

$\mathsf{MIP^*}$

是可判定的。反之， undecidable 在

$\mathsf{MIP^*}$

中會推翻 Connes‘ embedding conjecture。那麼如何證明 undecidable is in

$\mathsf{MIP^*}$

呢？

季錚鋒

在 2016 證明了 MIP* 的 compression theorem，即

$\mathsf{NEEXP} \subseteq \mathsf{MIP^*}(c,c-1/\exp(n))$

［7］，不過“壓縮”過程需要兩個額外的證明者；這一工作的後續的改進，使得在證明者數量保持不變的情況下，仍然可以完成上述“壓縮”過程［8］ —— 透過迭代使用 compression theorem，可以將

$\mathsf{NE^{f(n)}XP}$

放在

間隙

重指數小的

$\mathsf{MIP}^*$

中，也就是說

$\mathsf{Halting}\in \mathsf{MIP^*}(1,<1)$

（William Slofstra 的

$\mathsf{C}_{qa}\neq \mathsf{C}_{qs}$

證明［3］中同樣給出了這一結果）。

對上述

compression theorem

的進一步改進，比如說在“壓縮”過程中能保持

間隙不變的話，那麼可以證明

$\mathsf{Halting} \in \mathsf{MIP^*}$

。值得一提的是， compression theorem 的證明與 Natarajan-Vidick 在 2018 年證明的 games quantum PCP theorem ［9］毫無關係。但是 Natarajan-Wright 今年四月份證明的

$\mathsf{NEEXP} \subseteq \mathsf{MIP^*}$

［5］中用到了

新的 introspection 技術（簡單介紹見如何看待 NEEXP in MIP*？）；

games quantum PCP theorem ［9］證明中的自檢測（見 Climber。pI：量子 PCP 猜想淺說（三）： Pauli 矩陣的線性檢測）；

經典 PCP 定理證明中用到 PCP of proximity （PCP 定理的介紹見如何看待 2019 年哥德爾獎授予 Irit Dinur？）。

看起來 Natarajan-Wright 給出了證明 gap-preserving compression theorem 的一線曙光，如果

$\mathsf{MIP^*}$

現有的一系列技術整合的起來的話，那麼就能夠證明

$\mathsf{RE} \subseteq \mathsf{MIP^*}$

，即推翻 Connes embedding conjecture （並給出對 Tsirelson 問題的否定回答），進而可以用量子互動式證明系統來驗證停機問題。

參考文獻

［1］ Cleve， Richard， Peter Hoyer， Benjamin Toner， and John Watrous。 “Consequences and limits of nonlocal strategies。” In

Proceedings。 19th IEEE Annual Conference on Computational Complexity， 2004。

， pp。 236-249。 IEEE， 2004。

［2］ Slofstra， William。 “Tsirelson’s problem and an embedding theorem for groups arising from non-local games。”

Journal of the American Mathematical Society

（2019）。

［3］ Slofstra， William。 “The set of quantum correlations is not closed。” In

Forum of Mathematics， Pi

， vol。 7。 Cambridge University Press， 2019。

［4］ Coladangelo， Andrea， and Jalex Stark。 “Unconditional separation of finite and infinite-dimensional quantum correlations。”

arXiv preprint arXiv：1804。05116

（2018）。

［5］ Natarajan， Anand， and John Wright。 “NEEXP in MIP。”

arXiv

preprint arXiv

：1904。05870

（2019）。

［6］ Navascués， Miguel， Stefano Pironio， and Antonio Acín。 “A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations。”

New Journal of Physics

10， no。 7 （2008）： 073013。

［7］ Ji， Zhengfeng。 “Compression of quantum multi-prover interactive proofs。” In

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing

， pp。 289-302。 ACM， 2017。

［8］ Fitzsimons， Joseph， Zhengfeng Ji， Thomas Vidick， and Henry Yuen。 “Quantum proof systems for iterated exponential time， and beyond。” In

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

， pp。 473-480。 ACM， 2019。

［9］ Natarajan， Anand， and Thomas Vidick。 “Low-degree testing for quantum states， and a quantum entangled games PCP for QMA。” In

2018 IEEE 59th Annual Symposium on Foundations of Computer Science （FOCS）

， pp。 731-742。 IEEE， 2018。

［10］ Grilo， Alex B。， William Slofstra， and Henry Yuen。 “Perfect zero knowledge for quantum multiprover interactive proofs。”

arXiv preprint arXiv：1905。11280

（2019）。

［11］ Zhengfeng Ji， Anand Natarajan， Thomas Vidick， John Wright， Henry Yuen： “MIP*=RE”， 2020； arXiv：2001。04383。

［12］ Cleve， Richard， Peter Hoyer， Benjamin Toner， and John Watrous。 “Consequences and limits of nonlocal strategies。” In

Proceedings。 19th IEEE Annual Conference on Computational Complexity， 2004。

， pp。 236-249。 IEEE， 2004。

［13］ Kobayashi， Hirotada， and Keiji Matsumoto。 “Quantum multi-prover interactive proof systems with limited

prior entanglement

。”

Journal of Computer and System Sciences

66， no。 3 （2003）： 429-450。

標簽：量子證明互動式玩家 mip

上一篇:如何選擇網路機頂盒？

下一篇：騎動感單車到底有哪些好處？

量子互動式證明可以驗證停機問題嗎?

猜你喜歡

熱血傳奇：武器破防並非破風捉影！落魄神兵才是真正的破防屆神器！

銀行時點存款證明的時點、起始、解凍日期分別是怎麼算的？

「墨子號」實驗實現相距1200公里兩個地面站之間的量子態遠端傳輸

平衡對等

什麼是超程式設計以及元語言？