  Quantum annealers (QAs) are specialized quantum computers that minimize
objective functions over discrete variables by physically exploiting quantum
effects. Current QA platforms allow for the optimization of quadratic
objectives defined over binary variables (qubits), also known as Ising
problems. In the last decade, QA systems as implemented by D-Wave have scaled
with Moore-like growth. Current architectures provide 2048 sparsely-connected
qubits, and continued exponential growth is anticipated, together with
increased connectivity. We explore the feasibility of such architectures for
solving SAT and MaxSAT problems as QA systems scale. We develop techniques for
effectively encoding SAT -and, with some limitations, MaxSAT- into Ising
problems compatible with sparse QA architectures. We provide the theoretical
foundations for this mapping, and present encoding techniques that combine
offline Satisfiability and Optimization Modulo Theories with on-the-fly
placement and routing. Preliminary empirical tests on a current generation
2048-qubit D-Wave system support the feasibility of the approach for certain
SAT and MaxSAT problems.
