论文标题
K-SAT和哈密顿周期的算法QUBO公式
Algorithmic QUBO Formulations for k-SAT and Hamiltonian Cycles
论文作者
论文摘要
二次无约束的二进制优化（QUBO）可以看作是一种用于优化问题的通用语言。 Qubos引起了特别的关注，因为它们可以用量子硬件解决，例如量子退火器或运行QAOA的量子门计算机。在本文中，我们介绍了两种新型的Qubo配方，用于$ K $ -SAT和HAMILTON循环，它们比现有方法明显更好。对于$ k $ -sat，我们将Qubo矩阵的增长从$ O（k）$减少到$ O（log（k））$。对于哈密顿循环，矩阵不再在节点数量中二次增长，而是目前，而是在边缘数量和对数中线性地在节点的数量中进行线性增长。 我们介绍这两种公式而不是数学表达式，而是大多数QUBO公式，而是作为促进更复杂的Qubo配方设计并允许在更大且更复杂的Qubo配方中轻松重复使用的元算法。
Quadratic unconstrained binary optimization (QUBO) can be seen as a generic language for optimization problems. QUBOs attract particular attention since they can be solved with quantum hardware, like quantum annealers or quantum gate computers running QAOA. In this paper, we present two novel QUBO formulations for $k$-SAT and Hamiltonian Cycles that scale significantly better than existing approaches. For $k$-SAT we reduce the growth of the QUBO matrix from $O(k)$ to $O(log(k))$. For Hamiltonian Cycles the matrix no longer grows quadratically in the number of nodes, as currently, but linearly in the number of edges and logarithmically in the number of nodes. We present these two formulations not as mathematical expressions, as most QUBO formulations are, but as meta-algorithms that facilitate the design of more complex QUBO formulations and allow easy reuse in larger and more complex QUBO formulations.
