量子科技中心_量科网

该研究团队针对量子多体物理与量子复杂性理论中的两个核心问题——局域哈密顿量（LH）问题的计算复杂度与量子配分函数（QPF）的近似计算展开研究。这两个问题均已被证明具有QMA完全性，在广泛认可的𝖡𝖰𝖯≠𝖰𝖬𝖠假设下不存在高效量子算法。当前LH问题的最优量子算法时间复杂度为O(2^(n/2)(1−o(1)))，而QPF问题在相对误差δ下的最优算法时间复杂度为O*(1/δ√(2^nZ))，其中Z表示配分函数值。是否存在更高效算法是该领域的开放性难题。 该工作建立了严格的条件性下界，证明现有算法近乎最优。基于量子强指数时间假设（QSETH），研究人员证明：即使对于3-局域哈密顿量系统，不存在显著快于O(2^(n/2))的量子算法能求解LH或近似QPF。具体贡献包括：1）在QSETH下，3-局域LH问题无法在O(2^(n/2)(1−ε))时间内求解（∀ε>0）；2）在QSETH下，3-局域QPF问题无法在O(2^(n/2)(1−ε))时间内实现任意恒定相对误差近似（∀ε>0）；3）提出新型量子算法，可在O*(2^(n/2))时间内实现1/2+1/poly(n)相对误差的QPF近似，与条件性下界相匹配。 值得注意的是，这是首次针对固定局域性（3-局域LH与3-局域QPF）建立的精细粒度下界，与QSETH中SAT实例局域性及哈密顿量参数依赖ε的平凡下界形成鲜明对比。该结果与多数物理系统中相互作用粒子数固定的特性相吻合。研究结果表明：在QSETH假设下，当相对误差超过1/2时，即使施加局域性约束，现有LH与QPF算法的改进空间极其有限，这为量子计算领域这些基础问题划定了精确的算法极限。