The Embedding Problem

Lobe, Elisabeth

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.

Travis Norsen

Art Hobson

Mohammad Kashfi Haghighi, N.J. Dimopoulos

With the current progress of quantum computing, quantum annealing is being introduced as a powerful method to solve hard computational problems. In this paper, we study the potential capability of quantum annealing in solving the phase unwrapping problem, an instance of hard computational problems. To solve the phase unwrapping problem using quantum annealing, we deploy the D-Wave Advantage machine which is currently the largest available quantum annealer. The structure of this machine, however, is not compatible with our problem graph structure. Consequently, the problem graph needs to be mapped onto the target (Pegasus) graph, and this embedding significantly affects the quality of the results. Based on our experiment and also D-Wave's reports, the lower chain lengths can result in a better performance of quantum annealing. In this paper, we propose a new embedding algorithm that has the lowest possible chain length for embedding the graph of the phase unwrapping problem onto the Pegasus graph. The obtained results using this embedding strongly outperform the results of Auto-embedding provided by D-Wave. Besides the phase unwrapping problem, this embedding can be used to embed any subset of our problem graph to the Pegasus graph.

Elisabeth Lobe, Volker Kaibel

Abstract One of the central applications for quantum annealers is to find the solutions of Ising problems. Suitable Ising problems, however, need to be formulated such that they, on the one hand, respect the specific restrictions of the hardware and, on the other hand, represent the original problems which shall actually be solved. We evaluate sufficient requirements on such an embedded Ising problem analytically and transform them into a linear optimization problem. With an objective function aiming to minimize the maximal absolute problem parameter, the precision issues of the annealers are addressed. Due to the redundancy of several constraints, we can show that the formally exponentially large optimization problem can be reduced and finally solved in polynomial time for the standard embedding setting where the embedded vertices induce trees. This allows to formulate provably equivalent embedded Ising problems in a practical setup.