量子科技中心_量科网

“卵石游戏”——这一经典可逆计算中的抽象概念——已被用于设计处理固有顺序任务的量子电路。Gidney的研究表明，在卵石游戏过程中引入哈达玛基测量能显著降低计算成本，这种扩展被称为“幽灵卵石游戏”，因为测量会留下名为“幽灵”的暂态相位误差。该工作首次定义并研究了并行幽灵卵石游戏。Blocki、Holman和Lee（TCC 2022）及Gidney先前的研究分别验证了并行性或幽灵机制单独带来的优势；而本研究表明，当这两种技术协同使用时将产生惊人增益。首先通过构造性证明，研究团队展示长度为𝓁的线图可在深度2𝓁（达到理论最优）条件下用≤2.47 log 𝓁的空间完成卵石摆放。随后为探索更低空间占用的方案，该团队采用Julia语言实现的高度优化A*搜索算法，针对给定卵石数𝑠的不同线图长度𝓁，找到了深度最小的并行幽灵卵石摆放方案。 这些技术被应用于Regev因数分解算法（Journal of the ACM 2025），显著降低了其算术运算成本。例如研究发现4096位整数𝑁可在乘法深度193的条件下完成分解，优于Regev早期变体所需的680层深度，也优于Ekerå与Gärtner报告的Shor算法444层深度（IACR Communications in Cryptology 2025）。尽管空间优化的Shor算法实现仍是大整数量子分解的最有力候选方案，但本研究表明Regev算法未来可能具有实用价值，特别是考虑到进一步优化的可能性。最后，该团队相信这些卵石摆放技术在整数分解之外的量子密码分析领域也将获得应用。