Ollivier-Ricci curvature and fast approximation to tree-width in embeddability of QUBO problems
Chi Wang, EDMOND A. JONCKHEERE, Todd A. Brun · 2014
The D-Wave quantum computer is designed to solve a specific class of problems - The Quadratic Unconstrained Binary Optimization (QUBO) problem. One of the key processes in this pathway to the solution consists in embedding the problem graph into a hardware graph. It is a nontrivial task to determine whether a problem graph is minor embeddable in a hardware graph. One method that singles out cases where minor embeddability fails requires calculation of the tree-width of both the problem and the hardware graphs. The latter computation is known to be NP-Complete. In this paper, we propose a novel, fast approximation to tree-width based on the differential geometric concept of Ollivier-Ricci curvature. This latter runs in linear time and thus could significantly reduce the overall complexity of determining whether a QUBO problem is solvable on the D-Wave architecture.