Pattern QUBOs: Algorithmic construction of 3SAT-to-QUBO transformations

Understand

3SAT instances need to be transformed into instances of Quadratic Unconstrained Binary Optimization (QUBO) to be solved on a quantum annealer.

• Although it has been shown that the choice of the 3SAT-to-QUBO transformation can impact the solution quality of quantum annealing significantly, currently only a few 3SAT-to-QUBO transformations are known.
• Additionally, all of the known 3SAT-to-QUBO transformations were created manually (and not procedurally) by an expert using reasoning, which is a rather slow and limiting process.
• In this paper, we will introduce the name Pattern QUBO for a concept that has been used implicitly in the construction of 3SAT-to-QUBO transformations before.