Class find_embedding::embedding#

template<typename embedding_problem_t>
class embedding#

This class is how we represent and manipulate embedding objects, using as much encapsulation as possible.

We provide methods to view and modify chains.

Public Functions

inline embedding(embedding_problem_t &e_p)#

constructor for an empty embedding

inline embedding(embedding_problem_t &e_p, map<int, vector<int>> &fixed_chains, map<int, vector<int>> &initial_chains)#

constructor for an initial embedding: accepts fixed and initial chains, populates the embedding based on them, and attempts to link adjacent chains together.

inline embedding<embedding_problem_t> &operator=(const embedding<embedding_problem_t> &other)#

copy the data from other.var_embedding into this.var_embedding

inline const chain &get_chain(int v) const#

Get the variables in a chain.

inline unsigned int chainsize(int v) const#

Get the size of a chain.

inline int weight(int q) const#

Get the weight of a qubit.

inline int max_weight() const#

Get the maximum of all qubit weights.

inline int max_weight(const int start, const int stop) const#

Get the maximum of all qubit weights in a range.

inline bool has_qubit(const int v, const int q) const#

Check if variable v is includes qubit q in its chain.

inline void set_chain(const int u, const vector<int> &incoming)#

Assign a chain for variable u.

inline void fix_chain(const int u, const vector<int> &incoming)#

Permanently assign a chain for variable u.

NOTE: This must be done before any chain is assigned to u.

inline bool operator==(const embedding &other) const#

check if this and other have the same chains (up to qubit containment per chain; linking and parent information is not checked)

inline void construct_chain(const int u, const int q, const vector<vector<int>> &parents)#

construct the chain for u, rooted at q, with a vector of parent info, where for each neibor v of u, following q -> parents[v][q] -> parents[v][parents[v][q]]

terminates in the chain for v

inline void construct_chain_steiner(const int u, const int q, const vector<vector<int>> &parents, const vector<vector<distance_t>> &distances, vector<vector<int>> &visited_list)#

construct the chain for u, rooted at q.

for the first neighbor v of u, we follow the parents until we terminate in the chain for v q -> parents[v][q] -> …. adding all but the last node to the chain of u. for each subsequent neighbor w, we pick a nearest Steiner node, qw, from the current chain of u, and add the path starting at qw, similar to the above… qw -> parents[w][qw] -> … this has an opportunity to make shorter chains than construct_chain

inline void flip_back(int u, const int target_chainsize)#

distribute path segments to the neighboring chains &#8212; path segments are the qubits that are ONLY used to join link_qubit[u][v] to link_qubit[u][u] and aren’t used for any other variable

  • if the target chainsize is zero, dump the entire segment into the neighbor

  • if the target chainsize is k, stop when the neighbor’s size reaches k

inline void tear_out(int u)#

short tearout procedure blank out the chain, its linking qubits, and account for the qubits being freed

inline int freeze_out(int u)#

undo-able tearout procedure.

similar to tear_out(u), but can be undone with thaw_back(u). note that this embedding type has a space for a single frozen chain, and freeze_out(u) overwrites the previously-frozen chain consequently, freeze_out(u) can be called an arbitrary (nonzero) number of times before thaw_back(u), but thaw_back(u) MUST be preceeded by at least one freeze_out(u). returns the size of the chain being frozen

inline void thaw_back(int u)#

undo for the freeze_out procedure: replaces the chain previously frozen, and destroys the data in the frozen chain thaw_back(u) must be preceeded by at least one freeze_out(u) and the chain for u must currently be empty (accomplished either by tear_out(u) or freeze_out(u))

inline void steal_all(int u)#

grow the chain for u, stealing all available qubits from neighboring variables

inline int statistics(vector<int> &stats) const#

compute statistics for this embedding and return 1 if no chains are overlapping when no chains are overlapping, populate stats with a chainlength histogram chains do overlap, populate stats with a qubit overfill histogram a histogram, in this case, is a vector of size (maximum attained value+1) where stats[i] is either the number of qubits contained in i+2 chains or the number of chains with size i

inline bool linked() const#

check if the embedding is fully linked &#8212; that is, if each pair of adjacent variables is known to correspond to a pair of adjacent qubits

inline bool linked(int u) const#

check if a single variable is linked with all adjacent variables.

inline void print() const#

print out this embedding to a level of detail that is useful for debugging purposes TODO describe the output format.

inline void long_diagnostic(std::string current_state)#

run a long diagnostic, and if debugging is enabled, record current_state so that the error message has a little more context.

if an error is found, throw a CorruptEmbeddingException

inline void run_long_diagnostic(std::string current_state) const#

run a long diagnostic to verify the integrity of this datastructure.

the guts of this function are its documentation, because this function only exists for debugging purposes