Abstract:
In this paper we present for the first time quantum annealing solutions for densest
k-subgraph problems which have many applications in computational biology. Our
solutions are formulated as solutions for Quadratic Unconstrained Binary Optimisa-
tion and Integer Programming problems, proved to be equivalent with the densest
k-subgraph problems and then tested on an D-Wave 2X machine. The QUBO formu-
lations are optimal in terms of the number of logical qubits, but require the highest
number of physical qubits after embedding. Experimental work reported here suggests
that the D-Wave 2X model cannot handle problems of this difficulty. The next genera-
tion of D-Wave hardware architecture|the Pegasus architecture|is much denser than
the current one, so dense QUBOs will be easier to embed. The experimental work also
suggests that the current built-in post-processing optimisation method does not work
very well for some problems and the default setting (post-processing optimisation on)
should be avoided (or at least tested before being turned on).