鉴于某洗稿事件, 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". 这可能也是矩阵的非交换性质带给我们的诸多麻烦之一.

参考

1. ^Matthew B. Hastings. "Trivial low energy states for commuting Hamiltonians, and the quantum PCP conjecture." arXiv preprint arXiv:1201.3387 (2012).
2. ^当然, 我们应该讨论 decision problem, 不过这里暂不区分.
3. ^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).
4. ^Lior Eldar. "Robust quantum entanglement at (nearly) room temperature." arXiv preprint arXiv:1911.04461 (2019).
5. ^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.
6. ^Nikolas P. Breuckmann, and Jens N. Eberhardt. "Balanced product quantum codes." IEEE Transactions on Information Theory 67, no. 10 (2021): 6653-6674.
7. ^Anthony Leverrier, and Gilles Zémor. "Quantum tanner codes." arXiv preprint arXiv:2202.13641 (2022).
8. ^Zhiyang He, and Chinmay Nirkhe. "NLTS Hamiltonians from classical LTCs." arXiv preprint arXiv:2210.02999 (2022).