Displaying Embedding Generated by EmbeddingComposite

Thomas L

May 10, 2019 15:46

I have the following code, where I provide a QUBO to an EmbeddingComposite wrapped DWaveSampler.

from dwave.system.samplers import DWaveSampler
from dwave.system.composites import EmbeddingComposite
sampler = DWaveSampler()
response = EmbeddingComposite(sampler).sample_qubo(qubo, num_reads=200)

How do I retrieve the actual embedding that was used on the hardware? I want to see what how the size of the model changed while embedding.

Comments

19 comments

David J (Report)
May 10, 2019 18:14 (Edited February 18, 2023 23:17)
The best way to see the embedding is to use the FixedEmbeddingComposite:
https://docs.ocean.dwavesys.com/projects/system/en/stable/reference/composites.html#fixedembeddingcomposite

This is a simple example illustrating how to use it:
```
from dwave.system.samplers import DWaveSampler
from dwave.system.composites import FixedEmbeddingComposite
from minorminer import find_embedding

solver = DWaveSampler()

Q = {(0,1):1}

__, target_edgelist, target_adjacency = solver.structure

emb = find_embedding(Q, target_edgelist, verbose=1)

sampler = FixedEmbeddingComposite(solver, emb)

result = sampler.sample_qubo(Q, num_reads=1)
```
The verbose parameter is optional.

Note that if you save the embedding, it will use the same embedding every time, unlike when you use the EmbeddingComposite, which generates a new one every time.

You can easily regenerate the embedding if you desire this behaviour.

I hope this was helpful!
1

Comment actions Permalink
Thomas L (Report)
May 12, 2019 18:40

It was, thank you! Does the "FixedEmbeddingComposite" use majority voting to resolve chain breaks by default?

Does it allow for a customization of the chain-break resolution method?

0

Comment actions Permalink
David J (Report)
May 13, 2019 19:27 (Edited August 12, 2019 20:36)
At the moment, you cannot customize the chain-break resolution method, however there is a feature request to add it!
Here's a link to the feature request for reference:
https://github.com/dwavesystems/dwave-system/issues/182

For the time being, you can also do the embedding and unembedding in separate steps.

Here is a code example of how to do this:
```
from dimod import BinaryQuadraticModel
from dwave.embedding import embed_bqm, unembed_sampleset
from dwave.system.samplers import DWaveSampler
from minorminer import find_embedding
from dwave.embedding.chain_breaks import majority_vote

solver = DWaveSampler()

__, target_edgelist, target_adjacency = solver.structure

bqm = BinaryQuadraticModel.from_qubo(Q)

emb = find_embedding(Q, target_edgelist)

embedded_bqm = embed_bqm(bqm, emb, target_adjacency)

result = solver.sample(embedded_bqm, num_reads=1)

unembedded = unembed_sampleset(result, emb, bqm, chain_break_method=majority_vote(bqm, emb))
```
The chain_break_method can be replaced with one of the generators listed in the documentation here:
https://docs.ocean.dwavesys.com/projects/system/en/latest/reference/embedding.html#chain-break-resolution

Here is a link to the documentation for the unembed function:
https://docs.ocean.dwavesys.com/projects/system/en/latest/reference/generated/dwave.embedding.unembed_sampleset.html

I hope this was helpful.
Please let us know if you have any questions or need more information.
1

Comment actions Permalink
Thomas L (Report)
May 14, 2019 06:01 (Edited May 14, 2019 06:02)

Thanks David. I actually arrived at that same solution myself. I'm finding that the output of that code is significantly less diverse than the output I get from the FixedCompositeEmbedding. Do you know how that module resolves chain-breaks by default?

I was unable to produce the same looking results (as FCE) with any of the custom chain-break resolution methods.

0

Comment actions Permalink
David J (Report)
May 14, 2019 15:54

My apologies!
I forgot to mention that the default chain break method is indeed majority_vote.

So, you tried using majority_vote and are seeing different behaviour?

How is the behaviour differing?
Maybe we can offer an explanation or find a place for further investigation.

0

Comment actions Permalink

Thomas L (Report)

May 14, 2019 17:28

I've created a minimum working example that shows the discrepancy between the two modes of operation. In this example "manual_embed" can be switched between True and False. If majority voting was the only thing being used, I would expect the output of the two methods to be identical. As you can see in the results I provide, they are not identical.

Code

# Initialize some settings for this test.
manual_embed = True
num_samples = 256
qubo = {(0, 0): 0, (1, 1): 0, (2, 2): 0.0, (3, 3): 0, (4, 4): 7.5,
(5, 5): 7.5, (6, 6): 0.5, (7, 7): 11.75, (0, 1): 0,
(0, 2): 5.5, (0, 3): 5.5, (0, 4): 0, (0, 5): -11.0, (0, 6): 0,
(0, 7): -11.0, (1, 2): 5.5, (1, 3): 5.5, (1, 4): -11.0,
(1, 5): 0, (1, 6): -11.0, (1, 7): 0, (2, 3): 0, (2, 4): -11.0,
(2, 5): 0, (2, 6): 0, (2, 7): -11.0, (3, 4): 0, (3, 5): -11.0,
(3, 6): -11.0, (3, 7): 0, (4, 5): 2.0, (4, 6): 4.0,
(4, 7): 1.0, (5, 6): 4, (5, 7): 1.0, (6, 7): 2.0}


# Construct a sampler over a real quantum annealer.
from dwave.system.samplers import DWaveSampler
sampler = DWaveSampler()


# Construct an automatic embedding over the machine architecture.
_, edgelist, adjacency = sampler.structure
from minorminer import find_embedding
embedding = find_embedding(qubo, edgelist, random_seed=0)


if manual_embed:
    # Pick the method for fixing broken chains.
    from dwave.embedding.chain_breaks import majority_vote, weighted_random
    method = majority_vote
    # Submit the job via an embedded BinaryQuadraticModel.
    from dimod import BinaryQuadraticModel as BQM
    from dwave.embedding import embed_bqm, unembed_sampleset
    # Generate a BQM from the QUBO.
    q = BQM.from_qubo(qubo)
    # Embed the BQM onto the target structure.
    embedded_q = embed_bqm(q, embedding, adjacency)
    # Collect the sample output.
    response = unembed_sampleset(
       sampler.sample(embedded_q, num_reads=num_samples),
       embedding, q, chain_break_method=method,
       chain_break_fraction=True)
else:
    # Use a FixedEmbeddingComposite if we don't care about chains.
    from dwave.system.composites import FixedEmbeddingComposite
    system_composite = FixedEmbeddingComposite(sampler, embedding)
    response = system_composite.sample_qubo(qubo, num_reads=num_samples)


# Cycle through the results and yield them to the caller.
for out in response.data():
    # Get the output from the data.
    bits = (out.sample[b] for b in sorted(out.sample))
    occurrence = out.num_occurrences
    chain_break_fraction = out.chain_break_fraction
    energy = out.energy + self.constant
    print(bits, occurrence, 100*chain_break_fraction, energy)

Results

manual_embed = False

Bits                        Occurrence  Chain breaks   Energy
 (1, 1, 1, 1, 1, 1, 1, 1)       3        12.5%          0.25
 (1, 1, 1, 1, 1, 1, 1, 1)      99        25.0%          0.25
 (1, 1, 1, 1, 1, 1, 1, 1)     150        37.5%          0.25
 (0, 1, 1, 1, 1, 0, 1, 0)       1        12.5%          4.0
 (0, 1, 1, 1, 1, 1, 1, 0)       1        25.0%          6.5
 (1, 1, 1, 1, 0, 1, 1, 1)       1        37.5%          7.75
 (1, 1, 1, 1, 0, 1, 1, 1)       1        50.0%          7.75

manual_embed = True

Bits                        Occurrence  Chain breaks   Energy
(1, 1, 1, 1, 1, 1, 1, 1)       88        50.0%          0.25
(1, 1, 1, 1, 0, 1, 1, 1)       43        62.5%          7.75
(0, 1, 1, 1, 1, 1, 1, 1)       84        50.0%         11.25
(0, 1, 1, 1, 1, 1, 1, 1)        1        62.5%         11.25
(0, 1, 1, 1, 0, 1, 1, 1)       39        62.5%         18.75
(0, 1, 1, 1, 0, 1, 1, 1)        1        75.0%         18.75

Conclusion

The results of the FixedCompositeEmbedding do not appear to be the same as a majority vote. Perhaps I've coded something incorrectly. Barring errors, it looks like the behavior of the two is indeed different when executing on the real hardware. It also looks like the results of the manual embedding are significantly worse!

David J (Report)
May 15, 2019 22:36
Is it possible that you are actually just seeing the differences between embeddings?

The embedding should be generated and then stored somewhere else so that it can be used with each of the methods.
It's possible that you are doing this, but with the code example, it seems that a new embedding is generated on each run of the code body.

This line needs to be outside of the function call or loop:
```
embedding = find_embedding(qubo, edgelist, random_seed=0)
```
You will see differences between sets of runs, but the rates should average off to be the same between the methods (assuming they are using the same embedding and the same chain break method).

Please let me know if this makes sense, and if you had used the same embedding for both.
0

Comment actions Permalink
Thomas L (Report)
May 15, 2019 22:42
Notice the parameter
```
random_seed=0
```
which ensures that the same embedding is always generated.

I repeated this experiment numerous times beforehand (using identical embeddings) and consistently obtained similar results to what I posted above. I have always observed the FixedCompositeEmbedding to produce better solutions (in both variety and energy).

That is why I am assuming that a different chain break method is used by FCE (or there is some other difference).
0

Comment actions Permalink
David J (Report)
May 15, 2019 23:04

Ah! My apologies! I missed the random seed.

I am just reviewing the two methods with some colleagues to see if there are any other steps that are missing.

0

Comment actions Permalink
David J (Report)
May 16, 2019 19:34
Maybe changing these lines to use embed qubo might show similar results:
```
    # Generate a BQM from the QUBO.
    q = BQM.from_qubo(qubo)
    # Embed the BQM onto the target structure.
    embedded_q = embed_bqm(q, embedding, adjacency)
```
Like this:
```
    # Embed the QUBO onto the target structure.
    embedded_q = embed_qubo(qubo, embedding, adjacency)
```
Or alternatively have the FixedEmbeddingComposite use a BQM:
```
# Generate a BQM from the QUBO.
q = BQM.from_qubo(qubo)
response = system_composite.sampl(q, num_reads=num_samples)
```
It's strange that converting it to a BQM might have differing results, but it might be one area to look into.

According to the code there really isn't a difference between the two methods.

You might be seeing a difference in probabilistic distribution, and with larger numbers of samples it will not be visible.

Here is a link to the sample function code of FixedEmbeddingComposite:
https://docs.ocean.dwavesys.com/projects/system/en/latest/_modules/dwave/system/composites/embedding.html#FixedEmbeddingComposite.sample

Here is a link to the unembed function which shows all of the default values, etc:
https://docs.ocean.dwavesys.com/projects/system/en/latest/_modules/dwave/embedding/transforms.html#unembed_sampleset
0

Comment actions Permalink
David J (Report)
May 17, 2019 23:08 (Edited May 17, 2019 23:17)
Good news!
We found the difference.

You also need to set the smear_vartype in the call to embed_bqm like this:
```
bqm_embedded = embed_bqm(bqm, embedding, target_adjacency,
chain_strength=chain_strength,
smear_vartype=dimod.SPIN)
```
This is the default being set in the FixedEmbeddingComposite.

Sorry for the confusion!

Here is a link to the relevant code:
https://github.com/dwavesystems/dwave-system/blob/master/dwave/system/composites/embedding.py#L199

Specifically, here is where the two diverge:
https://github.com/dwavesystems/dwave-system/blob/master/dwave/system/composites/embedding.py#L401

And here is a link to the explanation of smear_type:
https://docs.ocean.dwavesys.com/projects/system/en/latest/reference/generated/dwave.embedding.embed_bqm.html

I will be following up on this and be back to you with more information.
Thank you for your patience and understanding.

In the meantime, please let us know if you have any more questions.
0

Comment actions Permalink

David J (Report)

May 17, 2019 23:12

Another thing I wanted to mention is that you can remove the couplers that have 0 for their bias.

Including them causes them to get embedded, and causes more potential for chain breaks.

Removing them produces simpler embeddings.

So for example, your example from above would look like this:

qubo = {(0, 0): 0, (1, 1): 0, (2, 2): 0.0, (3, 3): 0, (4, 4): 7.5,
(5, 5): 7.5, (6, 6): 0.5, (7, 7): 11.75,
(0, 2): 5.5, (0, 3): 5.5, (0, 5): -11.0,
(0, 7): -11.0, (1, 2): 5.5, (1, 3): 5.5, (1, 4): -11.0,
(1, 6): -11.0, (2, 4): -11.0,
(2, 7): -11.0, (3, 5): -11.0,
(3, 6): -11.0, (4, 5): 2.0, (4, 6): 4.0,
(4, 7): 1.0, (5, 6): 4, (5, 7): 1.0, (6, 7): 2.0}

vaibhaw k (Report)
August 09, 2019 20:00

Hi, so I have tried to follow the steps to include chain_break_method when I sample. It seems to work for the generators specified on https://docs.ocean.dwavesys.com/projects/system/en/latest/reference/embedding.html#chain-break-resolution.

I am trying to use MinimizeEnergy now. I am not sure how to use it because MinimizeEnergy needs to have access to the unembedded samples. How can one get the unembedded response?

0

Comment actions Permalink

David J (Report)

August 10, 2019 01:15 (Edited August 12, 2019 20:36)

Note: Corrected unembed_sampleset call.

Hello,

You might need to provide a minimal code example so that we can see what you are trying to do.

Here is the code example I provided above, but modified to use MinimizeEnergy.

from dimod import BinaryQuadraticModel
from dwave.embedding import embed_bqm, unembed_sampleset
from dwave.system.samplers import DWaveSampler
from minorminer import find_embedding
from dwave.embedding.chain_breaks import MinimizeEnergy

solver = DWaveSampler()

__, target_edgelist, target_adjacency = solver.structure

bqm = BinaryQuadraticModel.from_qubo(Q)

emb = find_embedding(Q, target_edgelist)

embedded_bqm = embed_bqm(bqm, emb, target_adjacency)

result = solver.sample(embedded_bqm, num_reads=1)

unembedded = unembed_sampleset(result, emb, bqm, chain_break_method=MinimizeEnergy(bqm, emb))

vaibhaw k (Report)
August 12, 2019 16:03 (Edited August 12, 2019 20:47)

Thanks for your reply. I really appreciate it. Yeah, it works! I missed that the chain_break_method has this function as the parameter. Just updating things for future reference.

0

Comment actions Permalink
David J (Report)
August 12, 2019 22:29
Hello,

The chain_break_method parameter is a method, as you can see on the first link:
```
chain_break_method (function, optional):  
Method used to resolve chain breaks.  See :mod:`dwave.embedding.chain_breaks`.
```
The embedding parameter is the dictionary:
```
embedding (dict):  
Mapping from source graph to target graph as a dict of form  {s: {t, ...}, ...}, where s is a source variable and t is a target  variable.
```
But! I did find out what the issue was.

I had mistakenly just used the method reference, and the correct way to use it is like this:
```
unembed_sampleset(sampleset, emb, bqm, MinimizeEnergy(bqm, emb))
```
I apologize for the misprint.

I will correct it above as well.

Please let us know if you have any further problems!!
0

Comment actions Permalink
David J (Report)
August 12, 2019 23:46

Just a note.
There is a known issue in dwave-system 0.7.5, which is causing an error when calling the unembed_sampleset function, and will be fixed in dwave-system 0.7.6

We apologize for the inconvenience!

0

Comment actions Permalink
Hoa T (Report)
July 05, 2020 10:52
Hi David, I have a follow-up question:

Is there a simple way to implement chain_break_method=majority_vote or chain_break_method=discard?

I tried this and it does not work:
```
unembed_sampleset(sampleset, emb, bqm, chain_break_method=majority_vote(bqm, emb))
```
0

Comment actions Permalink
David J (Report)
July 06, 2020 22:44
Hello,

In the above example you are actually calling the majority_vote function call, and then assigning the returned value to the chain_break_method input parameter.

What you want to do is leave all of the parentheses portion out, and just provide the function itself, like this:
```
unembed_sampleset(sampleset, emb, bqm, chain_break_method=majority_vote)
```
I hope this was helpful!
Please let us know if you have any further questions!
0

Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post