Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets

by Kathleen D. Hamilton, Travis S. Humble


Using quantum annealing to solve an optimization problem requires minor embedding a logic graph into a known hardware graph.  In an effort to reduce the complexity of the minor embedding problem, we introdcue the minor set cover (MSC) of a known graph, G: a subset of graph minors which contain any remaining minor of the graph as a subgraph.  Any graph that can be embedded into G will be embeddable into a member of the MSC.  Focusing on embedding into the hardware graph of commercially available quantum annealers, we establish the MSC for a particular known virtual hardware, which is a complete bipartite graph.  We show that the complete bipartite graph KN,N has a MSC of N minors, from which KN+1 is identified as the largest c lique minor of KN,N.  The case of determning the largest clique minor of hardware with faults is briefly discussed but remains an open question.


Read more

Download Publication

Access for Quantum Information Processing subscribers only.

Publication Citation

Quantum Information Processing 2017 pp 94 September 27, 2017
DOI: 10.1007/s11128-016-1513-7