QIP 2023 有哪些值得关注的工作?
- 36 个点赞 👍
鉴于某洗稿事件, 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).
编辑于 2023-09-10 10:52・IP 属地日本查看全文>>
Climber.pI - 30 个点赞 👍
整理一下我个人比较感兴趣的工作。
首先是quantum simulation算法方向的。这部分感觉没有什么太新的内容,还是在原有的常用算法框架下研究某些特殊的模型,主要的进展是一些技术性的工作。
- Kaoru Mizuta and Keisuke Fujii. Optimal time-periodic Hamiltonian simulation
- Tomotaka Kuwahara, Tan Van Vu and Keiji Saito. Optimal light cone and digital quantum simulation of interacting bosons
- Adam Ehrenberg, Abhinav Deshpande, Christopher L. Baldwin, Dmitry A. Abanin and Alexey V. Gorshkov. Circuit complexity and classical simulation of Many-Body Localized Systems
一个与之相关的具体子领域是怎么把quantum simulation跟tomography和learning theory结合起来。一方面tomography有可能改进quantum simulation中的某些步骤,另一方面怎么从simulation的结果中提取信息也是个很自然的问题。
- Kianna Wan, William J. Huggins, Joonho Lee and Ryan Babbush. Matchgate Shadows for Fermionic Quantum Simulation
- Hsin-Yuan Huang, Yu Tong, Di Fang and Yuan Su. Learning many-body Hamiltonians with Heisenberg-limited scaling
- Hsin-Yuan Huang, Sitan Chen and John Preskill. Learning to predict arbitrary quantum processes
然后是近几年很火,个人也感觉比较重要的state tomography方向。
- Joran van Apeldoorn, Arjan Cornelissen, Andras Gilyen and Giacomo Nannicini. Quantum tomography using state-preparation unitaries
- Guang Hao Low. Classical shadows of fermions with particle number symmetry
- Sitan Chen, Brice Huang, Jerry Li, Allen Liu and Mark Sellke. Tight Bounds for State Tomography with Incoherent Measurements
对random state ensemble性质的研究。
- Joseph Iosue, Kunal Sharma, Michael Gullans and Victor Albert. Continuous-variable quantum state designs: theory and applications
- Prabhanjan Ananth, Aditya Gulati, Luowen Qian and Henry Yuen. Pseudorandom Quantum States, Revisited: New Properties, Variants, Constructions and Cryptographic Applications
- Srinivasan Arunachalam, Sergey Bravyi, Hao-Chung Cheng, Arkopal Dutt, Ching-Yi Lai and Ted Yoder. Learning beyond Cliffords: circuits and states
最后是关于entanglement entropy数学性质的研究。
- Nathaniel Johnston, Benjamin Lovitz and Aravindan Vijayaraghavan. A Complete Hierarchy of Linear Systems for Certifying Quantum Entanglement of Subspaces
- Isaac Kim, Michael Levin, Ting-Chun Lin, Daniel Ranard and Bowen Shi. Universal lower bound on topological entanglement entropy
- Nilin Abrahamsen, Ning Bao, Yuan Su, Yu Tong and Nathan Wiebe. Entanglement area law for 1D gauge theories and bosonic systems
编辑于 2022-12-31 16:55・IP 属地上海查看全文>>
Walk man