量子科技中心_量科网

对于一个（可能部分的）布尔函数f:{0,1}^n→{0,1}，以及将布尔函数映射到实数的查询复杂度度量M，该团队定义M在f上的组合极限为M*(f)=lim_{k→∞} M(f^k)^{1/k}。 该研究团队研究了查询复杂度中一般度量的组合极限。研究表明，在对度量做出合理假设的条件下，该极限是收敛的。随后，该工作给出了关于随机查询复杂度组合极限的惊人结果：证明R_0*(f)=max{R*(f),C*(f)}。特别值得注意的是，这意味着任何针对递归三多数问题的有界误差随机算法，都可以转化为完成同一任务的零误差随机算法。该结果还推广至量子算法领域：对于递归组合函数，有界误差量子算法可转化为高概率找到证书的量子算法。 在证明过程中，研究人员还建立了关于度量与组合极限的各种组合性质。