量子科技中心_量科网

局域哈密顿量（LH）问题是Kitaev提出的典型𝖰𝖬𝖠完全问题。本文以极强的方式证明了该问题的计算难度：在强指数时间假设（SETH）下，对于任意ε>0，n量子比特的3-局域哈密顿量问题无法在经典计算机上以O(2^(1-ε)n)时间求解；在量子强指数时间假设（QSETH）下，对于任意ε>0，该问题也无法在量子计算机上以O(2^(1-ε)n/2)时间求解。这些下界表明，当前已知的经典与量子LH算法难以被显著改进。此外，该研究团队还证明了具有任意常数相对误差的量子配分函数（QPF）近似计算的精细复杂度下界。已知QPF的相对误差近似等价于对𝖰𝖬𝖠问题解空间维度的近似计数。研究人员展示了在SETH和QSETH假设下，以常数相对误差估计QPF具有计算困难性。随后该工作提出了一个针对任意1/poly(n)相对误差、运行时间为O(2^n)的量子算法，不仅匹配了上述下界，还在低温区域改进了Bravyi、Chowdhury、Gosset和Wocjan（《自然·物理学》2022）提出的当前最优算法。为证明这些精细下界，该团队首次提出了保持系统规模不变的量子电路-哈密顿量映射构造：将作用于N个量子比特的T时间量子计算，编码为作用于N+O(T^(1/d))个量子比特的(d+1)-局域哈密顿量。这一构造优于基于一元时钟标准方案（需使用N+O(T)个量子比特）的传统方法。