By 刘杰 18 年 2022 月 XNUMX 日发布
人们普遍认为，量子计算机至少在 15 年内不会对我们的安全系统造成任何严重损害。 届时，全面的容错量子计算机有望面世，并能够在合理的时间内运行 Shor 算法来破解 RSA。 好吧，现实要暗淡得多：真正的量子安全威胁要紧迫得多，很可能在五年内。
你可能会问，“真的吗？ 为何如此？”
这些近期的安全威胁将来自我们今天已经身处的 NISQ 时代在容易出错的量子设备上运行的启发式算法。
使用 Shor 算法，分解 2048 位 RSA 数字需要 100,000 个容错量子位运行 10 天，或 20M NISQ 量子位运行 8 小时。 由于我们至少在十年内不会拥有如此大规模的量子计算机，因此我们可能会觉得手头有很多时间可以准备。
但是使用今天的 NISQ 设备，我们在 Zapata Computing 提出了一种启发式算法，称为 变分量子分解 （VQF，已获专利），我们估计它可以在一小时内将 2048 位 RSA 数分解为大约 6,000 个 NISQ 量子位。 根据领先的量子计算机公司发布的产品路线图，这种规模的 NISQ 量子计算机预计将在五年内面世。
想想看。 量子安全威胁比大多数人意识到的要紧迫得多。
好吧，您可能想知道，“什么是启发式算法，为什么在这种情况下，它在破解 RSA 数字方面比 Shor 算法强大得多？”
计算复杂性的先驱和图灵奖获得者斯蒂芬·库克 (Stephen Cook) 对此做出了很好的定义：
“A 启发式算法 是一种旨在通过牺牲最优性、准确性、精确性或完整性来换取速度，以比传统方法更快、更有效的方式解决问题的方法。”
换句话说，启发式算法在数学上并不完整或在理论上没有得到证明，但它在实践中有效。 启发式算法的一个著名示例是神经网络，它已被证明在面部识别等应用中极其有效，尽管没有数学证据表明它应该有效。 此外，随着更好的卷积神经网络的设计，它变得越来越准确和强大。
我们的 VQF 算法是另一个例子。 与秀尔算法不同，它是一种同时使用量子计算机和经典计算机的混合算法。 具体来说，它将因式分解问题映射为组合优化问题，使用经典计算机进行预处理，并采用著名的量子近似优化算法（QAOA）。 这种方法显着减少了分解大数所需的量子比特数。
NISQ 威胁比 PQC 威胁更近期
虽然学术界、标准机构和安全公司的大部分努力都集中在减轻未来十年或更长时间后量子密码学 (PQC) 时代的安全威胁，而 Shor 算法的预期威胁是在全面、容错量子上运行计算机，VQF 算法暴露了在我们今天已经处于 NISQ 时代的量子计算机上运行的启发式算法的近期安全威胁的可行性。
我们一直在密切关注这个问题，并与大型企业、政府和组织进行了交谈。 这是他们最关心的一种量子网络安全威胁。
凭借我们丰富的量子科学家和我们的 Orquestra® 软件平台 在量子计算机上运行，我们开发了一套工具和服务来帮助您更好地准备应对来自 NISQ 时代及以后的安全威胁，包括研究、评估、测试、评级和验证。
让我们今天开始吧。
Zapata Computing 产品副总裁 Jay Liu
