Poster 47: Decomposition Algorithms for Scalable Quantum Annealing

Authors: Elijah Pelofske (Los Alamos National Laboratory), Georg Hahn (Harvard University), Hristo Djidjev (Los Alamos National Laboratory)

Abstract: Commercial adiabatic quantum annealers such as D-Wave 2000Q have the potential to solve NP-complete optimization problems efficiently. One of the primary constraints of such devices is the limited number and connectivity of their qubits. This research presents two exact decomposition methods (for the Maximum Clique and the Minimum Vertex Cover problem) that allow us to solve problems of arbitrarily large sizes by splitting them up recursively into a series of arbitrarily small subproblems. Those subproblems are then solved exactly or approximately using a quantum annealer. Whereas some previous approaches are based on heuristics that do not guarantee optimality of their solutions, our decomposition algorithms have the property that the optimal solution of the input problem can be reconstructed given all generated subproblems are solved optimally as well. We investigate various heuristic and exact bounds as well as reduction methods that help to increase the scalability of our approaches.

Best Poster Finalist (BP): no

Poster: PDF
Poster summary: PDF


Back to Poster Archive Listing