#randomness-certification

共收录 1 条相关安全情报。

← 返回所有主题
👥 作者: Markus Bläser, Michael Gullans, Dominik Hangleiter, Yuxuan Liu, Youming Qiao

该论文研究的是量子优势(quantum advantage)理论中的一个核心开放问题:是否存在一类量子优势协议,其资源需求与随机电路采样(random circuit sampling, RCS)相当,同时又能仅凭量子计算输出的经典数据被经典验证者验证?作者指出,RCS 虽然资源需求低、实验上已可演示,但其输出结果在经典侧难以高效验证,因为验证者要判断采样是否来自目标分布,通常需要完成与经典对手同样困难的采样任务。为此,作者提出「模拟秘密(simulation secret)」这一新范式:验证者掌握一个只有自己知道的秘密,借助该秘密可以比经典对手更快地完成交叉熵测试(cross-entropy test),从而在经典侧高效判别量子设备是否真的完成了采样任务;而不知道秘密的经典对手即使能执行算法,也必须付出更高的计算代价才能通过同一测试。论文的具体实现基于 IQP 电路,其对应多项式为三次多项式,并带有「植入的独立空间(planted independent spaces)」。这些独立空间是多项式在一般线性群作用下的轨道中最大的独立集,并能导出对应量子态的低秩 stabilizer 分解,从而为验证者提供可高效计算的结构。作者提出两个猜想支撑安全性:第一,足够大的独立空间对计算受限的对手是「不可见」的,因此对手无法利用该结构通过协议;第二,对于均匀随机的多项式,产生能通过交叉熵测试的样本具有特定的细粒度复杂性下界。在这两个猜想成立的前提下,验证时间与经典对手通过协议所需时间之间形成多项式级别的差距,且二者都是指数级的。该方案还具有生成可经典认证的随机性的潜力,因为输出分布具有高最小熵。作者估计该植入多项式方案可在约 100 个逻辑量子比特、逻辑错误率约 10^-6 的条件下实现。

💡 推荐理由: 它把「量子优势」从单纯比拼算力推进到可经典验证的层面,并指向可认证随机数生成,这直接关系到密钥生成与信任根的安全假设,值得密码学与量子安全方向从业者跟进。

🎯 建议动作: 研究跟进:纳入内部评估,重点跟踪两个核心猜想的后续论证与实验资源需求变化。

排序因子: 来自 arXiv 其他板块 (+2) | Community 数据源 (+1) | LLM 评分加成 (+0.5)