A Method for Embedding QUBO Problems on Adiabatic Quantum Computers

Adiabatic quantum computers like the D-Wave 2000Q quantum computer can potentially solve the QUBO problem, which is an NP-Hard problem. Solving the QUBO problem literally means solving virtually any NP-Hard problem like the Traveling Salesman Problem (TSP), Airline Scheduling Problem, Protein Folding Problem, Genotype Imputation Problem etc., thereby enabling significant scientific progress, and potentially saving millions / billions of dollars in logistics, airlines and many other industries. However, before we solve QUBO problems on quantum computers, they must be embedded (or compiled) onto the hardware of quantum computers, which in itself is a very hard problem. In this work, we propose an efficient embedding algorithm, that lets us embed QUBO problems fast, uses less qubits and gets the objective function value closer to the global minimum value. We then compare the performance of our embedding algorithm to that of D-Wave’s embedding algorithm, which is the current state of the art, and show that our embedding algorithm convincingly outperforms D-Wave’s embedding algorithm.

---

---