量子科技中心_量科网

假设检验领域中最基本的问题之一是身份测试问题：判断从未知分布𝒢中采样的样本是否实际上来自于某个显式分布𝒟。已知当分布𝒟的支持集为[N]时，身份测试问题的最优样本复杂度大致为O(√N)。然而，许多感兴趣的分布（包括那些可以高效采样的分布）具有指数级大小的支持集，因此最优身份测试器也需要指数级样本。 在本研究中，该团队通过考虑受限设置来绕过这一下界。上述O(√N)样本复杂度的身份测试器被构造为不会被任何（即使是低效采样的）分布所欺骗。然而，在大多数应用中，所考虑的分布都是可高效采样的，因此只需考虑不会被高效采样分布欺骗的身份测试器就足够了。在这种情况下，该团队可以专注于使用高效身份测试器进行高效验证。 该研究团队调查了经典/量子分布的高效验证与经典/量子密码学之间的关系，并展示了以下结果： • 每个量子（或经典）高效可采样分布都可以通过经典确定性多项式时间算法查询𝐏𝐏预言机（或概率多项式时间算法查询𝐍𝐏预言机）进行验证 • 如果单向函数存在，则没有任何足够随机的经典高效可采样分布是可高效验证的 • 如果单向函数不存在，则每个经典高效可采样分布都是可高效验证的 • 如果QEFID对存在，则存在一个量子高效可采样分布，该分布不可高效验证 • 如果单向谜题不存在，则可以使用高效量子计算机验证基于采样的量子优势 为获得这些结果，该工作引入了时间有界Kolmogorov复杂度的量子变体，并证明了其编码定理和不可压缩性。这些技术贡献似乎具有独立的研究价值。