Class find_embedding::embedding

template<typename embedding_problem_t>
class find_embedding::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

embedding(embedding_problem_t &e_p)

constructor for an empty embedding

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.

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

copy the data from other.var_embedding into this.var_embedding

const chain &get_chain(int v) const

Get the variables in a chain.

unsigned int chainsize(int v) const

Get the size of a chain.

int weight(int q) const

Get the weight of a qubit.

int max_weight() const

Get the maximum of all qubit weights.

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

Get the maximum of all qubit weights in a range.

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

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

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

Assign a chain for variable u.

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.

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)

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

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

void flip_back(int u, const int target_chainsize)

distribute path segments to the neighboring chains 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

void tear_out(int u)

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

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

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))

void steal_all(int u)

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

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

bool linked() const

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

bool linked(int u) const

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

void print() const

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

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

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