论文标题
用量子近似优化算法解决布尔值的满足性问题
Solving boolean satisfiability problems with the quantum approximate optimization algorithm
论文作者
论文摘要
量子近似优化算法（QAOA）是近期量子计算的最突出的应用之一。在这里，我们研究了QAOA解决硬性约束满意度问题的能力，而不是优化问题。我们以随机$ k $ -sat的形式着重于基本的布尔满意度问题。由于变量$ n $的数量流向无穷大，我们对QAOA对随机布尔公式的平均成功概率的平均成功概率开发了分析界。固定参数的界限和$ k $是2的功率时。我们对这些理论结果进行了补充，并获得了针对小$ n $的QAOA性能的数值结果，这表明这些结果与限制的理论界限匹配。然后，我们使用这些结果将QAOA与领先的经典求解器进行比较。在随机8-SAT的情况下，我们发现，对于大约14个Ansatz层，QAOA与我们测试的最高绩效经典求解器的缩放性能相匹配。对于大量的层，QAOA的表现优于Walksatlm，其最终优势水平仍有待确定。我们的方法提供了一个框架，用于分析QAOA的性能，以解决严格的约束满意度问题，并在经典算法上找到进一步的加速。
The quantum approximate optimization algorithm (QAOA) is one of the most prominent proposed applications for near-term quantum computing. Here we study the ability of QAOA to solve hard constraint satisfaction problems, as opposed to optimization problems. We focus on the fundamental boolean satisfiability problem, in the form of random $k$-SAT. We develop analytic bounds on the average success probability of QAOA over random boolean formulae at the satisfiability threshold, as the number of variables $n$ goes to infinity. The bounds hold for fixed parameters and when $k$ is a power of 2. We complement these theoretical results with numerical results on the performance of QAOA for small $n$, showing that these match the limiting theoretical bounds closely. We then use these results to compare QAOA with leading classical solvers. In the case of random 8-SAT, we find that for around 14 ansatz layers, QAOA matches the scaling performance of the highest-performance classical solver we tested, WalkSATlm. For larger numbers of layers, QAOA outperforms WalkSATlm, with an ultimate level of advantage that is still to be determined. Our methods provide a framework for analysing the performance of QAOA for hard constraint satisfaction problems and finding further speedups over classical algorithms.
