  Quantum annealing provides a promising route for the development of quantum
optimization devices, but the usefulness of such devices will be limited in
part by the range of implementable problems as dictated by hardware
constraints. To overcome constraints imposed by restricted connectivity between
qubits, a larger set of interactions can be approximated using minor embedding
techniques whereby several physical qubits are used to represent a single
logical qubit. However, minor embedding introduces new types of errors due to
its approximate nature. We introduce and study quantum annealing correction
schemes designed to improve the performance of quantum annealers in conjunction
with minor embedding, thus leading to a hybrid scheme defined over an encoded
graph. We argue that this scheme can be efficiently decoded using an energy
minimization technique provided the density of errors does not exceed the
per-site percolation threshold of the encoded graph. We test the hybrid scheme
using a D-Wave Two processor on problems for which the encoded graph is a
2-level grid and the Ising model is known to be NP-hard. The problems we
consider are frustrated Ising model problem instances with "planted" (a priori
known) solutions. Applied in conjunction with optimized energy penalties and
decoding techniques, we find that this approach enables the quantum annealer to
solve minor embedded instances with significantly higher success probability
than it would without error correction. Our work demonstrates that quantum
annealing correction can and should be used to improve the robustness of
quantum annealing not only for natively embeddable problems, but also when
minor embedding is used to extend the connectivity of physical devices.
