D-Wave Experimental Results for an Improved QUBO Formulation of the Broadcast Time Problem

Abstract

Quantum computing has been a popular phenomena in Computer Science over the past few decades. More specifically in recent years, the D-Wave, a commercially available quantum computer, has been receiving significant attention due to the fact that it can take in as input non-trivial NP hard problems and produce results of varying accuracy. The broadcast problem is a popular optimization problem of graph theory, it asks if there is an efficient way to spread a message across a network in a given time frame. The main purpose of our efforts is two-fold; To evaluate the capacity of the D-Wave quantum computer to tackle this type of problem. Also to evaluate the current QUBO formulation (a specific presentation of the problem which the D-Wave can solve) of the broadcast problem and compare to a previous formulation. We present here the results as generated by the D-Wave on the current best-known QUBO formulation. We also compare them to the previous results, concluding that indeed the current QUBO formulation of the broadcast problem is more efficient.