Quantum Annealing XORSAT on Dilute Square Lattices*

Here we show how we can embed the 3-regular 3-XORSAT on a square lattice made out of gates
which couple the bits in a manner that recreates the constraints. This system can be annealed to the
solution by tuning a transverse field to zero. We explore ways to avoid two potential obstacles that
limit how fast one can anneal this system; the first is the nature of the phase transition as we tune
the transverse field and the second is the avoided level crossings for small transverse field strength.
We discuss how the second pitfall can possibly be avoided in the lattice and other embeddings
which have already been studied. We also present Quantum Monte Carlo results on the nature of
the phase transition for the embedding of XORSAT on the square lattice. We compare the results
to the embedding on a random regular graph, where the phase transition is known to be first order.
We also show that different XORSAT problems result in lattice arrangements which exhibit a phase
transition whose order is closely related to the classical complexity of the particular problem.