Minor-embedding of a non-fully connected graph

The maximum fully-connected graph that can be embedded onto a chimera graph has V nodes, where V = 1+L min(M,N), as explained here. This means that the largest K_v that can be embedded onto the DW2000Q is K65.

How does that change if we want to embed a graph that is not fully connected? How many nodes can we embed onto a DW2000Q if the graph is sparse? In other words, how does the formula V = 1+L min(M,N) change for sparse graphs?




1 comment
  • A sparse graph can use anywhere from 1 to the maximum number of available qubits. It really depends on your particular graph. 

    One example of a sparse graph that embeds well onto D-Wave's QPU is a 32 x 32 grid. That graph has 1024 nodes. Each node is embedded onto two qubits. Chimera graphs are also sparse graphs that embed well. They have 2048 nodes. Other graphs will be much more difficult to embed. 

    The minorminer tool in Ocean can help with embedding a graph onto the QPU. Here's a link to the documentation:


    I hope that helps!

    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post