量子科技中心_量科网

受量子启发式概念和平均情况而非最坏情况算法分析的启发，该研究团队基于单个问题实例定义量子计算优势。参考经典柯尔莫哥洛夫复杂性和实例复杂性的概念，研究人员定义了它们的量子版本。这使得该团队能够将诸如可满足性问题、因数分解等计算问题的“眩晕实例”定义为量子实例复杂性显著小于经典实例复杂性的实例——这些实例标志着量子优势：它们在量子计算机上易于求解，但经典算法却举步维艰（它们会感到“眩晕”）。 通过因数分解的规约，该工作证明了眩晕可满足性实例的存在性；具体而言，在合理的复杂性理论假设下，这些实例具有最大眩晕度。进一步研究表明，量子算法的眩晕特性具有指数级算法效用。该理论框架不仅为实践中寻找量子优势提供了指引灯塔，更因其聚焦单个实例的特性，有望催生量子算法设计的新范式。