Clique Sampler not performing well on dense bqm

I was trying out the influence embeddings can have on the solution quality. Since the BQM I want to solve is dense (118 linear and 6903 quadratic terms), I also used the cliquesampler.

I checked the chain lengthes produced. Emb1 - 3 are embeddings found by minor miner with given seeds, CL is the embedding found by cliquesampler.

While successfully reducing the chain lenght the performance is very bad (n=5):

1-4 are fixedembeddingcomposites with the embeddings from emb1-3 and 4 from cliquesampler. 5 is the raw cliquesampler that interesstingly does not vary much in the sampled energies.

Shouldn't the clique sampler perform better on dense BQM?
It's faster in finding an embedding, thats true, but that embedding obviously does not help at all to find the lowest energy.



1 comment
  • Hello,

    Clique embeddings found by the clique sampler will not necessarily perform better on dense problems, though they will find embeddings much faster. All quadratic terms are represented with clique embeddings, even if they are unused. These clique sampler embeddings have chain lengths that are uniform or close to uniform, which will generally perform better. However in certain cases, such as with small problems, irregular chain lengths will show better results.
    Chain strength can also affect the solution quality, as well as Lagrange parameters.

    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post