布尔的可满足性问题(SAT)在理论和实践上都很重要。 然而,量子算法的大多数可证明的保证完全依赖于Grover类型的方法,这种方法仅在二次加速时限制了可能的优势,因此寻找超越这种二次障碍的方法成为关键挑战。 从这个角度来看,这项工作对最近推出的测量驱动的量子SAT求解器进行了严格的最坏情况运行时分析。 重要的是,这种量子算法并不完全依赖于Grover类型的方法,并且显示出有希望的数值性能。 我们的分析确定,该算法的运行时取决于两个关键属性之间的指数权衡:相关Hamiltonian的光谱间隙和驾驶测量的成功概率。 我们表明,这种取舍可以通过可调的旋转角度系统地控制。 除了建立最坏情况的运行时表达式外,这项工作还有助于显著的算法改进。 首先,我们开发一个新的读出例程序,即使对于具有多个令人满意的作业的实例,也能有效地找到解决方案。 其次,引入了基于完美哈希家族的测量并行化方案。 第三,我们建立了测量驱动算法的振幅放大版本。 最后,我们展示了框架的实用功能:通过适当调度算法的参数,我们表明它的运行时在一个特殊的SAT实例上从指数级到多项式崩溃,这与它们已知的经典可操作性一致。 我们打开的一个问题是在光谱间隙上建立一个非平凡的下界,作为旋转角的函数。 解决这个问题直接转化为改进的最坏情况的运行时,有可能实现超象量子优势。