什麼是量子哈密頓量複雜性（Quantum Hamiltonian Complexity）？

12-31

謝邀, 我試著講一講吧.

簡單地說, 哈密頓量複雜性是從計算複雜性理論的角度來理解局部哈密頓量 (local Hamiltonian) 和基態 (包括基態本身和基態能量):

從計算機科學的角度來看, 這是對約束可滿足性問題 (constraint satisfaction problem, $mathsf{CSP}$ ) 的進一步推廣, 而與之相關的一系列結果 (包括 PCP 定理) 在量子情形下的對應並不平凡;
從物理學的角度來看, 它與基態 (也包括激發態) 的糾纏和關聯刻畫 (比如面積定律) 息息相關, 並在此基礎上提供了一系列全新的數值演算法 (因而和數值模擬相關).

哈密頓量複雜性可以稱為「量子計算」在觀念上的一次革新, 在此之前大家對量子計算的理解限於量子演算法 (如 Shor 演算法) 和複雜性 (如對量子 Turing 機的正確刻畫和 $mathsf{BQP}$ ), 在此之後則開始將理論計算機科學的思想和工具引入了理論物理 (主要是凝聚態物理).

便宜起見, 下面的敘述假設讀者知道本科層次計算理論中涉及的一些概念.

計算基態能量: LHP, QMA, 二分定理

「哈密頓量複雜性「這個名詞提出的其實很晚 (2010, 見 [2]), 而 Alexei Kitaev 在 1999 年將 Cook-Levin 定理 (3- $mathsf{SAT}$ 是 $mathsf{NP}$ -complete ) "量子化"的成功嘗試 [1] 之後, 這個領域客觀上就已經存在——Kitaev 定義了複雜性類 $mathsf{BQNP}$ ( $mathsf{QMA}$ ) 和局部哈密頓量問題 (local Hamiltonian problem), 並且證明了5- $mathsf{LHP}$ 是 $mathsf{QMA}$ -complete. 這樣的成功嘗試並不平凡, 其一是因為對於 $mathsf{LHP}$ , 時間演化的局部約束並不能直接導出全局約束 (多個量子態可以對應於相同的約化密度矩陣); 其二則是 soundness (NO instance 被接受的概率) 的證明需要引入隨機行走 (見 Yupan Liu：離散數學/圖論應用在數學/CS以外學科的例子?). 而這個結果本身也並不平凡——計算局部哈密頓量的局部可觀測量的期望值, 在一般情況下即使對量子計算機都是困難的.

局部哈密頓量問題 ( $mathsf{LHP}$ ) 說的是如何計算基態能量 (或者說是任何局部可觀測量的期望值), 對應於經典情形下的約束可滿足性問題 ( $mathsf{CSP}$ )的優化版本 (有多少約束未被滿足?). 而計算基態能量 (以及基態本身) 是凝聚態物理的數值模擬中的基本問題之一, 所以討論模擬量子系統的困難程度是哈密頓量複雜性中的一部分. 在此之後, 很多特定類型的 LHP 所屬的複雜性類被討論, 這裡不再贅述, 見 [10]. 類似 CSP, 一個自然的想法是能否建立關於 LHP 的二分定理 (dichotomy theorem), 即用某些參數對具體 LHP 所屬的複雜性層次進行分類. Cubitt 和 Montanaro 在 2013 年給出了關於量子比特(d=2)的哈密頓量的 LHP 的二分定理, 它們可能屬於 $mathsf{P}$ , $mathsf{NP}$ -complete, $mathsf{QMA}$ -complete 或 Ising-complete.

計算基態: 面積定律, 張量網路, 隨機行走/概率方法

除了基態能量, 如何計算基態也是凝聚態物理中的常見問題之一. 基於 DMRG 的一系列數值演算法 (包括後來的張量網路相關演算法) 對於一維有譜隙系統非常成功, 但是很長一段時間內沒有嚴格解釋. 那麼從計算複雜性的角度來看, 很自然的想到兩個問題:

這樣的物理系統的基態能否被有效地描述 (即參數規模為多項式)?
它們對應的局部哈密頓量問題是否在計算相對容易 (比如在 $mathsf{NP}$ 或 $mathsf{P}$ 中)?

第一個問題涉及面積定律(猜想), 即有譜隙系統的糾纏與邊界("面積")而不是整個系統("體積")有關. 基於張量網路方法的一系列構造性證明給出了一部分答案: 如一維面積定律的組合證明 [2], 即從乘積態出發用某些算符來製造糾纏, 並同時限制糾纏程度, 使得得到基態滿足譜隙和糾纏熵下界; 以及一維有譜隙的局部哈密頓量問題在 $mathsf{P}$ 中[3], 這裡用到了矩陣乘積態 (matrix product state), 這也給出了第二個問題的部分答案. 而二維面積定律以及相關的計算複雜性結果 (如對應的 $mathsf{LHP} in mathsf{NP}$ ) 至今仍是公開問題, 它的困難之處在於, 我們不知道如何證明這樣的基態的有效表示和投影糾纏對態 (projected entangled-pair states)相關; 而即使這樣的有效表示得以證明, 在計算局部可觀測量期望值的過程中, 張量網路的有效收縮仍然需要依賴系統的非平凡性質 (一般情形下收縮 PEPS 是 $mathsf{#P}$ -hard).

而對於無譜隙系統, 比如基態簡併情形, 在一維情形下可以證明它們符合對數修正後的面積定律[4]; 並提出了類似重整化群的具有遞歸結構的演算法, 對於部分臨界系統的數值模擬結果遠好於 DMRG[5], 後者是今年 APS March meeting 的 talk. 除此之外, Peter Shor 等人利用 Markov 鏈和隨機行走等組合/概率方法(計算譜隙和糾纏熵下界), 構造了spin-1的無譜隙的無阻挫(frustration-free)系統基態[6], 這意味著無阻挫系統的基態也可能有非平凡的糾纏 (spin-1/2 的無阻挫系統基態為乘積態).

關於無阻挫系統的另一個有趣結果, 是局部 Lovasz 引理 (local Lovasz lemma) 的量子對應所導出的基態計算演算法[7]. 如果我們把局部哈密頓量問題改為判斷系統是否無阻挫, 即基態能量是否為0, 這樣的問題稱為 quantum SAT. 而在經典情形下, 局部 Lovasz 引理的構造性證明給出了求解 SAT 問題的隨機演算法, 這也是經典結果"量子化"的為數不多的成功嘗試之一.

基態能量能被很好地近似嗎: 量子 PCP 猜想

PCP 定理, 即概率可檢查證明 (probability checkable proof, 或局部可檢查證明), 從互動式證明系統的角度重新刻畫了 $mathsf{NP}$ , 並在此基礎上建立了和不可近似性之間的聯繫. 對於約束可滿足問題, 比如說3-SAT, 我們知道判定是不是所有的子句(clause)都是滿足的是 $mathsf{NP}$ -hard 的; 而 PCP 定理告訴我們, 判定所有子句都是滿足的, 還是除了1/100的子句都是滿足的仍然是 $mathsf{NP}$ -hard 的. 因而 PCP 定理一度成為證明不可近似性的標準方法, 那麼 PCP 定理是否有量子對應呢?

這是一個非常困難的問題, 並且和很多問題有深刻地聯繫, 限於筆者水平姑且寫上一些. Matthew Hastings 提出了弱化版本, 即 NLTS 猜想 (No Low-energy Trivial State). NLTS 猜想說的是, 如果我們想尋找基態的近似的話 (即 low-energy state), 這些量子態都不能由常數深度 (const-depth) 的量子線路產生. 這和作為糾錯編碼 (error-correction code)的哈密頓量的基態相關, 因為這些糾錯編碼在出錯情形下不能和基態偏離太多, 也就是說具有足夠的魯棒性 (robust entanglement). 這一猜想的弱化版本被 Eldar 和 Harrow 證明[8], 更多的介紹見 Thomas Vidick 的博客 (Quid qPCP?).

上面的介紹沒有提及 Toby Cubitt 與可計算性相關的一些工作, 介紹見 Yupan Liu：Nature 和 Science 上有哪些非常有趣而又腦洞大開的文章？.

總而言之, 哈密頓量複雜性討論的是, 計算複雜性角度下的局部哈密頓量的基態(包括低能態)的一系列性質(比如能量), 包括它們所屬的複雜性類層次(特定類型的局部哈密頓量具有非平凡的物理意義, 比如有譜隙系統, 無譜隙系統, 子項互相對易的哈密頓量), 以及能否被很好地近似(與量子糾纏, 拓撲序和糾錯編碼, 以及互動式證明系統和 quantum game 相關).

Reference

[1] Kitaev A. Quantum np[J]. Talk at AQIP, 1999, 99.

[2] Aharonov D, Arad I, Landau Z, et al. Quantum Hamiltonian complexity and the detectability lemma[J]. arXiv preprint arXiv:1011.3445, 2010.

[3] Landau Z, Vazirani U, Vidick T. A polynomial time algorithm for the ground state of one-dimensional gapped local Hamiltonians[J]. Nature Physics, 2015, 11(7): 566-569.

[4] Arad I, Landau Z, Vazirani U, et al. Rigorous RG algorithms and area laws for low energy eigenstates in 1D[J]. Communications in Mathematical Physics, 2017, 356(1): 65-105. (ITCS 2017)

[5] Roberts B, Vidick T, Motrunich O I. Rigorous renormalization group method for ground space and low-energy states of local Hamiltonians[J]. arXiv preprint arXiv:1703.01994, 2017. (APS March meeting 2017)

[6] Movassagh R, Shor P W. Power law violation of the area law in quantum spin chains[J]. arXiv preprint arXiv:1408.1657, 2014. (QIP 2015)

[7] Gilyén A, Sattath O. On preparing ground states of gapped Hamiltonians: An efficient Quantum Lov"asz Local Lemma[J]. arXiv preprint arXiv:1611.08571, 2016. (FOCS 2017)

[8] Eldar L, Harrow A W. Local Hamiltonians Whose Ground States are Hard to Approximate[J]. arXiv preprint arXiv:1510.02082, 2015 (FOCS 2017)

[9] Cubitt T, Montanaro A. Complexity classification of local Hamiltonian problems[J]. SIAM Journal on Computing, 2016, 45(2): 268-316.

[10] Gharibian S, Huang Y, Landau Z, et al. Quantum hamiltonian complexity[J]. Foundations and Trends? in Theoretical Computer Science, 2015, 10(3): 159-282.

[1106.5875] Hamiltonian complexity

Hamiltonian complexity is directly concerned with the question: how hard is it to simulate a physical system?