File pathfinder.hpp#

namespace find_embedding

template<typename embedding_problem_t> class pathfinder_base : public find_embedding::pathfinder_public_interface

#include <pathfinder.hpp>

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

Public Types

using embedding_t = embedding<embedding_problem_t>#

Public Functions

inline pathfinder_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 void set_initial_chains(map<int, vector<int>> chains) override: setter for the initial_chains parameter

inline virtual ~pathfinder_base()#

inline bool check_improvement(const embedding_t &emb): nonzero return if this is an improvement on our previous best embedding

inline virtual const chain &get_chain(int u) const override: chain accessor

inline virtual void quickPass(VARORDER varorder, int chainlength_bound, int overlap_bound, bool local_search, bool clear_first, double round_beta) override#

inline virtual void quickPass(const vector<int> &varorder, int chainlength_bound, int overlap_bound, bool local_search, bool clear_first, double round_beta) override#

inline virtual int heuristicEmbedding() override: perform the heuristic embedding, returning 1 if an embedding was found and 0 otherwise

Protected Functions

inline int find_chain(embedding_t &emb, const int u)#: tear out and replace the chain in emb for variable u

inline int check_stops(const int &return_value)#

internal function to check if we’re supposed to stop for an external reason — namely if we’ve timed out (which we catch immediately and return -2 to allow the heuristic to terminate gracefully), or received a keyboard interrupt (which we allow to propagate back to the user).

If neither stopping condition is encountered, return return_value.

inline int initialization_pass(embedding_t &emb)#: sweep over all variables, either keeping them if they are pre-initialized and connected, and otherwise finding new chains for them (each, in turn, seeking connection only with neighbors that already have chains)

inline int improve_overfill_pass(embedding_t &emb)#: tear up and replace each variable

inline int pushdown_overfill_pass(embedding_t &emb)#: tear up and replace each chain, strictly improving or maintaining the maximum qubit fill seen by each chain

inline int improve_chainlength_pass(embedding_t &emb)#: tear up and replace each chain, attempting to rebalance the chains and lower the maximum chainlength

inline void accumulate_distance_at_chain(const embedding_t &emb, const int v)#: incorporate the qubit weights associated with the chain for v into total_distance

inline void accumulate_distance(const embedding_t &emb, const int v, vector<int> &visited, const int start, const int stop)#: incorporate the distances associated with the chain for v into total_distance

inline void accumulate_distance(const embedding_t &emb, const int v, vector<int> &visited)#: a wrapper for accumulate_distance and accumulate_distance_at_chain

inline void compute_distances_from_chain(const embedding_t &emb, const int &v, vector<int> &visited)#

run dijkstra’s algorithm, seeded at the chain for v, using the visited vector note: qubits are only visited if visited[q] = 1.

the value -1 is used to prevent searching of overfull qubits

inline void compute_qubit_weights(const embedding_t &emb)#: compute the weight of each qubit, first selecting alpha

inline void compute_qubit_weights(const embedding_t &emb, const int start, const int stop)#: compute the weight of each qubit in the range from start to stop, where the weight is 2^(alpha*fill) where fill is the number of chains which use that qubit

Protected Attributes

embedding_problem_t ep#

optional_parameters &params#

embedding_t bestEmbedding#

embedding_t lastEmbedding#

embedding_t currEmbedding#

embedding_t initEmbedding#

int num_qubits#

int num_reserved#

int num_vars#

int num_fixed#

vector<vector<int>> parents#

vector<distance_t> total_distance#

vector<int> min_list#

vector<distance_t> qubit_weight#

vector<int> tmp_stats#

vector<int> best_stats#

int pushback#

clock::time_point stoptime#

vector<vector<int>> visited_list#

vector<vector<distance_t>> distances#

vector<vector<int>> qubit_permutations#

Private Functions

virtual void prepare_root_distances(const embedding_t &emb, const int u) = 0#: compute the distances from all neighbors of u to all qubits

inline int find_chain(embedding_t &emb, const int u, int target_chainsize)#: after u has been torn out, perform searches from each neighboring chain, select a minimum-distance root, and construct the chain

inline void find_short_chain(embedding_t &emb, const int u, const int target_chainsize)#

after u has been torn out, perform searches from each neighboring chain, iterating over potential roots to find a root with a smallest-possible actual chainlength whereas other variants of find_chain simply pick a random root candidate with minimum estimated chainlength.

this procedure takes quite a long time and requires that emb is a valid embedding with no overlaps.

template<typename pq_t, typename behavior_tag> inline void dijkstra_initialize_chain(const embedding_t &emb, const int &v, vector<int> &parent, vector<int> &visited, pq_t &pq, behavior_tag)#: this function prepares the parent & distance-priority-queue before running dijkstra’s algorithm

Friends

friend class pathfinder_serial< embedding_problem_t >

friend class pathfinder_parallel< embedding_problem_t >

struct default_tag#

struct embedded_tag#

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

using super = pathfinder_base<embedding_problem_t>#

using embedding_t = embedding<embedding_problem_t>#

Public Functions

inline pathfinder_serial(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 ~pathfinder_serial()#

inline virtual void prepare_root_distances(const embedding_t &emb, const int u) override: compute the distances from all neighbors of u to all qubits

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

using super = pathfinder_base<embedding_problem_t>#

using embedding_t = embedding<embedding_problem_t>#

Public Functions

inline pathfinder_parallel(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 ~pathfinder_parallel()#

inline virtual void prepare_root_distances(const embedding_t &emb, const int u) override: compute the distances from all neighbors of u to all qubits

Private Functions

inline void run_in_thread(const embedding_t &emb, const int u)#

template<typename C> inline void exec_chunked(C e_chunk)#

template<typename C> inline void exec_indexed(C e_chunk)#

Private Members

int num_threads#

vector<std::future<void>> futures#

vector<int> thread_weight#

mutex get_job#

unsigned int nbr_i#

int neighbors_embedded#

class pathfinder_public_interface

#include <pathfinder.hpp>

Subclassed by find_embedding::pathfinder_base< embedding_problem_t >

Public Functions

virtual int heuristicEmbedding() = 0#

virtual const chain &get_chain(int) const = 0#

inline virtual ~pathfinder_public_interface()#

virtual void set_initial_chains(map<int, vector<int>>) = 0#

virtual void quickPass(const vector<int>&, int, int, bool, bool, double) = 0#

virtual void quickPass(VARORDER, int, int, bool, bool, double) = 0#