量子科技中心_量科网

该研究团队构建了一个由指数级大规模图的Perron-Frobenius特征向量诱导的概率分布，该分布无法被任何经典算法高效采样——即使提供最优预热分布作为初始条件。在量子计算框架下，该问题可视为在给定引导态条件下制备随机哈密顿量的基态，已知量子计算机能高效解决此类问题。这一结果表明，经典算法无法高效解决广泛的随机基态问题类别。 该团队基于高度数、高围长谱扩张图构建了特殊图结构，并在其上附加自相似树结构。该工作继承并拓展了Gilyén、Hastings和Vazirani的研究成果（发表于《Quantum》2021和STOC 2021会议），其原工作证伪了特定随机绝热路径算法的去量子化可能性。本研究通过彻底排除经典算法实现引导基态制备的可能性，显著强化了前人结论。