QIP 2023 有哪些值得關註的工作？

2022-11-25科學

鑒於某洗稿事件, literature review 式的評論就不要想了......寫點我不考慮做, 但出於種種原因長期關註的問題.

(2023 年 9 月 10 日補) 推薦 Chimay Nirkhe 今年七月份在 Simons Institute 的 talk (Making the Leap to Quantum PCPs), 對 NLTS theorem 證明背後的直覺給了很好的解釋 (如為什麽我們需要 quantum LDPC code? 為什麽有了 quantum LDPC code 還不夠?), 也對這一結果的局限性和可能的後續問題 (如構造 computationally hard 的 NLTS) 有很好的介紹.

蹲了很久也沒看到知乎上有 NLTS conjecture 相關的問題, 不過 Quanta Magazine 倒是給這個結果冠上了高得離譜的評價: Computer Science Proof Lifts Limits on Quantum Entanglement | Quanta Magazine 和 The Biggest Discoveries in Computer Science in 2022. 不出意外, NLTS conjecture 的證明 又一次 給了 QIP plenary talk, 當然這次人們似乎很樂觀 (如 Thomas Vidick 在 Weizmann Institute 開的新課的 Syllabus 裏已經稱作 The NLTS theorem):

Anurag Anshu, Nikolas Breuckmann and Chinmay Nirkhe. NLTS Hamiltonians from good quantum codes

為什麽說又呢? 因為對歷史還有記憶的人們, 會記得 QIP 2016 也有個 plenary talk:

Lior Eldar and Aram Harrow. Local Hamiltonians with no low-energy trivial states.

我以前寫過很簡短的 NLTS conjecture 介紹, 這裏就再轉述一部份. NLTS 猜想 (No Low-energy Trivial State) 是 Matthew Hastings ^[1] 提出的量子 PCP 猜想的推論, 這裏的平凡態 (trivial state) 是說能用常數深度量子路線 (constant-depth quantum circuit) 制備的量子態.

為什麽是常數深度呢? 如果 Hamiltonian qPCP 成立, 那麽以常數精度估計基態能量 ^[2] 也是 QMA-hard 的 -- 這意味著對於那些能量跟基態足夠接近的低能態們, 估算它們的能量也是 QMA-hard 的. 那麽再假設 QCMA≠QMA, 這些低能態們就不可能是 classical witness, 也即不會是平凡態. 當然, 上述說法未必能服眾, 特別是如果你不相信量子 PCP 猜想.

Eldar-Harrow 的證明隨後被指出只證明了 NLTS conjecture 的弱化版本, 後來甚至被證明這個弱化版本是幾近平凡的 ^[3] , 因為這一性質甚至能在一維系統上復現. 而 Eldar-Harrow 的構造被一些人認為可能是正確的, 因為它用了 high-dimension expander. 此後也有一些 NLTS conjecture 的變種被證明, 如 Lior Eldar 證明的 thermal states 版本 ^[4] , 不過最重要的資訊可能是 這篇用了 quantum coding theory 的一些新進展 .

因而在去年 quantum LDPC conjecture 被兩位俄羅斯學者 Panteleev 和 Kalachev ^[5] (還應該加上提出正確猜想的 Breuckmann 和 Eberhardt ^[6] ) 證明後, 會很自然地猜測這一裏程碑式結果會在多大程度上幫助證明 NLTS 猜想. 然而答案不算特別出人意料, 2022 年 6 月初, 這三位作者們證明了 cNLTS 猜想 (NLTS 猜想的相對弱化版本, 甚至已經發表), 並在 6 月下旬聲稱證明了 NLTS 猜想. 證明需要特定的 qLDPC 構造 (即 Leverrier 和 Zémor 的 quantum Tanner codes ^[7] ), 新的附加性質的證明只用了不到 10 頁 .

看起來 NLTS 猜想只是 qLDPC 定理的不太困難的推論 , 但還好不完全是平凡的 -- Nirkhe 和 He 試圖證明 NLTS 猜想只需要經典的 (不是參數最優的) locally testable codes ^[8] , 但嘗試以失敗告終. 而盡管經典 PCP 定理需要 LTCs, 但並不需要它們是參數最優的 (或者說 good codes). 就量子 PCP 猜想而言, 這一結果最重要的資訊可能是

qLDPC theorem 很可能對證明 Hamiltonian qPCP 很有幫助.

既然提到量子 PCP 猜想, 那還應該提一下近年證明 local Hamiltonian problem 的不可近似性的其他嘗試. 如有一系列工作試圖刻畫 quantum Max-Cut (一類 QMA-hard 的 LHP instances) 的近似演算法和經典不可近似性, 有趣的是 classical Max-Cut 和 quantum Max-Cut 的關系並不像 Max-k-SAT 和 LHP (前者是後者的特例), 這也讓 quantum Max-Cut 的近似演算法不完全平凡. 這裏一個自然的問題是 quantum Max-Cut 是否是 UG-hard 的 (關於 unique games conjecture 見筆者舊作), 而這一問題有了部份答案:

Yeongwoo Hwang, Joe Neeman, Ojas Parekh, Kevin Thompson and John Wright. Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality

不過對 FOCS 2021 accepted papers (而不是 proceedings) 有印象的讀者們, 會發現這篇的標題中多了 "conjectured". 這可能也是矩陣的非交換性質帶給我們的諸多麻煩之一.

參考

^ Matthew B. Hastings. "Trivial low energy states for commuting Hamiltonians, and the quantum PCP conjecture." arXiv preprint arXiv:1201.3387 (2012).
^ 當然, 我們應該討論 decision problem, 不過這裏暫不區分.
^ Chinmay Nirkhe, Umesh Vazirani, and Henry Yuen. "Approximate low-weight check codes and circuit lower bounds for noisy ground states." arXiv preprint arXiv:1802.07419 (2018).
^ Lior Eldar. "Robust quantum entanglement at (nearly) room temperature." arXiv preprint arXiv:1911.04461 (2019).
^ Pavel Panteleev, and Gleb Kalachev. "Asymptotically good quantum and locally testable classical LDPC codes." In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 375-388. 2022.
^ Nikolas P. Breuckmann, and Jens N. Eberhardt. "Balanced product quantum codes." IEEE Transactions on Information Theory 67, no. 10 (2021): 6653-6674.
^ Anthony Leverrier, and Gilles Zémor. "Quantum tanner codes." arXiv preprint arXiv:2202.13641 (2022).
^ Zhiyang He, and Chinmay Nirkhe. "NLTS Hamiltonians from classical LTCs." arXiv preprint arXiv:2210.02999 (2022).