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 &#8212; 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#