量子领域的一个核心开放问题，就这样被两位华人研究员解决了？！
事情是这样的。
一直以来，量子的随机性在计算和密码学中极为有用。
一方面，它可以用来提升算法效率、优化复杂系统模拟，还能验证量子计算结果的可靠性；另一方面，量子随机性可用于生成真正随机的密钥，增强密钥分发的安全性，从而保障信息安全。
但问题是，实现这种随机性的成本很高。
因此，无数科学家们尝试找出伪造这种随机性的方法。
直到去年十月，华人研究员 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 年获得普林斯顿大学博士学位。
研究方向为量子计算及其对密码学、复杂性理论和物理学的影响。
黃信元，目前是谷歌量子人工智能的高级研究科学家，这项工作是在他访问西蒙斯计算理论研究所时进行的。
个人主页显示，他今年将加入加州理工学院任理论物理学助理教授。
其研究方向为：
量子机器何时能够比传统机器学习和预测得更好？
如何加速 / 自动化量子和物理科学的发展？
经典机器和量子机器可以学习和发现哪些物理现象？
论文：
pdf/2410.10116
本文来自微信公众号：量子位（ID：QbitAI），作者：一水
0 条