  The recent availability of the first commercial quantum computers has
provided a promising tool to tackle NP hard problems which can only be solved
heuristically with present techniques. However, it is unclear if the current
state of quantum computing already provides a quantum advantage over the
current state of the art in classical computing. This article assesses the
performance of the D-Wave 2X quantum annealer on two NP hard graph problems, in
particular clique finding and graph partitioning. For this, we provide
formulations as Qubo and Ising Hamiltonians suitable for the quantum annealer
and compare a variety of quantum solvers (Sapi, QBSolv, QSage provided by
D-Wave Sys, Inc.) to current classical algorithms (METIS, Simulated Annealing,
third-party clique finding and graph splitting heuristics) on certain test sets
of graphs. We demonstrate that for small graph instances, classical methods
still outperform the quantum annealer in terms of computing time, even though
the quality of the best solutions obtained is comparable. Nevertheless, due to
the limited problem size which can be embedded on the D-Wave 2X chip, the
aforementioned finding applies to most of problems of general nature solvable
on the quantum annealer. For instances specifically designed to fit the D-Wave
2X architecture, we observe substantial speed-ups in computing time over
classical approaches.
