Scholarlink

<p>Quantum annealers are presented as quantum computers that can, with a high probability, 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. In some preliminary works, 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 two variables that are satisfied. In this paper, we focus on introducing 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

SAT, gadgets, Max2XOR, and quantum annealers

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年10月15日

查看全文
  • Carlos Ansótegui,
  • Jordi Levy

摘要

Quantum annealers are presented as quantum computers that can, with a high probability, 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. In some preliminary works, 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 two variables that are satisfied. In this paper, we focus on introducing 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.