File embedding.hpp¶
Defines

DIAGNOSE_EMB
(X)¶

namespace
find_embedding

template<typename
embedding_problem_t
>
classembedding
 #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
intothis.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
andother
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 atq
, with a vector of parent info, where for each neiborv
ofu
, followingq
>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 atq
.for the first neighbor
v
ofu
, we follow the parents until we terminate in the chain forv
q
>parents[v][q]
> …. adding all but the last node to the chain ofu
. for each subsequent neighborw
, we pick a nearest Steiner node,qw
, from the current chain ofu
, and add the path starting atqw
, similar to the above…qw
>parents[w][qw]
> … this has an opportunity to make shorter chains thanconstruct_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) undoable tearout procedure.
similar to
tear_out(u)
, but can be undone withthaw_back(u)
. note that this embedding type has a space for a single frozen chain, andfreeze_out(u)
overwrites the previouslyfrozen chain consequently,freeze_out(u)
can be called an arbitrary (nonzero) number of times beforethaw_back(u)
, butthaw_back(u)
MUST be preceeded by at least onefreeze_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 onefreeze_out(u)
and the chain foru
must currently be empty (accomplished either bytear_out(u)
orfreeze_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, populatestats
with a chainlength histogram chains do overlap, populatestats
with a qubit overfill histogram a histogram, in this case, is a vector of size (maximum attained value+1) wherestats[i]
is either the number of qubits contained ini+2
chains or the number of chains with sizei

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

int
num_qubits
¶

int
num_reserved
¶

int
num_vars
¶

int
num_fixed
¶

vector<int>
qub_weight
¶ weights, that is, the number of nonfixed chains that use each qubit this is used in pathfinder clases to determine nonoverlapped, or or leastoverlapped paths through the qubit graph

frozen_chain
frozen
¶


template<typename