search

dwavesystems / minorminer

minorminer is a heuristic tool for minor embedding: given a minor and target graph, it tries to find a mapping that embeds the minor into the target.
https://docs.ocean.dwavesys.com/projects/minorminer/en/latest
Apache License 2.0
46 stars 37 forks source link

richer embedding objects #17

Open boothby opened 6 years ago

boothby commented 6 years ago

During the course of embedding, the algorithm holds a rich embedding object that contains connectivity information for chains -- couplers that are used to make chains, and couplers that are used for chain interactions. That information is currently being thrown away, only to be reconstructed by the user at a later stage. It may be nice to handle this a little better; returning and accepting richer embedding objects that contain full or partial connectivity information.

jberwald commented 5 years ago

I would also advocate for simple information such a max_chain_length and number_max_chains to be returned as attributes of some sort. That way a user can decide whether the embedding is likely to succeed (eg., chains of length 22, try again), or whether they should try the embedder again. This would be especially useful when searching for a fixed embedding that will be used many times.

jberwald commented 5 years ago

@boothby, regarding your comments above, how would chain connectivity information recorded? Do you imagine sending more vectors to find_embedding() would be the way? Eg., vector[vector[int]] chain_couplers?

boothby commented 5 years ago

For the time being, minorminer stores chain connectivity in the chain class, found in chain.hpp. Specifically, the chain for u contains a link to itself (link[u]), encoding the chain's root; and for each neighbor v, there's a link[v] encoding a single qubit which is used for the u-side of the edge (u,v), with the invariant that if q = chain[u].link[v] exists, then p = chain[v].link[u] also exists and the edge (p,q) is in the target graph.

The chain class is a reference-counting datastructure, and one place where link is used is in tearing out chains -- since each edge has a unique link per qubit, we simply unlink the chain we're tearing out, and garbage-collect superfluous qubits from neighboring chains. Without that uniqueness, tearing chains out becomes significantly more complex.

In short, I'm having a hard time motivating my original query -- it will take a significant amount of work, only to save maybe .01% of the embedding runtime. On the other side, Harris et al have better bias&interaction spreading algorithms which need to know all of the couplers, not just a random one picked out for convenience in this heuristic. If we open up the question "is a more complicated tearout algorithm more effective and also improved by storing all intended chain-chain interactions" then I'd consider this interface change, but without that research bearing fruit, I don't see it.

arcondello commented 3 years ago

See also EmbeddingStructure added by https://github.com/dwavesystems/dwave-system/pull/321