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