Namespace find_embedding

namespace find_embedding

Typedefs

using find_embedding::distance_t = typedef long long int

using find_embedding::RANDOM = typedef default_random_engine

using find_embedding::clock = typedef std::chrono::high_resolution_clock

using find_embedding::distance_queue = typedef pairing_queue::pairing_queue_fast_reset<distance_t>

using find_embedding::int_queue = typedef pairing_queue::pairing_queue_fast_reset<int64_t>

typedef shared_ptr<LocalInteraction> find_embeddingLocalInteractionPtr

Enums

enum find_embeddingVARORDER

Values:

find_embeddingVARORDER_SHUFFLE

find_embeddingVARORDER_DFS

find_embeddingVARORDER_BFS

find_embeddingVARORDER_PFS

find_embeddingVARORDER_RPFS

find_embeddingVARORDER_KEEP

Functions

template <class pathfinder_t>
int find_embeddingfind_embedding_execute(graph::input_graph &var_g, graph::input_graph &qubit_g, optional_parameters &params_, vector<vector<int>> &chains)

This function parses inputs, scrambles node labels, dispatches the main embedding algorithm, pathfinder_base.heuristicEmbedding, and finally unscrambles the resulting answer.

int find_embeddingfindEmbedding(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 find_embeddingcollectMinima(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 find_embeddingmax_distance = numeric_limits<distance_t>::max()

class find_embeddingchain

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

Public Functions

find_embedding::chainchain(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 &find_embedding::chainoperator=(const vector<int> &c)

assign this to a vector of ints.

each incoming qubit will have itself as a parent.

chain &find_embedding::chainoperator=(const chain &c)

assign this to another chain

int find_embedding::chainsize() const

number of qubits in chain

int find_embedding::chaincount(const int q) const

returns 0 if q is not contained in this, 1 otherwise

int find_embedding::chainget_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 find_embedding::chainset_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 find_embedding::chaindrop_link(const int x)

discard and return the linking qubit for x, or -1 if that link is not set

void find_embedding::chainset_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 find_embedding::chainclear()

empty this data structure

void find_embedding::chainadd_leaf(const int q, const int parent)

add the qubit q as a leaf, with parent as its parent

int find_embedding::chaintrim_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 find_embedding::chaintrim_leaf(int q)

try to delete the qubit q from this chain.

if q cannot be deleted, return it; otherwise return its parent

int find_embedding::chainparent(const int q) const

the parent of q in this chain which might be q but otherwise cycles should be impossible

void find_embedding::chainadopt(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 find_embedding::chainrefcount(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

template <typename embedding_problem_t>
void find_embedding::chainsteal(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 find_embedding::chainlink_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 find_embedding::chainbegin() const

iterator pointing to the first qubit in this chain

iterator find_embedding::chainend() const

iterator pointing to the end of this chain

void find_embedding::chaindiagnostic(char *last_op)

run the diagnostic, and if it fails, report the failure to the user and throw -1.

the last_op argument is used in the error message

int find_embedding::chainrun_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 find_embeddingdomain_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 find_embeddingdomain_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 find_embeddingembedding

#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

find_embedding::embeddingembedding(embedding_problem_t &e_p)

constructor for an empty embedding

find_embedding::embeddingembedding(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> &find_embedding::embeddingoperator=(const embedding<embedding_problem_t> &other)

copy the data from other.var_embedding into this.var_embedding

const chain &find_embedding::embeddingget_chain(int v) const

Get the variables in a chain.

int find_embedding::embeddingchainsize(int v) const

Get the size of a chain.

int find_embedding::embeddingweight(int q) const

Get the weight of a qubit.

int find_embedding::embeddingmax_weight() const

Get the maximum of all qubit weights.

int find_embedding::embeddingmax_weight(const int start, const int stop) const

Get the maximum of all qubit weights in a range.

bool find_embedding::embeddinghas_qubit(const int v, const int q) const

Check if variable v is includes qubit q in its chain.

void find_embedding::embeddingset_chain(const int u, const vector<int> &incoming)

Assign a chain for variable u.

void find_embedding::embeddingfix_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 find_embedding::embeddingoperator==(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 find_embedding::embeddingconstruct_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 find_embedding::embeddingflip_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 find_embedding::embeddingtear_out(int u)

short tearout procedure blank out the chain, its linking qubits, and account for the qubits being freed

void find_embedding::embeddingsteal_all(int u)

grow the chain for u, stealing all available qubits from neighboring variables

int find_embedding::embeddingstatistics(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 find_embedding::embeddinglinked() 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 find_embedding::embeddinglinked(int u) const

check if a single variable is linked with all adjacent variables.

void find_embedding::embeddingprint() const

print out this embedding to a level of detail that is useful for debugging purposes TODO describe the output format.

void find_embedding::embeddinglong_diagnostic(char *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 -1

void find_embedding::embeddingrun_long_diagnostic(char *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 find_embeddingembedding_problem : public find_embedding::embedding_problem_base, public fixed_handler, public domain_handler

#include <embedding_problem.hpp>

A template to construct a complete embedding problem by combining embedding_problem_base with fixed/domain handlers.

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

Public Functions

const vector<int> &find_embedding::embedding_problem_basevar_neighbors(int u) const

a vector of neighbors for the variable u

const vector<int> &find_embedding::embedding_problem_basequbit_neighbors(int q) const

a vector of neighbors for the qubit q

int find_embedding::embedding_problem_basenum_vars() const

number of variables which are not fixed

int find_embedding::embedding_problem_basenum_qubits() const

number of qubits which are not reserved

int find_embedding::embedding_problem_basenum_fixed() const

number of fixed variables

int find_embedding::embedding_problem_basenum_reserved() const

number of reserved qubits

template <typename... Args>
void find_embedding::embedding_problem_baseerror(const char *format, Args... args) const

printf regardless of the verbosity level

template <typename... Args>
void find_embedding::embedding_problem_basemajor_info(const char *format, Args... args) const

printf at the major_info verbosity level

template <typename... Args>
void find_embedding::embedding_problem_baseminor_info(const char *format, Args... args) const

print at the minor_info verbosity level

template <typename... Args>
void find_embedding::embedding_problem_baseextra_info(const char *format, Args... args) const

print at the extra_info verbosity level

template <typename... Args>
void find_embedding::embedding_problem_basedebug(const char *ONDEBUGformat, Args... ONDEBUGargs) const

print at the debug verbosity level (only works when CPPDEBUG is set)

int find_embedding::embedding_problem_baserandint(int m)

make a random integer between 0 and m-1

template <typename A, typename B>
void find_embedding::embedding_problem_baseshuffle(A a, B b)

shuffle the data bracketed by iterators a and b

void find_embedding::embedding_problem_basequbit_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> &find_embedding::embedding_problem_basevar_order(VARORDER order = VARORDER_SHUFFLE)

compute a variable ordering according to the order strategy

void find_embedding::embedding_problem_basedfs_component(int x, const vector<vector<int>> &neighbors, vector<int> &component, vector<int> &visited)

Perform a depth first search.

Public Members

optional_parameters &find_embedding::embedding_problem_baseparams

A mutable reference to the user specified parameters.

class find_embeddingFindEmbeddingException

#include <util.hpp>

Subclassed by find_embedding::ProblemCancelledException

class find_embeddingfixed_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 find_embeddingfixed_handler_list

#include <embedding_problem.hpp>

This fixed handler is used when variables are allowed to be fixed after instantiation.

For that functionality, we probably need…

• dynamic modification of var_neighbors and qubit_neighbors to maintain speed gains: fixed variables are sinks, reserved qubits are sources.
• access to / ownership of var_neighbors and qubit_neighbors in this data structure
• move existing initialization code from find_embedding.hpp into fixed_handler_hival (note the interplay with shuffling qubit labels, this might get gross)

class find_embeddingfixed_handler_none

#include <embedding_problem.hpp>

This fixed handler is used when there are no fixed variables.

class find_embeddingLocalInteraction

#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 find_embedding::LocalInteractiondisplayOutput(const string &msg) const

Print a message through the local output method.

bool find_embedding::LocalInteractioncancelled(const clock::time_point stoptime) const

Check if someone is trying to cancel the embedding process.

class find_embeddingoptional_parameters

#include <util.hpp>

Set of parameters used to control the embedding process.

Public Members

LocalInteractionPtr find_embedding::optional_parameterslocalInteractionPtr

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

double find_embedding::optional_parameterstimeout = 1000

Number of seconds before the process unconditionally stops.

template <typename embedding_problem_t>
class find_embeddingpathfinder_base

#include <pathfinder.hpp>

Subclassed by find_embedding::pathfinder_parallel< embedding_problem_t >, find_embedding::pathfinder_serial< embedding_problem_t >

Public Functions

int find_embedding::pathfinder_basecheck_improvement(const embedding_t &emb)

nonzero return if this is an improvement on our previous best embedding

const chain &find_embedding::pathfinder_baseget_chain(int u) const

chain accessor

int find_embedding::pathfinder_baseheuristicEmbedding()

perform the heuristic embedding, returning 1 if an embedding was found and 0 otherwise

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

virtual void find_embedding::pathfinder_parallelprepare_root_distances(const embedding_t &emb, const int u)

compute the distances from all neighbors of u to all qubits

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

virtual void find_embedding::pathfinder_serialprepare_root_distances(const embedding_t &emb, const int u)

compute the distances from all neighbors of u to all qubits