richer embedding objects

[boothby]

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]

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]

@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]

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]

See also EmbeddingStructure added by dwavesystems/dwave-system#321