Embedding parameters for Quantum Annealing

Many optimization problems are defined on highly connected graphs and many interesting physical spin-glass systems are featuring long-range interactions. One method to solve for the optimum/ground state is quantum annealing (QA). Most architectures for QA devices, manufactured or proposed, are based on optimizing Hamiltonians having spins connected in a non-complete graph, with nodes with a small maximum degree, compared to the requirements. To overcome this limitation 'embedding' is employed: the native graph is ‘tiled’ with ferromagnetic chains of spins that now are meant to represent the logical binary variables. While it is known how the strength of the ferromagnetic bonds can ensure that the classical Ising ground state of the embedded system can be univocally mapped to the ground state of the original system, there is very little study on the impact of these parameters on QA. Programmers have taken conservative choices for the parameters and the common practices can be improved. Starting from the physics of connected ferromagnetic Ising chains, we will review several parameter choices and discuss previous and new results obtained on the D-Wave 2X machine, on carefully designed problems that allow to isolate and evaluate the role of connectivity in embedded systems.