在破碎的Chimera和Pegasus图中嵌入的小嵌入是NP完成的 (Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete)

The embedding is an essential step when calculating on the D-Wave machine. In this work we show the hardness of the embedding problem for both types of existing hardware, represented by the Chimera and the Pegasus graphs, containing unavailable qubits. We construct certain broken Chimera graphs, where it is hard to find a Hamiltonian cycle. As the Hamiltonian cycle problem is a special case of the embedding problem, this proves the general complexity result for the Chimera graphs. By exploiting the subgraph relation between the Chimera and the Pegasus graphs, the proof is then further extended to the Pegasus graphs.

翻译：在计算 D- Wave 机器时,嵌入是一个重要的步骤。在这项工作中, 我们显示了以Chimera 和Pegasus 图形为代表的两种现有硬件嵌入问题的艰巨性, 这两种硬件都含有无法找到的qubts。我们建造了某些破碎的 Chimera 图形, 在那里很难找到汉密尔顿周期。汉密尔顿周期问题是嵌入问题的一个特殊案例, 这证明了Chimera 图形的总体复杂性。通过利用Chimera 和 Pegas 图形之间的子图关系, 证据被进一步扩展至 Pegas 图表。