Use an embedded complete graph as the starting graph for minorminer embedding

In my problem, there are 41 logical qubits and they do not form a complete graph. However, assuming that they form a complete graph, I used find_clique_embedding:

embedding = find_clique_embedding(k=41,m=16,target_edges=DW_target_edgelist)

Now since my actual graph is not complete, I want to supply the embedding above for minorminer.find_embedding as the starting graph so that the max chain length can be reduced further. How can I do that? I checked the documentation:

https://docs.ocean.dwavesys.com/projects/system/en/stable/reference/generated/minorminer.find_embedding.html

I think I somehow have to make the embedding as

initial_chains

but I am still not sure is this right and what is the specific format for initial_chains.

0

Comments

3 comments
  • Hello,

    You can run the above described example like this:

    J={(0,1):1,(0,2):1,(0,3):1,(0,4):1,(0,5):1,(1,4):1,(1,5):1,(2,3):1,(2,4):1,(4,5):1,(0,6):1,(2,6):1,(3,6):1,(4,6):1,}
    solver = DWaveSampler()
    __, target_edgelist, target_adjacency = solver.structure
    clique_embedding = find_clique_embedding(7, 16, 16)
    minorminer.find_embedding(J,target_edgelist)

    Here are the results I got:

    >>> clique_embedding
    {0: [1548, 1544, 1672], 1: [1549, 1545, 1673], 2: [1550, 1546, 1674], 3: [1551, 1547, 1675], 4: [1676, 1684, 1680], 5: [1677, 1685, 1681], 6: [1678, 1686, 1682]}

    >>> minorminer.find_embedding(J,target_edgelist, initial_chains=clique_embedding)
    {0: [1679, 1672], 1: [1545, 1673, 1551], 2: [1677, 1685], 3: [1547, 1675], 4: [1684, 1676], 5: [1683, 1687], 6: [1678, 1674]}

    Output:

    >>> minorminer.find_embedding(J,target_edgelist)
    {0: [691, 563, 694], 1: [565], 2: [693], 3: [689], 4: [690, 562], 5: [564, 560], 6: [692, 688]}
    >>> clique_embedding
    {0: [708, 704, 576], 1: [709, 705, 577], 2: [710, 706, 578], 3: [711, 707, 579], 4: [580, 588, 584], 5: [581, 589, 585], 6: [582, 590, 586]}
    >>> minorminer.find_embedding(J,target_edgelist, initial_chains=clique_embedding)
    {0: [583, 591, 578], 1: [587], 2: [577, 581], 3: [582], 4: [588, 580], 5: [589, 585], 6: [579]}

    As you can see, some of the chains are indeed shorter.
    That said, I don't believe this stops the graph from using other nodes not included in the initial clique, though it does come close.

    Also note that you will need to choose a clique embedding that is the right size, in this case 7, to account for all of the nodes in the graph, in this case nodes 0 to 6 (there are 7 of them).

    This is one way of finding an embedding, but it seems like you might be better off just using the minorminer.find_embedding function.

    You would just run it like:

    >>> mm.find_embedding(J,target_edgelist)
    {0: [207, 215, 208], 1: [214, 206], 2: [211], 3: [200, 205], 4: [201], 5: [204, 212], 6: [210, 213]}

    This would not allow you to define the starting graph nodes though, so the first method gives you a little more control over that.

    It is also probably not possible to reduce chain lengths of a clique embedding without some shifting, as the middle link of a chain might be the "extra" qubit.

    Since this qubit then just acts as a means of the outer qubits to be coherent with one another, the best way would be to get rid of it, but then you would need to connect the outer qubits to each other, which would require some shifting.

    Understandably, this is a lot of information and I am making some assumptions, so I will stop here for now.
    Please let us know if you need any further clarification or guidance.

    0
    Comment actions Permalink
  • Thank you for your detailed explanation. I do not quite understand the shifting you mentioned but I will think more about that.

    0
    Comment actions Permalink
  • The shifting I mentioned is just referring to how some chains have completely different qubit numbers in them after the find_embedding call compared to the clique_embedding.

    Some have none of the same qubits, while some have all of the same qubits.

    Taking excerpts from the above embedding

    clique_embedding qubit:
    0: [708, 704, 576]
    find_embedding with initial_chains qubit:
    0: [583, 591, 578]

    Compared to:

    clique_embedding qubit
    5: [581, 589, 585]
    find_embedding with initial_chains qubit:
    5: [589, 585]

    I hope this makes sense.

    0
    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post