量子科技中心_量科网

量子计算机在指数级小空间内模拟大规模经典系统已引起关注。先前研究表明，在模拟具有长程相互作用的经典动力学时，量子算法相比任何经典算法都能实现指数级加速。然而现实中的许多经典系统（如偏微分方程描述的体系）仅存在局域相互作用。在此条件下量子算法是否仍能保持指数加速优势？本研究系统刻画了模拟这类几何局域系统时量子算法的计算复杂度：首先，该团队实现了此类系统短时（多项式时间）动力学模拟量子算法的经典化重构，证明该模拟问题无法产生任何量子指数优势；其次，揭示了短时动力学量子算法与多项式时间概率经典计算具有相同复杂度；最后，论证了长时（指数时间）动力学量子算法的复杂度可由指数时间-多项式空间量子计算刻画。这表明在限定多项式空间时存在超多项式时间优势，否则将获得指数级空间优势。该研究为偏微分方程支配的经典动力学复杂度提供了新认知，为实际问题中实现量子优势开辟了路径。