面向布尔可满足性问题的结构约简空间高效量子求解器

《Physical Review A》：Space-efficient quantum solvers for Boolean satisfiability problems via structural reduction

　　布尔可满足性（SAT）问题作为量子优化的核心基准问题，常规编码通常需要为每个活跃变量分配一个量子比特，这限制了其在前端量子硬件上的应用。此处我们提出一种基于决定性链归约算法（DCRA）的空间高效框架，用于求解一三SAT问题，该算法利用了子句诱导的依赖关系。对于由n个变量和m个子句生成的实例，设?n为出现在子句中的活跃变量数量。DCRA识别s个初始变量，并将剩余的?n?s个活跃变量表示为这些初始变量的线性组合，从而将有效搜索空间从2?n缩减至2s。对于临界区域附近的随机正实例，我们经验性地发现s接近?n?m，从而带来显著的量子比特节省。在缩减空间中，我们推导出一个紧凑的二次无约束二值优化（QUBO）公式，其问题哈密顿量为量子退火（QA）、量子绝热算法（QAA）和量子近似优化算法（QAOA）提供了通用输入。数值模拟验证了该框架在处理多达150个变量的QA求解器实例和多达50个变量的QAA及QAOA实现实例中的有效性。对于基于QA的求解器，对最多200个变量的可满足正随机实例的有限尺寸标度显示，平均成功概率呈近似指数衰减，并揭示了量子比特缩减与退火难度之间的子句密度依赖性权衡。在超导处理器上，六量子比特的QAOA求解了一个包含?n=21个活跃变量的25变量实例，取得了12.62%的成功率，高于4.69%的均匀采样基线。对于一个13变量的实例，DCRA测得的成功概率为3.37%，而在相同射击预算下直接编码的成功率仅为0.05%。这些结果表明，利用结构特性的归约为近端硬件上实现量子比特高效的量子可满足性问题公式提供了一条实用途径。