量子科技中心_量科网

可满足性问题（SAT）是计算机科学的核心难题，其求解算法的进步对诸多领域具有深远影响。近期研究提出了基于格罗弗量子搜索算法的量子SAT求解方案。然而这类方法存在关键局限：通常需要预先获知目标布尔公式的可满足赋值数量——而这在多数实际场景中均不可得。量子计数虽可估算该数值，但会产生比格罗弗搜索高出数个数量级的计算开销。本文提出一种基于量子纠缠与等价性验证的新型量子SAT求解器。该方法无需预知解的数量，其计算效率优于量子计数方案。尽管最坏情况下时间复杂度仍呈指数级，但该团队证明对于随机布尔函数，该方法的期望时间复杂度仅为常数阶O(1)。实验结果亦验证了理论主张。