Practical Evaluation of the Optimal Embedded Ising Problem

Suitable Ising problems for quantum annealers need to be formulated such that they respect the specific hardware restrictions and at the same time represent the original problems which shall actually be solved. This requires to find an embedding into the hardware graph and choose the parameters of the embedded Ising problem in accordance with the precision of the machine. We have developed a method to provide provably equivalent embedded Ising problems with optimal parameters for a given arbitrary Ising problem and a corresponding embedding. The thus formulated optimal embedded Ising problems are compared to the state-of-the-art embedding transformation implemented in the D-Wave API. We investigate the Ising formulations in different scenarios to evaluate the performance of both methods. Meanwhile, we study the influence of the gap parameter of the optimality method. Although in theory, any positive value for this gap parameter suffices for the equivalence of the original and the embedded problem, i.e., for separating the feasible embedded solutions from the infeasible ones, the effective gap for practical setups differs. We show that our method provides better embedded Ising problems for certain constellations in terms of a better coefficient structure of the embedded Ising problem and of a larger success probability in finding the optimal solution of the original problem. The latter is the key factor from the users' point of view for using quantum annealers to solve their problems.