Performance of quantum annealing under different Ising mappings and graph embeddings

To apply quantum annealing (QA) to solve optimization problems, an Ising Hamiltonian must be derived that encodes the sought solution in its ground state, while respecting QA hardware constraints. In general, there are a variety of ways to obtain a Hamiltonian with quadratic spin interactions from a given problem (mapping), and to derive from it a Hamiltonian that fits the hardware graph (embedding). The probability quantum annealing finds the ground state depends on the spectral and relaxation properties of the quantum spin model derived from these mapping and embedding procedures. In this work, we classify mappings and embeddings into categories and we perform a rigorous study of these families on the performance of QA on the D-Wave II quantum annealer to check the validity of theoretical hypotheses. We also discuss the effect of noise on this performance under different choices. Our test set includes a collection of hard combinatorial optimization problems arising in the field of operational planning. Our results illustrate ways in which the efficacy of quantum annealing depends on both the mapping and the embedding, and paves the way to the formulation of general prescriptions for how to encode fruitfully combinatorial optimization problems into quantum annealers.