  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. We
will provide an in-depth explanation for the idea behind Pattern QUBOs and show
its importance by proposing an algorithmic method that uses Pattern QUBOs to
create new 3SAT-to-QUBO transformations automatically. As an additional
application of Pattern QUBOs and our proposed algorithmic method, we introduce
approximate 3SAT-to-QUBO transformations. These transformations sacrifice
optimality but use significantly fewer variables (and thus physical qubits on
quantum hardware) than non-approximate 3SAT-to-QUBO transformations. We will
show that approximate 3SAT-to-QUBO transformations can nevertheless be very
effective in some cases.
