量子科技中心_量科网

黑斯廷斯（《量子》2018、2019）提出的短路径量子算法是绝热量子算法的变体，通过避免控制长绝热路径上的能隙，实现了更简便的最坏情况分析。达尔泽尔、潘科蒂、坎贝尔和布兰道（STOC 2023）近期重新审视该框架，针对多类约束满足问题（MAX-k-CSPs）给出了清晰的短路径算法复杂度分析，推导出复杂度为2^(1−c)n/2的量子算法（其中c>0为常数）。该成果曾被认为实现了相对于经典算法的超二次量子优势。 本研究发现，该系列工作中存在一个显式的经典机制框架，并证明其可导向清晰的去量子化方案。由此，研究团队针对同类约束满足问题，获得了时间复杂度为2^(1−c′)n的经典算法（c′>c为常数）。这表明当前针对这些问题的短路径量子算法并未实现超二次优势。从积极角度看，该成果为重要约束满足问题类提供了一种新型"量子启发"式经典算法设计路径。