Random-Oracle Unitary Synthesis is Impossible

在量子世界中，基本的物理定律允许几乎无限种类的变换。想象一台机器，它可以将一段信息扭曲成任何可能的形状，无论其多么复杂或奇异。这些被称为“酉变换”（unitaries）的变换是量子计算的基石。然而，仅仅因为自然界允许某种变换，并不意味着计算机能够构建它。在那些易于构建的酉变换与那些利用当前技术几乎无法实现的酉变换之间，存在着巨大的鸿沟。几十年来，科学家们一直在思考这个鸿沟是真实的，还是仅仅由于我们理解的匮乏。具体而言，他们曾问过：是否可以通过仅仅掌握一个特定的、复杂的经典函数，就能构建出每一个困难的量子变换？如果答案是肯定的，这意味着量子计算中最难的问题与经典计算中最难的问题一样难，从而将这两个世界紧密联系在一起。如果答案是否定的，则表明量子力学拥有经典逻辑无法解锁的秘密，可能需要一种全新的复杂性理论。

一组研究人员通过稍微改变游戏规则，对这个问题进行了调查。他们不再询问计算机是否可以使用一个特定的、复杂的函数来构建一个特定的变换，而是询问计算机是否可以使用一个随机的、无结构的函数，来构建一个完全随机且不可预测的变换。这种转变使他们能够测试当输入数据没有任何隐藏模式可以利用时的可能性极限。他们的发现是决定性的：使用仅有的随机函数，不可能高效地合成一个真正的随机量子变换。他们证明了，无论算法多么巧妙，如果它依赖于一个随机选择的函数，那么它都无法创造出理想的量子态，除非它进行天文数字级的提问。这一结果通过展示构建复杂量子态的能力完全取决于所提供信息的结构，解决了一个长期的争论。如果没有这种结构，这项任务仍然是遥不可及的。

研究人员还探索了量子密码学中使用的相关概念——伪随机酉变换（pseudorandom unitaries）。这些是看起来随机的量子变换，即使它们是由一个简单且高效的过程构建而成的，对于不知道用于创建它们之密钥的观察者来说，它们看起来也是随机的。多年来，创建这些“伪装”随机变换的最佳方法一直受到限制；它们只能欺骗那些提出相对较少问题的观察者。研究人员想知道，这种限制是暂时的技术障碍，还是自然界的根本法则。他们构建了一种新方法，成功地创建了这些变换，使其即使在面对提出大量问题的观察者时也能保持安全，具体来说，提问数量可高达与系统总规模成比例的程度。这比之前的方法有了显著改进，之前的方案只能处理与系统规模平方根成比例的问题数量。

然而，他们的工作也揭示了一个硬性的天花 ceiling（上限）。虽然他们可以将这些伪随机变换的安全性推向比以前更远的高度，但他们证明了，如果想要达到理论上的最大值，是不可能保持过程高效的。他们证明了，如果要求一种方法在执行步骤方面是高效的，那么它就无法在面对提出极大量问题的观察者时保持安全。这创造了一个精确的边界：你可以拥有一个既高效又能抵御中等数量问题的方法，或者你可以拥有一个能抵御海量问题的方法，但你不能两者兼得。这一发现表明，当前量子密码学中的局限性不仅仅是等待更好算法的问题，它们很可能是宇宙的一种基本约束。

该研究还探讨了一个更广泛的问题：我们是否能通过正确的经典指令，构建一台能够合成任何量子变换的通用机器？通过展示随机输入无法产生随机输出，研究人员提供了强有力的证据，证明输入的结构是至关重要的。仅仅拥有强大的计算机和随机函数是不够的；函数本身必须经过精心设计，以引导计算机走向预期的结果。这意味着，创造某些量子态的难度不仅在于计算能力，而且在于描述它们所需的信息的本质属性。这项工作有效地关闭了“一个简单的随机预言机（random oracle）可以作为解锁所有量子可能性的通用钥匙”的大门。

最后，这篇论文描绘了一幅效率与随机性之间存在张力的量子图景。研究人员表明，虽然我们可以创造出非常有说服力的随机模仿品，但如果我们想要保持过程快速，这些模仿品的质量是有硬性限制的。他们还表明，希望利用一个简单的随机函数来构建任何量子变换的想法是徒劳的。这些结果不仅提供了一种新算法或一种新的限制，它们重新定义了量子领域中可能性的边界。它们告诉我们，量子世界的复杂性并不是可以通过巧妙技巧绕过的幻象，而是一个真实的特征，需要特定的、有结构的信息来导航。对于那些正在构建量子技术未来的人来说，这意味着前行的道路不仅需要更多的力量，更需要更精确的设计。看来，宇宙要求我们在它给出答案之前，必须明确知道我们想要的是什么。