Find Embedding on Chimera Graph
Hi everyone,
I generated a chimera graph and I did an edge contraction (consist of deleting an edge (v1,v2) and merging its endpoints v1 and v2 into a new vertex v*) on it. I'm trying to find an embedding of this graph on entire chimera graph (like this paper https://arxiv.org/abs/1801.08649 section 4.3) but function find_embedding of minorminer module return an empty embedding. I thought that this embedding is simple, theoretically. Any ideas?
Comments
Hi Alberto,
How are you obtaining the graph you are trying to find an embedding for?
The find_embedding function will throw an error if it can't find an embedding for the graph.
Are you catching errors?
Can you find an embedding for the graph before the edge contraction?
Sometimes removing an edge does not make the graph simpler, as it must be embedded onto the QPU, which might require that edge.
See "Fig. 17 Embedding a triangular graph into Chimera by using a chain." on the following page for more information:
https://docs.dwavesys.com/docs/latest/c_gs_7.html
I hope this was helpful!
Please let us know if you need any more information.
Hi David,
thank u for reply. I simply generate a portion of chimera graph, with chimera_graph function of dwave_networkx module, and I choice a random edge and I contracted it from graph. The function find_embedding not throw an error but only empty embedding. I know that this not mean that an embedding doesn't exists. I didn't try to find an embedding before contraction. Thanks for the link, I had already seen it but for large graph find a manual embedding it seems hard.
Hi Alberto,
Would you be able to provide a simple code sample, so I can take a better look at the behaviour?
Hi, sure but it is very simple.
Hi Alberto,
I am just looking further into what exactly is causing the embedding to return as an empty dictionary, but I suspect it has something to do with the length of the chains being produced by find_embedding.
If the embedding didn't fit, it would throw an error, so there must be something else happening.
In the mean time, maybe I can help you make some progress.
For a smaller graph, I was able to find an embedding.
It should be noted that find_embedding finds an embedding, but not necessarily the best embedding.
https://docs.ocean.dwavesys.com/projects/minorminer/en/latest/intro.html
Finding the best embedding is actually a really difficult thing to do, that is, it is not a trivial problem.
Even though they are both Chimera Graphs, it is really difficult to generalize and cover all cases or get the best embedding in this way.
If a smaller Chimera Graph is embedded, an embedding with multiple physical qubits mapped to one logical input qubit will be returned.
Multiple physical qubits acting as a single logical qubit are called "chains":
https://support.dwavesys.com/hc/en-us/community/posts/360016697094-What-is-a-chain-
Using something like this:
graph = dnx.chimera_graph(m=5, n=5, t=4)
Will give an embedding like this:
{0: [863, 871], 4: [865], 5: [858], 6: [867], 7: [866, 738, 610, 614],...
Note how qubits #4, #5, and #6 are mapped to a single qubit, while qubit #0 is mapped to a chain of two qubits, #7 is mapped to a chain of four qubits.
It is possible to get the graph of the QPU that is being used by setting up the solver and then getting the adjacency:
solver = DWaveSampler(solver=my_solver, token=my_dwave_token)
solver.adjacency
The above will result in the following mapping that shows which qubits are mapped to a given qubit:
{0: {128, 4, 5, 6, 7}, 1: {129, 4, 5, 6, 7}, 2: {130, 4, 5, 6, 7}, 3: {131, 4, 5, 6, 7}, 4: {0, 1, 2, 3, 12},...
This shows the exact topology of the physical qubits of the QPU.
Alternatively the list of couplers can be used for the same purpose:
solver.edgelist
Running the above gives the list of all edges or couplers between qubits:
[(0, 4), (0, 5), (0, 6), (0, 7), (0, 128), (1, 4), (1, 5),...
If mapping exactly to the Chimera Graph is desirable, it might be a good idea to think about how to map directly to the graph provided by the solver.
This link explains the Chimera Graph which might be a good reference to visualize the qubit numbering:
https://support.dwavesys.com/hc/en-us/articles/360003695354-What-is-the-Chimera-Topology-
Note that there are 8 qubits per unit and 16 units per row, so the first qubit is connected to qubits #4, #5, #6, #7 in the same unit, and #128 in the 17th unit.
There are 8 qubits per unti and 16 units per row, so:
8 x 16 = 128
This would be the first qubit in the first unit of the second row, since we also have a #0 qubit.
It is possible to contract one of the edges, as you had mentioned previously, by adjusting the coupler value associated with that edge.
As described in the page about chains mentioned above, changing the coupler strength will have multiple qubits act as a single qubit.
Hi David,
it's all clear. Thank u very much for reply.
I was introduced to another way to work with this problem using coordinates.
You can map between two sets of coordinates like in the following code example:
Here is a link to the chimera_coordinates function code:
https://github.com/dwavesystems/dwave_networkx/blob/048b67d9ed568eced46e22ea16124bd37e6b14dc/dwave_networkx/generators/chimera.py#L344
Just an update, that the {} returned is by design, and our documentation was out of date.
This return value means that no embedding could be found.
See the github issue for more information:
https://github.com/dwavesystems/minorminer/issues/70
Hi David,
Thank you for reply. Coordinates method works better but sometimes I've an error when I try to submit QUBO problem to QPU.
sampler = FixedEmbeddingComposite(DWaveSampler(), embedding=embedding)
resp = sampler.sample_qubo(Q)
When I submit the problem the second statement throw me an error:
"given bqm does not match the sampler's structure"
The strange thing is that it not throw me this error always.
Any ideas?
Hi Alberto,
Could you send the code snippet that you use to make the embedding?
This looks like the embedding is not matching the QPU structure.
Please sign in to leave a comment.