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
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 dynamically-selected 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 find_embedding::MinorMinerException - #include <util.hpp>
-
class
chain
- #include <chain.hpp>
Public Functions
-
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
-
chain &
operator=
(const vector<int> &c) assign this to a vector of ints.
each incoming qubit will have itself as a parent.
-
size_t
size
() const number of qubits in chain
-
size_t
count
(const int q) const returns 0 if
q
is not contained inthis
, 1 otherwise
-
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)
-
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)
-
int
drop_link
(const int x) discard and return the linking qubit for
x
, or -1 if that link is not set
-
void
set_root
(const int q) insert the qubit
q
intothis
, and setq
to be the root (represented as the linking qubit forlabel
)
-
void
clear
() empty this data structure
-
void
add_leaf
(const int q, const int parent) add the qubit
q
as a leaf, withparent
as its parent
-
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
-
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
-
int
parent
(const int q) const the parent of
q
in this chain which might beq
but otherwise cycles should be impossible
-
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
-
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
-
size_t
freeze
(vector<chain> &others, frozen_chain &keep) store this chain into a
frozen_chain
, unlink all chains from this, and clear()
-
void
thaw
(vector<chain> &others, frozen_chain &keep) restore a
frozen_chain
into this, re-establishing links from other chains.precondition: this is empty.
-
template<typename
embedding_problem_t
>
voidsteal
(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
-
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 parent-path is eventually contained inother
)
-
iterator
begin
() const iterator pointing to the first qubit in this chain
-
iterator
end
() const iterator pointing to the end of this chain
-
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
-
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>
-
-
class
CorruptEmbeddingException
: public find_embedding::MinorMinerException - #include <util.hpp>
-
class
CorruptParametersException
: public find_embedding::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
>
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) undo-able 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 previously-frozen 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
-
-
template<class
fixed_handler
, classdomain_handler
, classoutput_handler
>
classembedding_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
-
void
reset_mood
() resets some internal, ephemeral, variables to a default state
-
void
populate_weight_table
(int max_weight) precomputes a table of weights corresponding to various overlap values
c
, forc
from 0 tomax_weight
, inclusive.
-
distance_t
weight
(unsigned int c) const returns the precomputed weight associated with an overlap value of
c
-
const vector<int> &
var_neighbors
(int u) const a vector of neighbors for the variable
u
-
const vector<int> &
var_neighbors
(int u, shuffle_first) a vector of neighbors for the variable
u
, pre-shuffling them
-
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
-
const vector<int> &
qubit_neighbors
(int q) const a vector of neighbors for the qubit
q
-
int
num_vars
() const number of variables which are not fixed
-
int
num_qubits
() const number of qubits which are not reserved
-
int
num_fixed
() const number of fixed variables
-
int
num_reserved
() const number of reserved qubits
-
int
randint
(int a, int b) make a random integer between 0 and
m-1
-
template<typename
A
, typenameB
>
voidshuffle
(A a, B b) shuffle the data bracketed by iterators
a
andb
-
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
-
const vector<int> &
var_order
(VARORDER order = VARORDER_SHUFFLE) compute a variable ordering according to the
order
strategy
-
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 &
params
A mutable reference to the user specified parameters.
-
void
-
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 qubit-use 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
-
void
displayOutput
(int loglevel, const string &msg) const Print a message through the local output method.
-
void
displayError
(int loglevel, const string &msg) const Print an error through the local output method.
-
int
cancelled
(const clock::time_point stoptime) const Check if someone is trying to cancel the embedding process.
-
void
-
class
max_heap_tag
- #include <pairing_queue.hpp>
-
class
min_heap_tag
- #include <pairing_queue.hpp>
-
class
MinorMinerException
: public runtime_error - #include <util.hpp>
Subclassed by find_embedding::BadInitializationException, find_embedding::CorruptEmbeddingException, find_embedding::CorruptParametersException, find_embedding::ProblemCancelledException, find_embedding::TimeoutException
-
class
optional_parameters
- #include <util.hpp>
Set of parameters used to control the embedding process.
Public Functions
-
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.
-
-
template<bool
verbose
>
classoutput_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 errors-only 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
>
voiderror
(const char *format, Args... args) const printf regardless of the verbosity level
-
template<typename ...
Args
>
voidmajor_info
(const char *format, Args... args) const printf at the major_info verbosity level
-
template<typename ...
Args
>
voidminor_info
(const char *format, Args... args) const print at the minor_info verbosity level
-
template<typename ...
Args
>
voidextra_info
(const char *format, Args... args) const print at the extra_info verbosity level
-
template<typename ...
Args
>
voiddebug
(const char*, Args...) const print at the debug verbosity level (only works when
CPPDEBUG
is set)
-
template<typename ...
-
template<typename
N
>
classpairing_node
: public N - #include <pairing_queue.hpp>
Public Functions
-
pairing_node<N> *
merge_roots
(pairing_node<N> *other) the basic operation of the pairing queue put
this
andother
into heap-order
-
pairing_node<N> *
-
template<typename
N
>
classpairing_queue
- #include <pairing_queue.hpp>
-
class
parameter_processor
- #include <find_embedding.hpp>
-
template<typename
embedding_problem_t
>
classpathfinder_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
-
void
set_initial_chains
(map<int, vector<int>> chains) override setter for the initial_chains parameter
-
bool
check_improvement
(const embedding_t &emb) nonzero return if this is an improvement on our previous best embedding
-
const chain &
get_chain
(int u) const override chain accessor
-
int
heuristicEmbedding
() override perform the heuristic embedding, returning 1 if an embedding was found and 0 otherwise
-
void
-
template<typename
embedding_problem_t
>
classpathfinder_parallel
: public find_embedding::pathfinder_base<embedding_problem_t> - #include <pathfinder.hpp>
A pathfinder where the Dijkstra-from-neighboring-chain passes are done serially.
Public Functions
-
void
prepare_root_distances
(const embedding_t &emb, const int u) override compute the distances from all neighbors of
u
to all qubits
-
void
-
class
pathfinder_public_interface
- #include <pathfinder.hpp>
Subclassed by find_embedding::pathfinder_base< embedding_problem_t >
-
template<typename
embedding_problem_t
>
classpathfinder_serial
: public find_embedding::pathfinder_base<embedding_problem_t> - #include <pathfinder.hpp>
A pathfinder where the Dijkstra-from-neighboring-chain passes are done serially.
Public Functions
-
void
prepare_root_distances
(const embedding_t &emb, const int u) override compute the distances from all neighbors of
u
to all qubits
-
void
-
template<bool
parallel
, boolfixed
, boolrestricted
, boolverbose
>
classpathfinder_type
- #include <find_embedding.hpp>
-
class
pathfinder_wrapper
- #include <find_embedding.hpp>
-
template<typename
P
, typenameheap_tag
= min_heap_tag>
classpriority_node
- #include <pairing_queue.hpp>
-
class
ProblemCancelledException
: public find_embedding::MinorMinerException - #include <util.hpp>
-
struct
rndswap_first
- #include <embedding_problem.hpp>
-
struct
shuffle_first
- #include <embedding_problem.hpp>
-
class
TimeoutException
: public find_embedding::MinorMinerException - #include <util.hpp>
-
using