XiaoMi-AI文件搜索系统
World File Search System合取范式
Lightsolver 挑战领先的深度学习求解器来解决 Max-2-SAT 问题
大量具有重大社会、经济和科学意义的现实问题都可以表示为组合优化任务。组合优化方面的进步使得运输系统、供应链、资源管理等更加高效 [1、2、3、4、5]。在本文中，我们考虑经典的最大 2-可满足性（MAX-2-SAT）问题 [6]，该问题在调度或资源分配任务中普遍存在，这只是其中的一些应用 [7]。假设给定一组 N 个二进制变量 x = (x1, x2, ..., xN) 和一组 C 个约束（或子句），每个子句有两个变量，它们形成布尔公式 F(x)。我们的目标是为每个变量 xi 分配一个二进制值，使得最大数量的子句得到满足。我们考虑的布尔公式 F(x) 采用合取范式，由子句的合取（逻辑与）组成，其中每个子句都是文字的析取（逻辑或）。例如，公式
在经典和量子计算平台上估计布尔可满足性问题的状态密度
给定一个合取范式 (CNF) 中的布尔公式 φ (x)，状态密度计算对于所有 e 值，恰好违反 e 个子句的变量分配的数量。因此，状态密度是所有可能分配中未满足子句数量的直方图。这种计算概括了最大可满足性 (MAX-SAT) 和模型计数问题，不仅可以洞察整个解空间，还可以衡量问题实例的难度。因此，在现实世界中，即使使用最先进的算法，这个问题通常也是不可行的。虽然找到这个问题的确切答案是一项计算密集型任务，但我们提出了一种基于测度不等式集中度来估计状态密度的新方法。该方法产生了二次无约束二进制优化 (QUBO)，这特别适用于基于量子退火的解决方案。我们介绍了总体方法，并将 D-Wave 量子退火器的结果与最著名的经典算法（如 Hamze-de Freitas-Selby (HFS) 算法和可满足性模理论 (SMT) 求解器）进行了比较。
关于布尔函数和实函数作为量子计算汉密尔顿函数的表示
将位上的函数映射到作用于量子位上的汉密尔顿量在量子计算中有许多应用。特别是，表示布尔函数的汉密尔顿量对于将量子退火或量子近似优化算法应用于组合优化问题是必不可少的。我们展示了这些函数如何自然地用汉密尔顿量来表示，这些汉密尔顿量是泡利 Z 算子（伊辛自旋算子）的和，和的项对应于函数的傅里叶展开。对于许多由紧凑描述给出的布尔函数类，例如给出可满足性问题实例的合取范式布尔公式，计算其汉密尔顿量表示是 #P 难，即与计算其满足分配的数量一样难。另一方面，构造表示实函数的汉密尔顿量（例如每个作用于固定数量的位的局部布尔子句之和）通常不存在这种困难，这在约束满足问题中很常见。我们展示了组合规则，通过将表示更简单子句的汉密尔顿算子组合为构建块，明确构造表示各种布尔函数和实函数的汉密尔顿算子，这些规则特别适合直接实现为经典软件。我们进一步将结果应用于受控酉算子的构造，以及在辅助量子比特寄存器中计算函数值的算子的特殊情况。最后，我们概述了我们的结果在量子优化算法中的几个其他应用和扩展。这项工作的目标是提供一个量子优化设计工具包，专家和从业者都可以使用它来构建和分析新的量子算法，同时为文献中出现的各种构造提供一个统一的框架。