一个有趣的思想实验可能最好地理解量子计算复杂性的一个惊人的新证明。 洗个澡，然后将一堆漂浮的条形磁铁倒入水中。 每个磁铁都会来回翻转它的方向，试图与它的邻居对齐。 它会推动和拉动其他磁铁，并反过来被推动和拉动。 现在试着回答这个问题：系统的最终安排是什么？
事实证明，这个问题和其他类似问题是不可能的复杂。 使用超过几百个磁铁的任何东西，计算机模拟都将花费大量的时间来吐出答案。
现在让这些磁铁量子化——单个原子服从量子世界的拜占庭规则。 正如您可能猜到的那样，问题变得更加困难。 “相互作用变得更加复杂，”说 袁世凯 哥伦比亚大学的。 “对于两个相邻的‘量子磁体’何时满意，有一个更复杂的限制。”
这些看似简单的系统为经典和量子版本的计算极限提供了非凡的见解。 在经典或非量子系统的情况下， 来自计算机科学的里程碑定理 带我们走得更远。 被称为 PCP 定理（用于“概率可检验的证明”），它表明不仅磁体的最终状态（或与之相关的方面）非常难以计算，而且导致它的许多步骤也是如此。 情况的复杂性更加剧烈，也就是说，最终状态被一片神秘地带所包围。
PCP 定理的另一个版本，尚未证明，专门处理量子情况。 计算机科学家怀疑量子 PCP 猜想是正确的，并证明它会改变我们对量子问题复杂性的理解。 它可以说是量子计算复杂性理论中最重要的开放问题。 但到目前为止，它仍然无法访问。
九年前，两位研究人员确定了帮助我们实现目标的中间目标。 他们想出了 一个更简单的假设，称为“非低能平凡态”（NLTS）猜想，如果量子 PCP 猜想为真，则该猜想必须为真。 证明它并不一定会使证明量子 PCP 猜想变得更容易，但它会解决其中一些最有趣的问题。
然后上个月，三位计算机科学家 证明了 NLTS 猜想. 该结果对计算机科学和量子物理学具有惊人的意义。
“这非常令人兴奋，”说 多里特·阿哈罗诺夫 耶路撒冷希伯来大学。 “它将鼓励人们研究量子 PCP 猜想这个更难的问题。”
要理解新结果，首先要想象一个量子系统，例如一组原子。 每个原子都有一种称为自旋的特性，它有点类似于磁体的排列，因为它沿着一个轴指向。 但与磁体的排列不同，原子的自旋可以处于不同方向同时混合的状态，这种现象称为叠加。 此外，如果不考虑来自遥远区域的其他原子的自旋，可能无法描述一个原子的自旋。 当这种情况发生时，这些相互关联的原子被称为处于量子纠缠状态。 纠缠是显着的，但也很脆弱，很容易被热相互作用破坏。 系统中的热量越多，纠缠就越难。
现在想象一下冷却一堆原子，直到它们接近绝对零。 随着系统变冷并且纠缠模式变得更加稳定，它的能量会减少。 最低可能的能量，或“地面能量”，提供了对整个系统复杂的最终状态的简明描述。 或者至少它会，如果它可以被计算的话。
从 1990 年代后期开始，研究人员发现，对于某些系统，这种地面能量永远无法在任何合理的时间范围内计算出来。
然而，物理学家认为接近地面能量（但不完全存在）的能级应该更容易计算，因为系统会更温暖，纠缠更少，因此更简单。
计算机科学家不同意。 根据经典的 PCP 定理，接近最终状态的能量与最终能量本身一样难以计算。 因此，如果 PCP 定理的量子版本是正确的，它将说地面能量的前体能量与地面能量一样难以计算。 由于经典的 PCP 定理是正确的，许多研究人员认为量子版本也应该是正确的。 “当然，量子版本一定是真的，”Yuen 说。
这样一个定理的物理意义将是深远的。 这意味着存在在更高温度下保持纠缠的量子系统——这完全与物理学家的预期相矛盾。 但没有人能证明任何这样的系统存在。
2013 年，迈克尔·弗里德曼和马修·黑斯廷斯都在位于加利福尼亚州圣巴巴拉的微软研究院 Q 站工作，他们缩小了这个问题的范围。 他们决定寻找仅根据一个指标很难计算出最低和几乎最低能量的系统：计算机模拟它们所需的电路数量。 这些量子系统如果能找到它们，就必须在所有最低能量下保持丰富的纠缠模式。 此类系统的存在并不能证明量子 PCP 猜想——可能还有其他硬度指标需要考虑——但它可以算作进步。
计算机科学家不知道任何这样的系统，但他们知道去哪里寻找它们：在称为量子纠错的研究领域，研究人员创建纠缠配方，旨在保护原子免受干扰。 每个食谱都被称为一个代码，并且有许多大小不同的代码。
到 2021 年底，计算机科学家 取得重大突破 在创建本质上理想性质的量子纠错码方面。 在接下来的几个月里，其他几组研究人员在这些结果的基础上创建了不同的版本。
这篇新论文的三位作者在过去两年中一直在相关项目上进行合作，他们共同证明其中一个新代码具有制造弗里德曼和黑斯廷斯假设的那种量子系统所需的所有属性. 通过这样做，他们证明了 NLTS 猜想。
他们的结果表明，纠缠不一定像物理学家认为的那样脆弱和对温度敏感。 它支持量子 PCP 猜想，表明即使远离地面能量，量子系统的能量仍然几乎无法计算。
“它告诉我们，看起来不太可能是真的事情是真的，”说 艾萨克·金 加州大学戴维斯分校。 “尽管在一些非常奇怪的系统中。”
研究人员认为，需要不同的技术工具来证明完整的量子 PCP 猜想。 然而，他们认为有理由乐观地认为目前的结果将使他们更接近。
他们最感兴趣的可能是新发现的 NLTS 量子系统——尽管在理论上是可能的——实际上是否可以在自然界中创造出来，以及它们的外观。 根据目前的结果，它们需要复杂的远程纠缠模式，而这些模式从未在实验室中产生过，而且只能使用天文数量的原子来构建。
“这些都是高度工程化的物体，”说 钦梅尼尔克是加州大学伯克利分校的计算机科学家，也是这篇新论文的合著者。 阿努拉格·安舒 哈佛大学和 尼古拉斯·布雷克曼 伦敦大学学院。
“如果你有能力耦合真正遥远的量子比特，我相信你可以实现这个系统，”Anshu 说。 “但要真正进入低能谱，还有另一段旅程。” Breuckmann 补充道，“也许宇宙的某个部分是 NLTS。 我不知道。”
