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

domain_handler_masked(optional_parameters &p, int n_v, int n_f, int n_q, int n_r)
~domain_handler_masked()
void prepare_visited(vector<int> &visited, const int u, const int v)
void prepare_distances(vector<distance_t> &distance, const int u, const distance_t &mask_d)
void prepare_distances(vector<distance_t> &distance, const int u, const distance_t &mask_d, const int start, const int stop)
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

domain_handler_universe(optional_parameters&, int, int, int, int)
~domain_handler_universe()

Public Static Functions

void prepare_visited(vector<int> &visited, int, int)
void prepare_distances(vector<distance_t> &distance, const int, const distance_t&)
void prepare_distances(vector<distance_t> &distance, const int, const distance_t&, const int start, const int stop)
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

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

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)
~embedding_problem_base()
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.

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

size_t compute_margin()

computes an upper bound on the distances computed during tearout & replace

template<typename queue_t>
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)

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

fixed_handler_hival(optional_parameters&, int n_v, int, int n_q, int)
~fixed_handler_hival()
bool fixed(const int u)
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

fixed_handler_none(optional_parameters&, int, int, int, int)
~fixed_handler_none()

Public Static Functions

bool fixed(int)
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

output_handler(optional_parameters &p)
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)

Private Members

optional_parameters &params
struct rndswap_first
#include <embedding_problem.hpp>
struct shuffle_first
#include <embedding_problem.hpp>