量子科技中心_量科网

近期，一项用于估算任意单纯复形归一化贝蒂数的经典算法被提出。受具有类似蒙特卡洛结构且样本复杂度更优的量子算法启发，研究团队对该经典算法的样本复杂度进行了更深入的分析。为此，研究团队给出了经典算法中估计量方差的上界，并证明该方差取决于底层单纯复形的特定组合性质。这一新分析促使研究团队改进了经典算法，使得“简单案例更易处理”——当单纯复形方差足够小时，样本复杂度得以降低。通过分析Erdős-Rényi随机图模型来验证“易处理”和“难处理”案例的存在性，研究团队证实了这些经典算法的有效性和局限性。具体而言，对于某些模型，改进方案几乎总能降低样本复杂度；同时也揭示了两种算法均呈现指数级样本复杂度的不同参数区间。