Journal
QUANTUM INFORMATION PROCESSING
Volume 16, Issue 4, Pages -Publisher
SPRINGER
DOI: 10.1007/s11128-016-1513-7
Keywords
Minor embedding; Adiabatic quantum computing; Quantum annealing; Clique minor; Graph theory
Funding
- US Department of Defense
- Computational Research and Development Programs at Oak Ridge National Laboratory
- UT-Battelle
- LLC [DE-AC0500OR22725]
- US Department of Energy
Ask authors/readers for more resources
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 K-N,K-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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available