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