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

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

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 introduce 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 clique minor of KN , N. The case of determining the largest clique minor of hardware with faults is briefly discussed but remains an open question.

Original languageEnglish
Article number94
JournalQuantum Information Processing
Volume16
Issue number4
DOIs
StatePublished - Apr 1 2017

Funding

This work was supported by the US Department of Defense and used resources of the Computational Research and Development Programs at Oak Ridge National Laboratory. This manuscript has been authored by UT-Battelle, LLC, under Contract No. DE-AC0500OR22725 with the US Department of Energy. The US Government retains and the publisher, by accepting the article for publication, acknowledges that the US Government retains a non-exclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this manuscript, or allow others to do so, for the US Government purposes. The Department of Energy will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan.

Keywords

  • Adiabatic quantum computing
  • Clique minor
  • Graph theory
  • Minor embedding
  • Quantum annealing

Fingerprint

Dive into the research topics of 'Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets'. Together they form a unique fingerprint.

Cite this