Solving the Bounded-Depth Steiner Tree Problem using an Adiabatic Quantum Computer

We propose a quadratic unconstrained binary optimization (QUBO) formulation for the Bounded-Depth Steiner Tree problem suitable for adiabatic quantum computers. The numbers of qubits (dimension of QUBO matrices) required by our formulation is O(|V|3), where |V| represents the number of vertices. A D-Wave 2X computer consisting of 1098 active qubits is evaluated for a selection of known common graphs. Experimental results are shown and discussed. Our results are applicable to the Bounded-Depth Minimum Spanning Tree problem, as a special case.