Abstract:
The D-Wave system architecture is designed to deal with quantum annealing to solve computational problems. To run or solve a problem by the D-Wave hardware, we need to rst transform the problem into an Ising or Quadratic Unconstrained Binary Optimization (QUBO) instance, then embed Hamiltonians (logical qubit relationships) onto the actual D-Wave hardware which is currently based on Chimera graphs (physical qubit couplings). In order to have better performance of D-Wave's quantum annealing, an efficient algorithm to nd good embeddings needs to be obtained. In this paper, we present some heuristic algorithms for minor embedding an arbitrary guest graph onto a host Chimera graph. Our implementations show these new algorithms are practical for sparse graphs with hundreds of vertices. In general, for a given minor embedding, we tried to minimize the maximum number physical qubits representing by any logical qubit and/or the total number of physical qubits used.