Minor embedding: an application in quantum annealing*

Minor embedding is the embedding of a logical graph as a minor of another graph representing a real quantum annealing device. In the embedded graph each logical qubit is represented by a tree of ferromagnetically-coupled physical qubits.
Choi’s work gives bounds on the magnitude of the ferromagnetic coupling needed to preserve the ground state spin configuration. We have developed a new method for determining tighter bounds on this magnitude, which in turn should result in fewer errors from thermal noise. Moreover, we prove that our bound is the best bound under some conditions.
We have confirmed this result by experimenting on the D-Wave annealer. Since this machine is an open quantum system, the probability of finding the ground state of the embedded problem is maximized when the ferromagnetic coupling strength is set to be equal to the calculated best bound. Our result will likely lead to improved performance for a wide variety of optimization problems with higher degree than can be directly implemented on quantum annealing hardware.