两华人76页论文解决量子领域核心问题：首次证明伪随机性真实存在

量子领域的一个核心开放问题，就这样被两位华人研究员解决了？！

事情是这样的。

一直以来，量子的随机性在计算和密码学中极为有用。

一方面，它可以用来提升算法效率、优化复杂系统模拟，还能验证量子计算结果的可靠性；另一方面，量子随机性可用于生成真正随机的密钥，增强密钥分发的安全性，从而保障信息安全。

但问题是，实现这种随机性的成本很高。

因此，无数科学家们尝试找出伪造这种随机性的方法。

直到去年十月，华人研究员Fermi Ma和黃信元发表了一篇论文，提出了一种伪造随机性的新方法。

按量子杂志的说法，他们的新方法“优雅且安全”，还无需大量计算开销。

同时，MIT量子计算研究员Alexander Poremba也表示：

• 我们首次有了确凿的证据证明伪随机性是一个真实存在的概念。

具体咋回事儿？下面咱们接着看。

核心用10页论文证明了PRUs的存在

概括而言，两位作者用76页论文（核心证明过程仅10页）证明了假设存在任何量子安全单向函数的情况下，伪随机幺正态（PRUs）的存在。

要想理解这项研究，我们首先需要了解随机幺正（Random unitaries）这个概念。

随机幺正在量子计算中扮演着核心角色，它们是量子霸权实验、量子算法和各种加密原语设计的基础。在物理学中，它们用于模拟高度混乱的过程，例如黑洞动力学。

然而，随机幺正变换需要大量时间（通常是指数级的）和计算资源来实现，因此现实层面很难操作。

于是乎，PRUs应运而生。一旦证明存在PRUs，随机幺正变换也能变得更加高效。

2017年，一篇论文引入了PRUs的概念，并试图用一种结构上可控的方法来模拟Haar随机酉矩阵。

p.s. Haar随机酉矩阵是数学家Alfréd Haar在20世纪初提出的概念，它定义了某种最纯粹的“随机”，即每个可能状态都等概率地出现在酉矩阵空间里。

不过遗憾的是，作者未能证明其构造的PRUs方法能像真正的Haar随机酉矩阵一样。

而在前人研究基础上，两位华人研究员首次证明了PRUs的存在。

从论文介绍来看，他们在存在量子安全单向函数的合理假设下，成功证明了标准PRUs和强PRUs的存在。

具体而言，他们使用了“净化”（purification）这一量子信息理论中的老技术。

其核心思想是，一个复杂随机系统，其实可以看成是一个更大、但状态确定的系统的一部分。

通过提出“路径记录模拟”（path-recording simulation）这一新方法，他们能把酉算子在运算过程中的一些关键信息记录下来，这样就可以通过分析这些记录来了解酉算子的特点，为后续的证明提供了一个有用观察角度。

然后借助一种特殊函数——单向函数，即从一个方向计算很容易，但几乎很难从结果反推回去，他们发现了一个之前被认为是“弱伪随机”的构造，实际可以看作“真伪随机”。

• 在保持简单结构的同时，伪装成Haar随机酉矩阵。

此外，他们还证明了对于一些研究Haar随机酉矩阵的量子算法，有一种高效的模拟方法，且模拟误差几乎可以忽略不计。

这一证明是通过仔细研究量子算法在执行过程中的各种情况，再利用“路径记录模拟”记录的信息，巧妙地设计出模拟过程来实现的。

论文最后，他们灵活运用胶合引理（能把证明过程中不同部分的结果连接起来的方法）完整地证明了伪随机幺正态是存在的。

完整证明过程可查看以下章节部分：

作者为两位华人

论文作者一共两位，均为华人。

Fermi Ma，目前是西蒙斯-伯克利博士后研究员，于2021年获得普林斯顿大学博士学位。

研究方向为量子计算及其对密码学、复杂性理论和物理学的影响。

黃信元，目前是谷歌量子人工智能的高级研究科学家，这项工作是在他访问西蒙斯计算理论研究所时进行的。

个人主页显示，他今年将加入加州理工学院任理论物理学助理教授。

其研究方向为：

• 量子机器何时能够比传统机器学习和预测得更好？
• 如何加速/自动化量子和物理科学的发展？
• 经典机器和量子机器可以学习和发现哪些物理现象？

论文：
https://arxiv.org/pdf/2410.10116