Scaling of Graph Embedding for Quantum Annealers

Many combinatorial optimization problems are NP-hard, giving significant value to the discovery of efficient quantum solvers. In the context of quantum annealing, problems are expressed in the Ising model, and can be viewed as graphs. Thus an understanding of how such graphs can be embedded in an array of qubits, and how many qubits will be needed, are interesting questions. We review the currently known embedding algorithms, and apply them in a controlled fashion to graphs with a variety of sizes and characteristics, comparing the quality of embeddings and execution time. Multiple topologies for qubit couplings are considered, as well as the effect of defects. We develop analytic models and compare to the experimental results. Our lower bound shows that the qubit count scales linearly with the edge count, and gives a good estimate of the actual qubit requirements for dense graphs, without assuming any particular topology.