量子科技中心_量科网

量子算法与密码学中的一个核心问题是：如何分析具有随机群元素（如随机函数、置换或幺正算符）预言机访问权限的算法？能否高效模拟这类算法？能否在 t 次查询后确定它们学到了什么？为此，一个经典工具是惰性采样：预言机不会预先提交完整的群元素，而是在查询过程中逐步采样其部分信息。该工作研究惰性采样的量子模拟：压缩预言机（或称记录预言机）。这些量子数据结构允许对量子查询进行实时模拟，最初由 Zhandry (CRYPTO '19) 针对随机函数提出，随后由 Ma-Huang (STOC '25) 推广至幺正算符，由 Carolan (STOC '26) 推广至置换，并因其可解释性在安全证明和下界推导中取得了显著成效。该团队定义并分析了一种通用的、可解释的路径记录预言机，该预言机基于第一性原理推导，可完美模拟 \(U(N)\) 的任何闭子群的随机元素。该预言机以叠加态形式存储 t 个输入-输出对，其更新过程由群张量幂表示的交换子代数来描述。这一机制透明地记录了算法已学习到的信息。该工作建立在 Grinko-Yoshida (QIP '26) 近期工作的基础上，后者提出了一种不同但缺乏清晰可解释性的通用压缩预言机。该团队的路径记录预言机的一个有趣应用是，允许对不同群的压缩预言机进行直接比较，从而为证明伪随机性结果提供了一种新技术。例如，比较 \(S_N\) 和 \(U(N)\) 可得到目前可谓最简洁的伪随机幺正算符构造：即一个伪随机置换与一个随机 Clifford 算符的乘积 PC，这改进了先前的 PFC 构造 (Metger-Poremba-Sinha-Yuen, FOCS '24; Ma-Huang, STOC '25)。