量子科技中心_量科网

该研究团队探讨了部分布尔函数何时能（或不能）展现超多项式级量子查询加速，并通过两个互补维度构建了排除此类加速的通用框架：承诺感知的复杂度度量与函数完备化。 首先，研究人员引入了标准组合度量（包括块灵敏度及其变体）的承诺版本，并证明若相关承诺度量与完备化度量坍缩，则确定性与量子查询复杂度必然存在多项式关联，即D(f)=poly(Q(f))。随后分析了结构化承诺族，包括对称部分函数和基于汉明切片支撑的承诺，针对对称情形以单一间隙参数获得了精确（至多项式因子）的特征刻画，同时对k切片域给出了细化的切片依赖性边界。 接着，该工作将完备化复杂度形式化为部分函数在全体完备化上某度量的最小值，并证明度量的可完备性决定了超多项式量子加速的可能性。最后，应用该视角推导出若干函数类的广泛非加速判据——例如在标准及p偏置超立方体上具有低最大影响的函数、以及具备高效可识别定义域的函数，同时展示了通用完备化技术的某些困难性结果。