The Boolean satisfiability problem (SAT) is of central importance in both theory and practice. Yet, most provable guarantees for quantum algorithms rely exclusively on Grover-type methods that cap the possible advantage at only quadratic speed-ups, making the search for approaches that surpass this quadratic barrier a key challenge. In this light, this work presents a rigorous worst-case runtime analysis of a recently introduced measurement-driven quantum SAT solver. Importantly, this quantum algorithm does not exclusively rely on Grover-type methods and shows promising numerical performance. Our analysis establishes that the algorithm's runtime depends on an exponential trade-off between two key properties: the spectral gap of the associated Hamiltonian and the success probability of the driving measurements. We show that this trade-off can be systematically controlled by a tunable rotation angle. Beyond establishing a worst-case runtime expression, this work contributes significant algorithmic improvements. First, we develop a new readout routine that efficiently finds a solution even for instances with multiple satisfying assignments. Second, a measurement parallelization scheme, based on perfect hash families, is introduced. Third, we establish an amplitude-amplified version of the measurement-driven algorithm. Finally, we demonstrate the practical utility of our framework: By suitably scheduling the algorithm's parameters, we show that its runtime collapses from exponential to polynomial on a special class of SAT instances, consistent with their known classical tractability. A problem we leave open is to establish a non-trivial lower bound on the spectral gap as a function of the rotation angle. Resolving this directly translates into an improved worst-case runtime, potentially realizing a super-quadratic quantum advantage.

翻译：布尔可满足性问题（SAT）在理论与实践层面均具有核心重要性。然而，现有量子算法的可证明性能保证主要依赖于Grover型方法，其优势上限仅为二次加速，因此探索突破该二次屏障的算法成为关键挑战。鉴于此，本文对近期提出的一种测量驱动量子SAT求解器进行了严格的最坏情况运行时分析。该量子算法不完全依赖Grover型方法，并展现出良好的数值性能。我们的分析表明，算法运行时间取决于两个关键特性之间的指数权衡：关联哈密顿量的谱间隙与驱动测量的成功概率。我们证明该权衡可通过可调旋转角进行系统性调控。除建立最坏情况运行时表达式外，本研究还提出了重要的算法改进：首先，开发了一种新型读出流程，能高效求解具有多个可满足赋值的实例；其次，基于完美哈希族引入了测量并行化方案；第三，构建了测量驱动算法的振幅放大版本；最后，通过合理调度算法参数，我们证明在特定SAT实例类上（其经典可解性已知），算法运行时间可从指数级坍缩至多项式级。一个待解决的开放问题是建立谱间隙关于旋转角的非平凡下界，该问题的解决将直接转化为改进的最坏情况运行时，并可能实现超二次量子优势。