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

249 0 0

文章摘要

量子领域的一个核心开放问题——量子随机性的实现，长期以来因其高昂的成本而备受关注。量子随机性在提升算法效率、优化复杂系统模拟以及增强密钥分发的安全性等方面具有重要应用。然而，实现这种随机性需要大量的计算资源，这使得科学家们一直在探索伪造随机性的方法。2023年10月，华人研究员Fermi Ma和黃信元发表了一篇论文，提出了一种伪造随机性的新方法，该方法不仅“优雅且安全”，还无需大量计算开销。MIT量子计算研究员Alexander Poremba对此表示，这是首次确凿地证明了伪随机性是一个真实存在的概念。

两位研究员通过76页的论文（核心证明过程仅10页）证明了在假设存在任何量子安全单向函数的情况下，伪随机幺正态（PRUs）的存在。PRUs的提出是为了解决随机幺正变换在现实操作中的困难。随机幺正在量子计算中扮演着核心角色，它们是量子霸权实验、量子算法和各种加密原语设计的基础。然而，随机幺正变换需要大量时间和计算资源来实现，因此PRUs的出现为这一问题提供了新的解决方案。

在2017年，一篇论文引入了PRUs的概念，并试图用一种结构上可控的方法来模拟Haar随机酉矩阵。Haar随机酉矩阵是数学家Alfréd Haar在20世纪初提出的概念，它定义了某种最纯粹的“随机”，即每个可能状态都等概率地出现在酉矩阵空间里。然而，前人的研究未能证明其构造的PRUs方法能像真正的Haar随机酉矩阵一样。Fermi Ma和黃信元在前人研究的基础上，首次证明了PRUs的存在。他们在存在量子安全单向函数的合理假设下，成功证明了标准PRUs和强PRUs的存在。

他们的证明过程使用了“净化”这一量子信息理论中的老技术，并结合了“路径记录模拟”这一新方法。通过提出“路径记录模拟”，他们能够记录酉算子在运算过程中的一些关键信息，从而为后续的证明提供了一个有用的观察角度。此外，他们还发现了一种之前被认为是“弱伪随机”的构造，实际上可以看作“真伪随机”。这一发现为研究Haar随机酉矩阵的量子算法提供了一种高效的模拟方法，且模拟误差几乎可以忽略不计。

论文最后，他们灵活运用胶合引理，完整地证明了伪随机幺正态是存在的。这一证明过程通过仔细研究量子算法在执行过程中的各种情况，再利用“路径记录模拟”记录的信息，巧妙地设计出模拟过程来实现。这一成果不仅解决了量子领域的一个核心问题，还为未来的量子计算和密码学研究提供了新的方向。

论文的作者Fermi Ma目前是西蒙斯-伯克利博士后研究员，研究方向为量子计算及其对密码学、复杂性理论和物理学的影响。黃信元目前是谷歌量子人工智能的高级研究科学家，研究方向包括量子机器学习和物理科学的发展。他们的这一研究成果不仅展示了华人科学家在量子计算领域的重要贡献，也为未来的量子技术发展奠定了坚实的基础。