量子科技中心_量科网

布尔可满足性问题（SAT）在理论与实践领域均具有核心地位。然而，现有量子算法的可证明优势主要依赖于Grover类方法，其加速上限仅为二次方突破，这使得寻找超越该限制的算法成为关键挑战。有鉴于此，该研究团队对近期提出的测量驱动型量子SAT求解器进行了严格的最坏情况时间复杂度分析。值得注意的是，该量子算法不仅依赖Grover类方法，其数值模拟性能也表现出色。分析表明，算法运行时间取决于两个关键特性的指数级权衡：关联哈密顿量的谱间隙与驱动测量的成功概率。研究证实，这种权衡可通过可调旋转角进行系统控制。 除建立最坏情况时间复杂度表达式外，该工作还实现了多项算法改进：首先，开发了新型读取程序，可高效求解含多组满足赋值的问题实例；其次，基于完美哈希族提出了测量并行化方案；第三，构建了测量驱动算法的振幅放大版本；最后，通过合理调度算法参数，证明该框架在特定SAT问题类上可将指数级运行时间降为多项式级，这与该类问题的经典可解性特征一致。尚待解决的开放问题是建立旋转角函数的非平凡谱间隙下界——该问题的解决将直接改进最坏情况时间复杂度，有望实现超二次量子优势。