标题： 满足性问题（SAT）、小工具（Gadgets）、最大2约束满足问题（Max2XOR）和量子退火机 显示英文标题

标题： SAT, Gadgets, Max2XOR, and Quantum Annealers

摘要： 量子退火器基本上是一种量子计算机，它以高概率在常数时间内优化某些关于布尔变量的二次函数。 这些函数本质上是Ising模型的哈密顿量，在退火过程后有很高的概率达到基态能量。 它们被提出作为一种解决SAT问题的方法。 这些哈密顿量可以看作是Max2XOR问题，即寻找一种赋值，使得最多包含两个变量的XOR子句中满足的数量最大化的问题。 在本文中，我们提出了几个小工具来将SAT问题约化为Max2XOR问题。 我们展示了如何使用它们将SAT实例转换为量子退火器的初始配置。 显示英文摘要

摘要： Quantum Annealers are basically quantum computers that with high probability can optimize certain quadratic functions on Boolean variables in constant time. These functions are basically the Hamiltonian of Ising models that reach the ground energy state, with a high probability, after an annealing process. They have been proposed as a way to solve SAT. These Hamiltonians can be seen as Max2XOR problems, i.e. as the problem of finding an assignment that maximizes the number of XOR clauses of at most 2 variables that are satisfied. In this paper, we present several gadgets to reduce SAT to Max2XOR. We show how they can be used to translate SAT instances to initial configurations of a quantum annealer.