File embedding.hpp

Defines

DIAGNOSE_EMB(X)
namespace find_embedding
template<typename embedding_problem_t>
class embedding
#include <embedding.hpp>

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

Private Functions

bool linkup(int u, int v)

This method attempts to find the linking qubits for a pair of adjacent variables, and returns true/false on success/failure in finding that pair.

Private Members

embedding_problem_t &ep
int num_qubits
int num_reserved
int num_vars
int num_fixed
vector<int> qub_weight

weights, that is, the number of non-fixed chains that use each qubit this is used in pathfinder clases to determine non-overlapped, or or least-overlapped paths through the qubit graph

vector<chain> var_embedding

this is where we store chains see chain.hpp for how

frozen_chain frozen