Presentation
Poster 47: Decomposition Algorithms for Scalable Quantum Annealing
SessionResearch Posters Display
Event Type
Posters
Research Posters
TP
EX
EXH
TimeThursday, 21 November 20198:30am - 5pm
LocationE Concourse
DescriptionCommercial 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.
Archive