Namespace find_embedding¶

namespace find_embedding
Typedefs

using distance_t = long long int¶

using clock = std::chrono::high_resolution_clock¶

using min_queue = std::priority_queue<priority_node<P, min_heap_tag>>¶

using max_queue = std::priority_queue<priority_node<P, max_heap_tag>>¶

using distance_queue = pairing_queue<priority_node<distance_t, min_heap_tag>>¶

typedef shared_ptr<LocalInteraction> LocalInteractionPtr¶
Enums

enum VARORDER
Values:

enumerator VARORDER_SHUFFLE

enumerator VARORDER_DFS

enumerator VARORDER_BFS

enumerator VARORDER_PFS

enumerator VARORDER_RPFS

enumerator VARORDER_KEEP

enumerator VARORDER_SHUFFLE
Functions

int findEmbedding(graph::input_graph &var_g, graph::input_graph &qubit_g, optional_parameters ¶ms, vector<vector<int>> &chains)
The main entry function of this library.
This method primarily dispatches the proper implementation of the algorithm where some parameters/behaviours have been fixed at compile time.
In terms of dispatch, there are three dynamicallyselected classes which are combined, each according to a specific optional parameter.
a domain_handler, described in embedding_problem.hpp, manages constraints of the form “variable a’s chain must be a subset of…”
a fixed_handler, described in embedding_problem.hpp, manages contstraints of the form “variable a’s chain must be exactly…”
a pathfinder, described in pathfinder.hpp, which come in two flavors, serial and parallel The optional parameters themselves can be found in util.hpp. Respectively, the controlling options for the above are restrict_chains, fixed_chains, and threads.
Variables

constexpr distance_t max_distance = numeric_limits<distance_t>::max()¶

class BadInitializationException : public minorminer::MinorMinerException
 #include <util.hpp>

class chain
 #include <chain.hpp>
Public Functions

inline chain(vector<int> &w, int l)
construct this chain, linking it to the qubit_weight vector
w
(common to all chains in an embedding, typically) and setting its variable labell

inline chain &operator=(const vector<int> &c)
assign this to a vector of ints.
each incoming qubit will have itself as a parent.

inline size_t size() const
number of qubits in chain

inline size_t count(const int q) const
returns 0 if
q
is not contained inthis
, 1 otherwise

inline int get_link(const int x) const
get the qubit, in
this
, which linksthis
to the chain of x (if x==label, interpret the linking qubit as the chain’s root)

inline void set_link(const int x, const int q)
set the qubit, in
this
, which linksthis
to the chain of x (if x==label, interpret the linking qubit as the chain’s root)

inline int drop_link(const int x)
discard and return the linking qubit for
x
, or 1 if that link is not set

inline void set_root(const int q)
insert the qubit
q
intothis
, and setq
to be the root (represented as the linking qubit forlabel
)

inline void clear()
empty this data structure

inline void add_leaf(const int q, const int parent)
add the qubit
q
as a leaf, withparent
as its parent

inline int trim_branch(int q)
try to delete the qubit
q
from this chain, and keep deleting until no more qubits are free to be deleted.return the first ancestor which cannot be deleted

inline int trim_leaf(int q)
try to delete the qubit
q
from this chain.if
q
cannot be deleted, return it; otherwise return its parent

inline int parent(const int q) const
the parent of
q
in this chain — which might beq
but otherwise cycles should be impossible

inline void adopt(const int p, const int q)
assign
p
to be the parent ofq
, on condition that bothp
andq
are contained inthis
,q
is its own parent, andq
is not the root

inline int refcount(const int q) const
return the number of references that
this
makes to the qubitq
— where a “reference” is an occurrence ofq
as a parent or an occurrence ofq
as a linking qubit / root

inline size_t freeze(vector<chain> &others, frozen_chain &keep)
store this chain into a
frozen_chain
, unlink all chains from this, and clear()

inline void thaw(vector<chain> &others, frozen_chain &keep)
restore a
frozen_chain
into this, reestablishing links from other chains.precondition: this is empty.

template<typename embedding_problem_t>
inline void steal(chain &other, embedding_problem_t &ep, int chainsize = 0) assumes
this
andother
have links for eachother’s labels steals all qubits fromother
which are available to be taken bythis
; starting with the qubit links and updating qubit links after all

inline void link_path(chain &other, int q, const vector<int> &parents)
link this chain to another, following the path
q
,parent[q]
,parent[parent[q]]
, …from
this
toother
and intermediate nodes (all but the last) intothis
(preconditions:this
andother
are not linked,q
is contained inthis
, and the parentpath is eventually contained inother
)

inline iterator begin() const
iterator pointing to the first qubit in this chain

inline iterator end() const
iterator pointing to the end of this chain

inline void diagnostic()
run the diagnostic, and if it fails, report the failure to the user and throw a CorruptEmbeddingException.
the
last_op
argument is used in the error message

inline int run_diagnostic() const
run the diagnostic and return a nonzero status
r
in case of failure if(r
&1), then the parent of a qubit is not contained in this chain if(r
&2), then there is a refcounting error in this chain

class iterator
 #include <chain.hpp>

inline chain(vector<int> &w, int l)

class CorruptEmbeddingException : public minorminer::MinorMinerException
 #include <util.hpp>

class CorruptParametersException : public minorminer::MinorMinerException
 #include <util.hpp>

class domain_handler_masked
 #include <embedding_problem.hpp>
this domain handler stores masks for each variable so that prepare_visited and prepare_distances are barely more expensive than a memcopy

class domain_handler_universe
 #include <embedding_problem.hpp>
this is the trivial domain handler, where every variable is allowed to use every qubit

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

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
intothis.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
andother
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 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

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

inline 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

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

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 onefreeze_out(u)
and the chain foru
must currently be empty (accomplished either bytear_out(u)
orfreeze_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, 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

inline 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

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

inline embedding(embedding_problem_t &e_p)

template<class fixed_handler, class domain_handler, class output_handler>
class embedding_problem : public find_embedding::embedding_problem_base, public fixed_handler, public domain_handler, public find_embedding::output_handler<verbose>  #include <embedding_problem.hpp>
A template to construct a complete embedding problem by combining
embedding_problem_base
with fixed/domain handlers.

class embedding_problem_base
 #include <embedding_problem.hpp>
Common form for all embedding problems.
Needs to be extended with a fixed handler and domain handler to be complete.
Subclassed by find_embedding::embedding_problem< fixed_handler, domain_handler, output_handler >
Public Functions

inline void reset_mood()
resets some internal, ephemeral, variables to a default state

inline void populate_weight_table(int max_weight)
precomputes a table of weights corresponding to various overlap values
c
, forc
from 0 tomax_weight
, inclusive.

inline distance_t weight(unsigned int c) const
returns the precomputed weight associated with an overlap value of
c

inline const vector<int> &var_neighbors(int u) const
a vector of neighbors for the variable
u

inline const vector<int> &var_neighbors(int u, shuffle_first)
a vector of neighbors for the variable
u
, preshuffling them

inline const vector<int> &var_neighbors(int u, rndswap_first)
a vector of neighbors for the variable
u
, applying a random transposition before returning the reference

inline const vector<int> &qubit_neighbors(int q) const
a vector of neighbors for the qubit
q

inline int num_vars() const
number of variables which are not fixed

inline int num_qubits() const
number of qubits which are not reserved

inline int num_fixed() const
number of fixed variables

inline int num_reserved() const
number of reserved qubits

inline int randint(int a, int b)
make a random integer between 0 and
m1

template<typename A, typename B>
inline void shuffle(A a, B b) shuffle the data bracketed by iterators
a
andb

inline void qubit_component(int q0, vector<int> &component, vector<int> &visited)
compute the connected component of the subset
component
of qubits, containingq0
, and usingvisited
as an indicator for which qubits have been explored

inline const vector<int> &var_order(VARORDER order = VARORDER_SHUFFLE)
compute a variable ordering according to the
order
strategy

inline void dfs_component(int x, const vector<vector<int>> &neighbors, vector<int> &component, vector<int> &visited)
Perform a depth first search.
Public Members

optional_parameters ¶ms
A mutable reference to the user specified parameters.

inline void reset_mood()

class fixed_handler_hival
 #include <embedding_problem.hpp>
This fixed handler is used when the fixed variables are processed before instantiation and relabeled such that variables v >= num_v are fixed and qubits q >= num_q are reserved.

class fixed_handler_none
 #include <embedding_problem.hpp>
This fixed handler is used when there are no fixed variables.

struct frozen_chain
 #include <chain.hpp>
This class stores chains for embeddings, and performs qubituse accounting.
The
label
is the index number for the variable represented by this chain. Thelinks
member of a chain is an unordered map storing the linking information for this chain. Thedata
member of a chain stores the connectivity information for the chain.Links: If
u
andv
are variables which are connected by an edge, the following must be true: either chain_u or chain_v is empty,or
chain_u.links[v] is a key in chain_u.data, chain_v.links[u] is a key in chain_v.data, and (chain_u.links[v], chain_v.links[u]) are adjacent in the qubit graph
Moreover, (chain_u.links[u]) must exist if chain_u is not empty, and this is considered the root of the chain.
Data: The
data
member stores the connectivity information. More precisely,data
is a mappingqubit>(parent, refs)
where:parent
is also contained in the chainrefs
is the total number of references toqubit
, counting both parents and links the chain root is its own parent.

class LocalInteraction
 #include <util.hpp>
Interface for communication between the library and various bindings.
Any bindings of this library need to provide a concrete subclass.
Public Functions

inline void displayOutput(int loglevel, const string &msg) const
Print a message through the local output method.

inline void displayError(int loglevel, const string &msg) const
Print an error through the local output method.

inline int cancelled(const clock::time_point stoptime) const
Check if someone is trying to cancel the embedding process.

inline void displayOutput(int loglevel, const string &msg) const

class max_heap_tag
 #include <pairing_queue.hpp>

class min_heap_tag
 #include <pairing_queue.hpp>

class optional_parameters
 #include <util.hpp>
Set of parameters used to control the embedding process.
Public Functions

inline optional_parameters(optional_parameters &p, map<int, vector<int>> fixed_chains, map<int, vector<int>> initial_chains, map<int, vector<int>> restrict_chains)
duplicate all parameters but chain hints, and seed a new rng.
this vaguely peculiar behavior is utilized to spawn parameters for component subproblems
Public Members

LocalInteractionPtr localInteractionPtr
actually not controlled by user, not initialized here, but initialized in Python, MATLAB, C wrappers level

double timeout = 1000
Number of seconds before the process unconditionally stops.

inline optional_parameters(optional_parameters &p, map<int, vector<int>> fixed_chains, map<int, vector<int>> initial_chains, map<int, vector<int>> restrict_chains)

template<bool verbose>
class output_handler  #include <embedding_problem.hpp>
Output handlers are used to control output.
We provide two handlers — one which only reports all errors (and optimizes away all other output) and another which provides full output. When verbose is zero, we recommend the errorsonly handler and otherwise, the full handler Here’s the full output handler
Subclassed by find_embedding::embedding_problem< fixed_handler, domain_handler, output_handler >
Public Functions

template<typename ...Args>
inline void error(const char *format, Args... args) const printf regardless of the verbosity level

template<typename ...Args>
inline void major_info(const char *format, Args... args) const printf at the major_info verbosity level

template<typename ...Args>
inline void minor_info(const char *format, Args... args) const print at the minor_info verbosity level

template<typename ...Args>
inline void extra_info(const char *format, Args... args) const print at the extra_info verbosity level

template<typename ...Args>
inline void debug(const char*, Args...) const print at the debug verbosity level (only works when
CPPDEBUG
is set)

template<typename ...Args>

template<typename N>
class pairing_node : public N  #include <pairing_queue.hpp>
Public Functions

inline pairing_node<N> *merge_roots(pairing_node<N> *other)
the basic operation of the pairing queue — put
this
andother
into heaporder

inline pairing_node<N> *merge_roots(pairing_node<N> *other)

template<typename N>
class pairing_queue  #include <pairing_queue.hpp>

class parameter_processor
 #include <find_embedding.hpp>

template<typename embedding_problem_t>
class pathfinder_base : public find_embedding::pathfinder_public_interface  #include <pathfinder.hpp>
Subclassed by find_embedding::pathfinder_parallel< embedding_problem_t >, find_embedding::pathfinder_serial< embedding_problem_t >
Public Functions

inline virtual void set_initial_chains(map<int, vector<int>> chains) override
setter for the initial_chains parameter

inline bool check_improvement(const embedding_t &emb)
nonzero return if this is an improvement on our previous best embedding

inline virtual const chain &get_chain(int u) const override
chain accessor

inline virtual int heuristicEmbedding() override
perform the heuristic embedding, returning 1 if an embedding was found and 0 otherwise

inline virtual void set_initial_chains(map<int, vector<int>> chains) override

template<typename embedding_problem_t>
class pathfinder_parallel : public find_embedding::pathfinder_base<embedding_problem_t>  #include <pathfinder.hpp>
A pathfinder where the Dijkstrafromneighboringchain passes are done serially.
Public Functions

inline virtual void prepare_root_distances(const embedding_t &emb, const int u) override
compute the distances from all neighbors of
u
to all qubits

inline virtual void prepare_root_distances(const embedding_t &emb, const int u) override

class pathfinder_public_interface
 #include <pathfinder.hpp>
Subclassed by find_embedding::pathfinder_base< embedding_problem_t >

template<typename embedding_problem_t>
class pathfinder_serial : public find_embedding::pathfinder_base<embedding_problem_t>  #include <pathfinder.hpp>
A pathfinder where the Dijkstrafromneighboringchain passes are done serially.
Public Functions

inline virtual void prepare_root_distances(const embedding_t &emb, const int u) override
compute the distances from all neighbors of
u
to all qubits

inline virtual void prepare_root_distances(const embedding_t &emb, const int u) override

template<bool parallel, bool fixed, bool restricted, bool verbose>
class pathfinder_type  #include <find_embedding.hpp>

class pathfinder_wrapper
 #include <find_embedding.hpp>

template<typename P, typename heap_tag = min_heap_tag>
class priority_node  #include <pairing_queue.hpp>

class ProblemCancelledException : public minorminer::MinorMinerException
 #include <util.hpp>

struct rndswap_first
 #include <embedding_problem.hpp>

struct shuffle_first
 #include <embedding_problem.hpp>

class TimeoutException : public minorminer::MinorMinerException
 #include <util.hpp>

using distance_t = long long int¶