File embedding_problem.hpp#

namespace find_embedding

Enums

enum VARORDER#

Values:

enumerator VARORDER_SHUFFLE#

enumerator VARORDER_DFS#

enumerator VARORDER_BFS#

enumerator VARORDER_PFS#

enumerator VARORDER_RPFS#

enumerator VARORDER_KEEP#

class domain_handler_universe

#include <embedding_problem.hpp>

this is the trivial domain handler, where every variable is allowed to use every qubit

Public Functions

inline domain_handler_universe(optional_parameters&, int, int, int, int)#

inline virtual ~domain_handler_universe()#

Public Static Functions

static inline void prepare_visited(vector<int> &visited, int, int)#

static inline void prepare_distances(vector<distance_t> &distance, const int, const distance_t&)#

static inline void prepare_distances(vector<distance_t> &distance, const int, const distance_t&, const int start, const int stop)#

static inline bool accepts_qubit(int, int)#

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

Public Functions

inline domain_handler_masked(optional_parameters &p, int n_v, int n_f, int n_q, int n_r)#

inline virtual ~domain_handler_masked()#

inline void prepare_visited(vector<int> &visited, const int u, const int v)#

inline void prepare_distances(vector<distance_t> &distance, const int u, const distance_t &mask_d)#

inline void prepare_distances(vector<distance_t> &distance, const int u, const distance_t &mask_d, const int start, const int stop)#

inline bool accepts_qubit(const int u, const int q)#

Private Members

optional_parameters &params#

vector<vector<int>> masks#

class fixed_handler_none

#include <embedding_problem.hpp>

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

Public Functions

inline fixed_handler_none(optional_parameters&, int, int, int, int)#

inline virtual ~fixed_handler_none()#

Public Static Functions

static inline bool fixed(int)#

static inline bool reserved(int)#

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.

Public Functions

inline fixed_handler_hival(optional_parameters&, int n_v, int, int n_q, int)#

inline virtual ~fixed_handler_hival()#

inline bool fixed(const int u)#

inline bool reserved(const int q)#

Private Members

int num_v#

int num_q#

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

inline output_handler(optional_parameters &p)#

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)

Private Members

optional_parameters &params#

struct shuffle_first#: #include <embedding_problem.hpp>

struct rndswap_first#: #include <embedding_problem.hpp>

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 embedding_problem_base(optional_parameters &p_, int n_v, int n_f, int n_q, int n_r, vector<vector<int>> &v_n, vector<vector<int>> &q_n)#

inline virtual ~embedding_problem_base()#

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, for c from 0 to max_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, pre-shuffling 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 m-1

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

inline 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

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 &params: A mutable reference to the user specified parameters.

double max_beta#

double round_beta#

double bound_beta#

distance_t weight_table[64]#

int initialized#

int embedded#

int desperate#

int target_chainsize#

int improved#

int weight_bound#

Protected Attributes

int num_v#

int num_f#

int num_q#

int num_r#

vector<vector<int>> &qubit_nbrs#: Mutable references to qubit numbers and variable numbers.

vector<vector<int>> &var_nbrs#

uniform_int_distribution rand#: distribution over [0, 0xffffffff]

vector<int> var_order_space#

vector<int> var_order_visited#

vector<int> var_order_shuffle#

unsigned int exponent_margin#

Private Functions

inline size_t compute_margin()#: computes an upper bound on the distances computed during tearout & replace

template<typename queue_t> inline void pfs_component(int x, const vector<vector<int>> &neighbors, vector<int> &component, vector<int> &visited, vector<int> shuffled)#: Perform a priority first search (priority = #of visited neighbors)

inline void bfs_component(int x, const vector<vector<int>> &neighbors, vector<int> &component, vector<int> &visited, vector<int> &shuffled)#: Perform a breadth first search, shuffling level sets.

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.

Public Functions

inline embedding_problem(optional_parameters &p, int n_v, int n_f, int n_q, int n_r, vector<vector<int>> &v_n, vector<vector<int>> &q_n)#

inline virtual ~embedding_problem()#

Private Types

using ep_t = embedding_problem_base #

using fh_t = fixed_handler #

using dh_t = domain_handler #

using oh_t = output_handler #