Displaying Embedding Generated by EmbeddingComposite

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.

0

Comments

19 comments
  • The best way to see the embedding is to use the FixedEmbeddingComposite:
    https://docs.ocean.dwavesys.com/projects/system/en/latest/reference/composites/fixed_embedding.html

    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
  • 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
  • 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
  • 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
  • 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
  • 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!

     

    0
    Comment actions Permalink
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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}
    0
    Comment actions Permalink
  • 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
  • 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))
    0
    Comment actions Permalink
  • 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
  • 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
  • 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
  • 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
  • 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