今天是量子计算和密码学意义非凡的一天。两篇突破性论文刚刚发表（链接见下一条推文）。这两篇论文都改进了Shor的算法，该算法因破解RSA和椭圆曲线密码学而臭名昭著。这两个结果相结合，优化了量子堆叠的各个层。结果令人震惊。我预计叙事将发生转变，并进一步推动后量子密码学的研发。 第一篇论文是由谷歌量子人工智能撰写的。他们解决了（逻辑）Shor算法，将其定制为破解比特币和以太坊签名。该算法在256位椭圆曲线secp256k1的~1K逻辑量子位上运行。由于电路深度较低，快速超导计算机可以在几分钟内恢复私钥。我很感激能以已故论文合著者的身份加入，这在很大程度上是为了有机会与专家互动，并从内部讨论中获得阿尔法。 第二篇论文是由一家名为Oratomic的隐秘初创公司撰写的，该公司拥有前谷歌和加州理工学院的知名教员。他们的出发点是谷歌对逻辑量子电路的改进。然后，他们在物理层进行改进，使用中性原子量子计算机特有的技巧。结果估计，26000个原子量子位足以破解256位椭圆曲线签名。与之前的最先进技术相比，这将使物理量子比特数量大约提高40倍。另一方面，由于中性原子的速度相对较慢，单次Shor运行需要大约10天。 以下是我的主要收获。作为免责声明，我不是量子专家。需要时间对结果进行适当审查。根据我与团队的互动，我相信谷歌量子人工智能的结果是保守的。Oratomic论文对我来说更难评估，特别是因为使用了更奇特的qLDPC码。我会持保留态度，直到尘埃落定。 → q日：我对2032年q日的信心大幅上升。在国际海事组织看来，到2032年，量子计算机从暴露的公钥中恢复secp256k1 ECDSA私钥的可能性至少为10%。虽然2030年之前的加密相关量子计算机（CRQC）仍然不太可能，但现在无疑是开始准备的时候了。 → 审查：谷歌的论文使用零知识（ZK）证明来证明算法的存在，而不会泄露实际的优化结果。从现在开始，假设最先进的算法将被审查。出于道德或商业原因，或政府压力，可能会有自我审查。学术出版物的停刊将是一个明显的迹象。 → 破解时间：谷歌正在建造的超导量子计算机可以在几分钟内破解密钥。这是因为优化的量子电路只有100M的Toffoli门，这是令人惊讶的浅。（Toffoli门很难，因为它们需要产生所谓的“魔法状态”。）Toffoli门将在超导平台上消耗约10微秒，总计约1000秒的Shor运行时间。 → 延迟优化：两次延迟优化使密钥破解时间达到个位数分钟。第一种方法是跨量子设备并行计算。第二种方法是在通用设置阶段之后，在飞行途中将公钥馈送到量子计算机。 → 快时钟和慢时钟：初步估计，量子计算机有两个家族。快时钟风格，包括超导和光子架构，运行频率约为100 kHz。慢时钟风格，包括捕获离子和中性原子结构，运行速度大约慢1000倍（约100 Hz，或约1周破解一个键）。 → 量子位计数：该算法的尺寸优化变体在1200个逻辑量子位上运行。在一台具有表面代码纠错功能的超导计算机上，大约有500K的物理量子位，物理与逻辑之比为400:1。表面代码是保守的，假设只有四路最近邻电网连接。去年，谷歌在一台真正的量子计算机上演示了这一点。 → 未来收益：低垂的果实仍在被采摘，谷歌至少有一项优化是基于一个令人惊讶的简单观察得出的。有趣的是，人工智能（还没有！）的任务是寻找优化。这也是Craig Gidney等作者首次攻击椭圆曲线（与RSA相对）。肖尔的逻辑量子比特计数可能很快就会低于1K。 → 纠错：超导计算机的物理与逻辑比可能低于100:1。对于超导计算机来说，对于CRQC来说，这意味着大约100K的物理量子位，与最新技术相差两个数量级。中性原子量子计算机可以接受除表面码之外的纠错码。虽然运行速度要慢得多，但它们可以将物理与逻辑量子比特的比率降低到接近10:1。 → 比特币PoW：通过Grover算法实现商业上可行的比特币PoW不会很快发生。我们谈论的是几十年，可能是几个世纪之后。这一观察应有助于将讨论重点放在ECDSA和Schnorr上。（旁注：作为非官方的比特币安全研究员，我仍然认为比特币PoW是由于安全预算的减少而被煮熟的。） → 团队质量：Google Quantum AI的团队才是真正的团队。克雷格·吉德尼（@CraigGidney）可以说是世界上顶尖的量子电路优化器。就在去年，他从Shor中为RSA压缩了10倍，将物理量子比特计数从1000万减少到100万。特别感谢谷歌团队耐心地回答了我所有的新问题，并给出了详细的、基于事实的答案。我原以为会有一些炒作，但没有发现。