計算與驗證是不同任務
量子電路可以變換疊加態,再返回經典測量結果。複雜性理論研究的是這樣一族計算:當輸入長度增長時,其資源也按受控方式增長。另一個問題允許證明者提供一個量子態,幫助量子驗證器接受「是」實例。驗證器仍須對所有聲稱的見證拒絕「否」實例。
我們討論判定問題,以語言 表示。電路作用於經典輸入的基態編碼。複雜性類的包含關係是對所有輸入長度的陳述,不是關於某個固定大小的裝置,也不是關於某次恰好成功的實驗。
一致量子電路與 BQP
固定一個元素可計算的有限通用門集,例如包含 Hadamard、、受控非門和標準可逆經典門的門集。
定義 6.1.1
(多項式時間一致的電路族)
如果存在確定性經典算法,以 為輸入,在關於 的多項式時間內輸出 的描述,就稱族 多項式時間一致。
因此電路的門數和線路數也是多項式級。電路對長度 固定;具體輸入 放在輸入線上。有限門集避免把具有無限精度的任意實數角度旋轉當作一次免費操作。這裏的通用是指近似通用。對滿足通常逆門與通用性條件的標準固定有限門集,Solovay–Kitaev 定理 給出高效近似,其開銷對精度倒數呈多對數增長。將多項式數量的門近似到足夠小的逆多項式誤差,可在多項式開銷下保持常數判定間隔。這裏引用這一門集等價結果,不作證明。
定義 6.1.2
(BQP)
若存在多項式時間一致、多項式大小的量子電路族,輸入為 和多項式數量的 輔助量子比特,且指定輸出量子比特滿足
則稱語言 屬於 BQP。
接受指在計算基中測量指定輸出量子比特,結果為 1。概率由電路和測量決定,不需要對輸入假設某個概率分佈。利用標準電路構造可推遲中間測量;這裏的定義使用最終測量。這些常數表達固定間隔,並不要求答案完全精確。
例題 6.1.3
(奇偶性屬於 BQP)
一個一致可生成的可逆電路可將 的奇偶性算入初始為零的輸出位:從每個輸入位向輸出位依次施加受控非門。它必然接受奇校驗字串並拒絕偶校驗字串。因此奇偶性屬於 BQP,但該例並未顯示量子加速:這個問題用經典方法也很容易求解。
常見錯誤
(從定義中去掉一致性)
只要求多項式大小的電路而不要求一致生成,會使某些不可判定語言變成可高效判定。設 為任意集合,定義一元語言 。對每個 分別構造時,一個大小為 的電路可以檢查輸入是否為 ,並使用一個硬編碼位表示 與否。若 不可計算,甚至不存在可計算電路生成器能作出這些選擇。事實上,若電路可計算地生成、門元素可計算且具有有界誤差間隔,就能得到判定 的算法:生成電路,並將其有限維接受概率近似到足夠精度,即使模擬需要指數時間也無妨。只有多項式大小、沒有一致生成要求,是另一種非一致資源模型。
量子見證與 QMA
固定多項式以限制見證長度 、輔助寄存器長度和驗證電路大小。多項式時間一致的電路族 接收經典輸入 、 個量子比特的見證態 和新鮮的零輔助寄存器。見證可以是其寄存器上的任意密度算子:它可以是混態,也可以在不同量子比特之間糾纏。若證明者保留與見證糾纏的外部系統,驗證器收到的約化態也可能是混態。電路結束後測量指定輸出量子比特;令 為結果為 1 的概率。
定義 6.1.4
(QMA)
若這樣的驗證器對每個經典輸入 同時具有以下性質,則稱語言 屬於 QMA:
- 完備性: 若 ,存在見證 使 。
- 可靠性: 若 ,每個見證 都滿足 。
量詞次序很重要。「是」情形只需一個好狀態;「否」情形必須抵抗任意狀態,包括疊加態和混態。驗證器必須一致生成且大小為多項式。定義不要求驗證器能高效製備見證,也不提供尋找見證的方法。更一般地,承諾問題由互不相交的「是」輸入集和「否」輸入集組成;驗證器只須在這兩集合上滿足相應條件,承諾以外的行為可以任意。對語言而言,「否」集合是「是」集合的補集。
對固定輸入 ,接受概率可寫為 ,其中 是見證寄存器上的正算子。其構造是:準備固定輸入與輔助寄存器,用驗證電路共軛輸出接受投影,再對這些固定寄存器取相應矩陣元。由有限維譜定理,所有密度算子上的最大值是 的最大特徵值,並且可由純特徵態達到。因此允許混態不改變存在性最優值,但可靠性仍必須覆蓋所有狀態。此數學刻畫並不聲稱能高效對角化 。
反例模式
測試基態見證不等於可靠性
說法:若「否」實例上每個計算基見證都以至少 的概率被拒絕,則可靠性成立。令單量子比特見證的接受算子為 。可先測試是否為 ,成功時再以獨立公平硬幣決定是否接受,從而實現此算子。基態 各以 的概率被接受,符合 QMA「否」實例的 上界;但 以 的概率被接受,違反該界。即使測試所有計算基見證,也不能保證對任意量子見證的可靠性;該說法不成立,修正方法是界定 的最大特徵值,這裏是 。
基本包含關係
命題 6.1.5
(基本包含關係)
且 。
證明
(可逆模擬、被忽略的見證與經典見證)
對 BPP,將多項式時間隨機經典算法表示為一致的多項式大小經典電路 ,其中 是多項式長度的均勻隨機字串。保留 並可逆地計算該電路;例如,用可逆門記錄中間 Boolean 門的值。對每個隨機位施加 Hadamard 門進行準備。所得狀態的各分支由 標記且相互正交,測量輸出便得到與經典算法完全相同的接受概率。因此 BPP BQP。確定性多項式時間計算是特例。
對於 BQP QMA,讓驗證器運行 BQP 電路並忽略一個固定大小的見證寄存器。在「是」實例上任何見證都可以;在「否」實例上每個見證都得到相同的拒絕界。
對於 NP QMA,設確定性多項式時間經典驗證器 使用多項式長度見證。量子驗證器採用由 控制的經典可逆置換電路,保持見證寄存器不變並將 算入輸出。若 是「是」實例,將經典接受字串編碼為 即為被接受的量子見證。對固定 ,接受算子為 。因此任意密度算子 ,包括混態或糾纏見證,都滿足 。「否」實例中所有 均為零,故所有量子見證都被拒絕。
例題 6.1.6
(可滿足性驗證器與相干見證)
取 。只有賦值 (即 )滿足它,所以 。經典見證 以概率 被接受。相干見證 以概率 被接受,因為 。對不可滿足的公式,例如 ,,每個量子見證都被拒絕。這通過 NP 證明可滿足性語言屬於 QMA;它並未證明量子電腦能夠高效找到滿足賦值。
常見錯誤
(把包含關係讀成分離)
這些包含關係並未建立 、 或 。上面證明的箭頭不能推出其中任何一個結論。預言機模型中的查詢複雜性分離也必須保留預言機限定,不能自動當作無相對化複雜性類的分離。
誤差放大與見證的微妙之處
命題 6.1.7
(BQP 的誤差降低)
若某語言有間隔為 對 的 BQP 電路族,則對奇數 ,運行 個獨立副本並取多數,在每個輸入上的誤差至多為 。
證明
(獨立運行的多數)
可在同一經典輸入上用新寄存器運行 個相互獨立的副本,並在最終輸出測量前通過可逆經典電路取多數。原成功概率至少為 時,由 Hoeffding 不等式,多數判斷錯誤的概率至多為 。對「否」實例有類似界。取奇數 ,並使它按所需置信參數多項式增長,就能以多項式開銷得到指數小的誤差。這裏的輸入是可以複製的經典基態,並不是在克隆未知量子態。
例題 6.1.8
(三取多數:精確值與上界)
每次運行成功概率為 時,三取多數正確的概率為 。Hoeffding 上界 大於 ,在這裏甚麼也說明不了:只有 足夠大時該界才有用。要保證誤差至多為 ,可取 ,它是奇數且 ;當 時 。
對 QMA,不能以作弊者提供獨立見證為前提證明重複可靠。
定理 6.1.9
(QMA 的並行重複)
取 個見證寄存器,使見證長度變為 ,對每個寄存器各運行一次驗證器,並在多數接受時接受。則在「是」實例上存在見證,被接受的概率至少為 ;在「否」實例上每個見證(無論是否糾纏)被接受的概率至多為 。
證明
(對角化單次接受算子)
固定 並對角化單次接受算子 。每次測試的接受效應為 、拒絕效應為 。這些效應分別作用於不同寄存器,因此多數接受算子在 的張量積特徵基中為對角算子。「否」實例中可靠性使 的每個特徵值至多為 ;每個基向量元組給出獨立但不一定同分佈的 Bernoulli 結果,各次接受概率至多為 。Hoeffding 不等式將其多數接受概率界在 以下,而任意糾纏密度算子只給出這些對角值的凸組合。「是」實例中最大特徵值至少為 ,證明者可提供對應好特徵向量的乘積態;這不是驗證器克隆未知態。
證明透視
對角化如何排除糾纏的證明者
作弊的證明者可能把 個寄存器糾纏起來,使 次測試的結果不一定獨立。不顯然的一步是先對角化、再看見證:多數接受算子是相互對易的單次算子的函數,所以在乘積特徵基中是對角的,任何見證的接受概率都是對角元的凸組合。每個對角元就是若干獨立 Bernoulli 試驗取多數的普通概率,可用 Hoeffding 不等式。可靠性只通過特徵值界 被用到,而只對單個被測見證的界在這裏不夠用。沒有這一步,就只能對獨立見證論證。
Marriott 和 Watrous 的 Quantum Arthur-Merlin Games 給出更強結果:QMA 的完備性和可靠性誤差可以用多項式驗證器開銷降到指數小,而不增加見證長度。這裏引用該放大定理,不證明其構造。更強之處在於保持原見證長度。更一般地,只要完備性與可靠性閾值可高效指定且相距至少為逆多項式,就能以多項式開銷放大。放大不會將量子見證變成經典見證。
兩者都包含於經典的多項式空間計算之內,這限制了它們的大小。
自然延伸的下一個問題
BQP 和 QMA 與經典類相比如何?
兩者都包含於經典的多項式空間計算之內,這限制了它們的大小。
標準結果給出 以及 ,其中 是可由多項式時間概率算法判定的語言類,該算法的正確概率嚴格大於 。這些只是上界:目前並不知道 是否不同於 ,也不知道這兩個量子類是否等於 。
練習與解答
快速檢查
(一致電路族對每個「是」輸入以概率 接受,對每個「否」輸入以概率 接受。假設大小為多項式且輔助寄存器初始為零,它是否滿足所述 BQP 閾值?)
與 和 比較。
解答 · 答案
可以:在所述一致性與資源假設下, 且 。
快速檢查
(一個候選 QMA 驗證器在某個「否」輸入上以概率 接受一個被測試的見證。這足以證明可靠性嗎?)
回想可靠性條件中的量詞。
解答 · 答案
不夠。可靠性必須對每個見證成立,而不只是一個;另一個狀態可能以高概率被接受。
快速檢查
(解釋見證寄存器保持不變如何使 NP 到 QMA 驗證器的接受算子成為對角算子,並控制相干見證的接受概率。)
在見證字串的基中寫出接受算子。
解答 · 答案
可逆驗證器保持見證不變,接受算子為對角算子 。對每個密度算子,其接受概率為 ;在「否」實例上每一項都為零。
快速檢查
(某驗證器在一個見證量子比特上的接受算子為 。求所有密度算子上的最大接受概率,並給出達到它的見證。)
用最大特徵值。
解答 · 答案
最大特徵值為 ,由 達到。密度算子是純態的凸組合,沒有任何狀態能超過最大特徵值。
快速檢查
(僅由 ,能否推出該包含是嚴格的,或 NP 包含於 BQP?)
想想單單一個包含關係能說明甚麼。
解答 · 答案
這兩個結論都不能由該包含推出。單憑包含關係不能證明嚴格性,它本身也沒有說明 NP 是否包含於 BQP。
快速檢查
(對正整數 ,給出足夠的奇數次 BQP 重複次數,使 Hoeffding 誤差界至多為 。)
解 。
解答 · 答案
取 。它是奇數且 ,所以 。這是充分的界,不一定是最少的重複次數。
練習 6.1.10
(假設某「否」實例滿足 。對三個並行驗證器副本,證明即使見證是三寄存器糾纏態,至少兩次接受的概率也至多為 。)
核心證明
解答(3)
- 1
對角化單次算子
關鍵一步
在 的張量積特徵基中,三副本的多數接受算子是對角的,所以任何見證的接受概率都是對角元的凸組合。
- 2
界定一個對角元
一個基向量三元組給出獨立的接受概率 。至少兩次成功的概率對每個 逐座標不減,所以至多等於 處的值:
依據: 的每個特徵值至多為 。
- 3
對糾纏見證下結論
∎任何密度算子,無論是否糾纏,都給出這些對角值的凸組合,每個值至多為 ,所以接受概率至多為 。