量子科技中心_量科网

该研究团队探讨了作用于n个量子比特的对数局域哈密顿量A的归一化迹2⁻ⁿTr[f(A)]的计算复杂度估计问题。该问题在DQC1模型中自然出现，但目前仅对有限类函数f(x)的复杂度有明确认知。 研究表明：若f(x)是具有Ω(poly(n))近似次数的连续函数，在关于f(x)多项式逼近误差的技术性条件成立时，以恒定加性误差估计2⁻ⁿTr[f(A)]属于DQC1完全问题。该条件适用于包括指数函数、三角函数、对数函数及反函数类型在内的广泛函数类。进一步证明：当A为稀疏矩阵时，基于DQC1查询模型中k-Forrelation问题迹变体的猜想下界，该问题的经典查询复杂度相对于近似次数呈指数级增长。 这些结果共同表明：近似次数是主导归一化迹估计复杂度的关键参数——它不仅通过高效DQC1算法表征量子复杂度，在条件成立时也呈现经典计算困难性，从而产生指数级的量子-经典计算分离。该工作的证明构建了统一框架，有机融合了电路到哈密顿量构造方法、周期性雅可比算子，以及切比雪夫等振荡定理等多项式逼近理论工具。