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

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
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)
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 rndswap_first
#include <embedding_problem.hpp>
struct shuffle_first
#include <embedding_problem.hpp>