一个跟我无关的定理（的诞生）

以前看 Cedric Villani 的《一个定理的诞生》，特别羡慕。今天看见 arXiv 上 2D frustration-free gapped systems 的 area law 证明，有感而发，写点梦话。

MSc 一开始扔给我的题目是 stoquastic Hamiltonian 的一个子类的 area law，当时的导师是 ____ 和 I；其中 I 是做 area law 的专家，带学生也比较负责。I 在 2010 年前后做了一系列 1D gapped systems 的 area law 的工作（早期的合作者有著名 early-stage research 大师 ____，最后封顶的工作甚至拉上了 Alexei Kitaev）；尽管 Hastings 在 2007 年就证了一维系统的 area law（纠缠熵的 upper bound 很难看），然而这一系列工作还是赢得了 cs theory community 的极高赞誉，因为他们让大家认识到 computer scientist 也可以做 area law 这种脱胎自凝聚态物理的问题。我个人甚至认为 area law 可以说是传统 Hamiltonian complexity 中最核心的问题之一（重要程度超过不靠谱的 qPCP，而且也更为自然），当时一维系统的证明的副产品就是厘清了诸如 matrix product state 或者 DMRG 等物理学家们用的 heuristic techniques 的严格证明，后来还是 QIP 2015 的 tutorial。

说回 MSc project 吧。当时的 intuition 来自 ____，把 graph Laplacian 看成 (stoquastic) Hamiltonian，这里天然地可以定义 configuration graph，而诸如图的 connectivity 等性质跟基态的纠缠有关（某 S 姓大佬一众人的 PRL 提供了 non-trivial 的例子）。第一年我没有任何 intuition，I 不太忙还经常去跟他 meet，跟以前在 CQT intern 的时候一样； ____ 当时就很难找，但是 I 在所以情况还没失控。直到次年年中，我看到了 MIT 某组的 N 在一个 summer school 的 poster，在 ____ 的鼓励下跟对方邮件联系；他做了一些信息论的结果，当时觉得不好上手，磨磨蹭蹭暑假回来才鼓起勇气花了几天认真的读和算，他建立了一个新的量和这一类 Hamiltonian 的联系，但是不知道怎么把 gapped 和这个量联系上。一直到年底才找了个 non-trivial 的例子（一篇 PRL），建立了跟 gapped 的一点联系（只有下界，然而我们需要上界）。这是我在 HUJI 的近三年里，在这个 project 唯一的（unpublished）结果。

这段时间里 ____ 就开始有一些令人费解的行为，譬如说 N 的三四页的证明里用到了 Pinsker 不等式，于是在跟 ____ 和 I 某次隔了一个多月才排到的 meet 里，我们花了近两个小时陪 ____ 讨论 Pinsker 不等式和逆 Pinsker 不等式有多 tight（后来跟做信息论的同学聊，这些东西对于他们来说是 standard 的，换言之找个懂的人聊半个小时就能解决）。第二年之后才渐渐地有了一些 intuition，掌握了一大堆具体的 counterexamples。当时还觉得跟 QIP16 某篇工作有关，跟 N 邮件讨论了一下，后来觉得自己是在没动力算那十几页东西，找不到合适的合作者就作罢。然后就是 ____ 某篇技巧平平但是 conceptually novel 的顶会论文（当然非常符合其 early-stage research 大师的身份）被做了出来，虽然跟前文中的 project 相关，但是在挂 arXiv 之前我连完整的定理 statement 都没见到。 ____ 觉得能用在这个 project 里，折腾了两三周，然后无果而终。再后来就是研究生第二年的暑假。第三年第一学期在忙着 MSc thesis 收尾，第二学期本想着去 Berkeley 呆一个月，一开始是因为疫情作罢。而后 ____ 就放飞自我了，本科室友中间就建议我换导师，可我本着这两年半积累的信任妥协，后来通过其他渠道才知道因为什么——应该说是我这十年经历的最恶心的事情。

说回今天那篇 paper 吧。

先说此前那篇，我第一次听 I 说起这事，是在研究生第二年第一学期末，当时某印度师兄跟 W 校一位老师改进了 1D frustration-free system 的结果，问 I 有没有什么 extension。他们觉得能改进，也是因为我前面用到的那篇 PRL 里的结果说 frustration-free systems 的 correlation length 和一般情形差个平方根。再后来就是四月份他们的 sub-volume law paper 挂出来了，过了几周这位印度师兄还来 Technion 给了个报告。当时简单读了下他们的 paper，但是没什么 intuition；说来惭愧，I 此前做 1D area law 的那几篇成名作我都没仔细读过（or 算过）。

听了三四版报告都不得其法，直到去年四五月份这位师兄在 Simons 的报告才觉得很清楚。对于 commuting Hamiltonian，area law 的证明是 trivial 的；但是如果把 I 做 1D area law 的那几篇工作里的技术（用到了 Chebyshev 多项式）拿过来，并不足以证明 area law。其中的关键步骤是用次数尽可能低的多项式来足够好地近似允许噪声的 AND 函数，注意到 commuting 情形 Hamiltonian 的 spectrum 在整点上之后，用 I 的框架和不同的多项式就能给出 commuting 情形的证明。

诸如 Chebyshev 多项式和这些关于多项式的近似理论的把戏，此前只是用在 (quantum) query complexity 里（譬如上世纪末那些 polynomial method 的 paper）。我还记得当时该师兄来访问的时候某 A 姓 star 也在，他问的一个问题是：Chebyshev 多项式和 Grover search 的 quadratic speedup 是不是有关？我下一次听到这个事情是在那篇 quantum singular value transform 里，这是他们把 Jordan lemma 推广到 singular value 上之后的一个 non-trivial 例子。印度师兄的 PhD thesis 的一大部分是 (quantum) communication complexity 和信息论，由于 lifting 一类的技术的应用，想来这位师兄对 polynomial method 应该算是熟稔。应该说这篇工作是非常典型且出色的 middle-stage research，前提是对不同技术的深刻理解（算是阅读大量 paper 的推论）和很好的 insights；如果不是这位师兄的独特背景，也许这一系列结果会晚出现几年。

去年年中前后，听说他们把纠缠熵的上界从 n^{5/3} 改成 n^{3/2}（有趣的是，我问 I 的时候，他看了眼 paper 才想起来之前是 5/3）。印度师兄在 Simons 的报告里的故事几乎就跟今天的 paper 一样，核心构造看起来更简单，不过好处是能像 renormalization group 一样递归地应用了。

1D gapped systems 的 area law 从 frustration-free 拓展到一般情形用了三年，也许二维甚至高维情形也会在几年内解决吧。

期间还跟他们简单讨论过几次另一个 project，但是我发现自己想的 approach 并不 work 之后就想放弃了，因为我并没有 promising approach 需要的背景。这也引出了我近几个月想得很多的一个问题：

CS 背景的学生是否适合将 physics-motivated problems（指能用 cs theory techniques 解决的那些）作为主业？譬如说广义的 Hamiltonian complexity。

我的结论是不适合。

我本科的时候上的物理系的力学/电磁学/原分光/近代物理（尽管考得一团糟），还有两学期的数理方法和量子力学（旁听了一本研究生的高量），固体物理和量子场论旁听过几节但是从来没 follow。后来毕设跟着 I 做了个数值的 project，因为这个读了一堆 Physics Review 系列的 paper，虽然 project 最后是无疾而终。读研之后我搞了两年 area law，去年还审了某顶会一篇相关的新 paper（可惜作者只投了结果 non-trivial 的推论，并把主要技术单独写了一篇......不然还能给个 weak accept），也搞了小一年另外一个 HC 相关的 project。

然而这一切都跟我 arXiv 上的三篇 paper 毫无关系。在做这些 physics-motivated problems 的时候，我意识到很多时候我并没有相关的背景（譬如说一大堆 deeply involved 的概率统计或者信息论），硬着头皮啃会非常非常慢且痛苦。每个人都有自己理解起来很困难的东西，譬如 I 就曾说他因为某 project 的缘故自己试图看了几次 multiplicative weight update，但总是不得其法。另外那个 HC 相关的 project，我在 MWU-based approach 砸了好几个月的时间（第二年第二学期因为看 QIP=PSPACE 那几篇，把 MWU 沾边的东西都看了一遍），有一些 ideas 但是一直没动手继续算下去（相比之下，有明确的 ideas，昏天黑地地算个一两周，然后意识到完全用不到反倒不是什么糟糕的体验）；后来问题被解决了很大一部分，解决方案是个 statistics-based approach，然而在看到他们 paper 前我从来没听说过 sufficient statistics。

以上只是在技术层面上，严格来说属于“可以克服的困难”；因为如果导师靠谱，外加自己砸了足够多的时间的话，还是有可能解决的问题。如果考虑长期学术生涯，那么更大的问题是由于缺乏 physics insights，并不知道如何选择合适的问题，也不会判断哪些问题是自然的或者有意义的。譬如说，以指数精度来近似 local Hamiltonain 的 ground energy 是个自然的问题，因为这样精确的测量通常意味着更高的时间复杂度：

• 这个问题可以定义成复杂性类，叫 PreciseQMA，还可以证明它等于 PSPACE。
• 那么为什么这个问题这么复杂呢？只是因为指数精度吗？实际原因是这时候 spectral gap 也是指数小的，当 spectral gap 是 1/poly 的时候就要容易很多。

第二条是去年的新结果，用到的技术多是老生常谈，典型的现有技术的排列组合。反面例子则是那一堆 oracle problems，在此基础上讨论形形色色的 Hamiltonians 对应的 oracle problems，非常 artifical。而事实上 HC 这个圈子里，很少 CS 背景还能持续输出结果自然的 paper 的；常见例子里 V 姓 star 只投入了很有限的精力，而 ____ 则是本科和 MSc 都是学物理的。

我的结论是，如果想长期做这一类问题（即投入一定比例的精力）的话，要不然跟 V 姓 star 一样有合适且靠谱的物理背景合作者，并且只关注少数几个问题；要不然跟某印度师兄一样有一技之长（譬如信息论黑魔法师）。

梦话说的有点多了。这也算是我这些年几乎亲眼见证的最大的结果了吧。

又及。可能是我脱离学术界太久了吧，过了几天无意中翻了下 PI 的近期报告，看到了印度师兄在 1 月 28 日的 job candidate talk，讲了他 postdoc 这两年的四个工作（两篇 cs theory 顶会+一篇 PRX，没算这篇 breakthrough）。幻灯片上也写了这个结果，当时还是 work in progress，参数基本一样，非常简略地提及了证明思路。

如此说来二月初 QIP 的时候，应该已经有些 rumor 传了出来。去年的 MIP*=RE 就是如此，当时从 Caltech 的学生们那里走漏了一些消息，似乎是因为作者们中的某位给过报告。