Effectiveness of quantum annealing pause and partial gauges on embedded degree-bounded minimum spanning tree problems*

Robust communication networks are essential to the growing use of small Unmanned Aerial Systems (sUAS) technologies. This work focused on evaluating the potential for harnessing quantum annealing to optimize communication routing in UAS communication networks subject to constraints. To support experimentation on early hardware, we consider as a surrogate problem finding the minimum degree-bounded spanning tree within a communication graph. While finding the minimum spanning tree is computationally tractable, with bounds on the degree the problem becomes NP hard. We provide a mapping of the degree-bounded minimum spanning tree problem to a Quantum Unconstrained Binary Optimization problem, and report on results demonstrating the effectiveness of an annealing pause on these embedded problem instances. Lastly, we demonstrate the effectiveness of partial gauge transformation for situations where asymmetric parameter ranges make standard gauge transformation infeasible.