推荐 3.5
Conf: 50%
该论文研究量子过程中的伪随机性,试图推进 Gowers(1996)关于「反复组合局部随机可逆操作能否产生与真正随机排列不可区分的全局排列」这一长期猜想。作者考察该问题的酉量子类比,并给出两个否定性结果。第一个结果指出:以酉设计(unitary design)形式出现的统计矩匹配,一般并不能推出伪随机性,即使对最简单的量子过程也是如此。对任意固定 t,作者构造了一个可高效采样的单量子比特与双量子比特门分布族,在 T = O_t(n^2 log^2 n) 个独立步骤之后,所得到的 n 量子比特系综是带可忽略误差 exp(-Ω(log^2 n)) 的近似酉 t-设计,然而存在高效量子算法仅用 O_t(log^2 n) 次查询即可将其与真正随机区分开。这直接反驳了 Hoory–Magen–Myers–Rackoff 猜想的酉类比。第二个结果在多子集?——更准确地说,是在多项式有界矩的层次上给出酉设计与伪随机酉之间更强的分离,但该反例需要高度结构化的系综,与前面基于简单局部随机游走的构造形成对比。这意味着用酉设计来刻画黑洞物理中的信息扰乱需要谨慎:即便是最大程度扰乱的系统,也可能保留对高效实验可及的结构。基于这些发现,作者进一步提出了关于伪随机性如何在简单量子过程(如随机量子电路)中合理涌现的新猜想。
💡 推荐理由: 伪随机酉是量子密码学多类原语(如量子加密、承诺、混淆类构造)的基础假设。该工作表明「成为酉设计」并不蕴含伪随机性,直接冲击以设计性质替代伪随机性的安全论证,提醒安全从业者谨慎迁移此类假设。
🎯 建议动作: 研究跟进
排序因子: 来自 arXiv 其他板块 (+2) | Community 数据源 (+1) | LLM 评分加成 (+0.5)