Namespace find_embedding¶

namespace find_embedding

Typedefs

using distance_t = long long int¶

using RANDOM = fastrng ¶

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

Functions

int findEmbedding(graph::input_graph &var_g, graph::input_graph &qubit_g, optional_parameters &params, 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.

template<typename T> void collectMinima(const vector<T> &input, vector<int> &output)¶: Fill output with the index of all of the minimum and equal values in input.

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

chain &operator=(const vector<int> &c)

assign this to a vector of ints.

each incoming qubit will have itself as a parent.

chain &operator=(const chain &c): assign this to another chain

size_t size() const: number of qubits in chain

size_t count(const int q) const: returns 0 if q is not contained in this, 1 otherwise

int get_link(const int x) const: get the qubit, in this, which links this 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 links this 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 into this, and set q to be the root (represented as the linking qubit for label)

void clear(): empty this data structure

void add_leaf(const int q, const int parent): add the qubit q as a leaf, with parent 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 be q but otherwise cycles should be impossible

void adopt(const int p, const int q): assign p to be the parent of q, on condition that both p and q are contained in this, q is its own parent, and q is not the root

int refcount(const int q) const: return the number of references that this makes to the qubit q where a “reference” is an occurrence of q as a parent or an occurrence of q 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> void steal(chain &other, embedding_problem_t &ep, int chainsize = 0): assumes this and other have links for eachother’s labels steals all qubits from other which are available to be taken by this; 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 to other and intermediate nodes (all but the last) into this (preconditions: this and other are not linked, q is contained in this, and the parent-path is eventually contained in other)

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

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

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, for c from 0 to max_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, typename B> void shuffle(A a, B b): shuffle the data bracketed by iterators a and b

void qubit_component(int q0, vector<int> &component, vector<int> &visited): compute the connected component of the subset component of qubits, containing q0, 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.

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. The links member of a chain is an unordered map storing the linking information for this chain. The data member of a chain stores the connectivity information for the chain.

Links: If u and v 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 mapping qubit->(parent, refs) where: parent is also contained in the chain refs is the total number of references to qubit, 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.

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> 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 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> void error(const char *format, Args... args) const: printf regardless of the verbosity level

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

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

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

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

template<typename N> class pairing_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 and other into heap-order

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

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

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

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

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