量子伪随机性可证明后果的局限性
存在多种量子伪随机性概念，如伪随机酉算子（PRU）、伪随机态生成器（PRSG）和类伪随机函数态生成器（PRFSG）。与已知存在等价性的经典伪随机性不同，量子伪随机性之间的关联尚未完全建立。
该研究团队提出的证据表明，某些量子伪随机性不太可能从其他形式构造而成，或至少在某些猜想不成立时难以构建。这表明量子伪随机性可能表现出与经典伪随机性截然不同的特性。研究人员通过研究新的预言机世界——在特定假设或约束下存在一种量子伪随机性而另一种不存在——为实现完全黑盒分离提供了潜在方向。具体而言：
• 该团队构建了一个酉预言机，其中存在PRFSG但不存在不使用辅助寄存器的PRU。若能证明PRU算法的结构特性，该结果可推广至一般PRU。
• 假设等周不等式式猜想成立，该研究展示了一个酉预言机世界：其中存在对数长度输出的PRFSG，但证明具有可忽略正确性误差的量子可计算伪随机生成器（QPRG）存在性难度等同于证明𝖡𝖰𝖯≠𝖰𝖢𝖬𝖠。该结果表明当前从对数长度PRSG构造QPRG方案中存在的逆多项式误差具有内在必然性。
• 基于相同猜想，该工作证明从对数长度输出PRFSG构造超对数长度输出PRSG的某些自然方法不可行。这部分补充了已知PRSG输出长度压缩的困难性。过程中还探讨了扩展PRSG输出长度的其他潜在方法。
