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

template<>
using embedding_t = embedding<embedding_problem_t>

Public Functions

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)

void set_initial_chains(map<int, vector<int>> chains)

virtual ~pathfinder_base()

int check_improvement(const embedding_t &emb)

nonzero return if this is an improvement on our previous best embedding

virtual const chain &get_chain(int u) const

chain accessor

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

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

virtual int heuristicEmbedding()

perform the heuristic embedding, returning 1 if an embedding was found and 0 otherwise

Protected Functions

int find_chain(embedding_t &emb, const int u)

tear out and replace the chain in emb for variable u

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)

int improve_overfill_pass(embedding_t &emb)

tear up and replace each variable

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

int improve_chainlength_pass(embedding_t &emb)

tear up and replace each chain, attempting to rebalance the chains and lower the maximum chainlength

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

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

void accumulate_distance(const embedding_t &emb, const int v, vector<int> &visited)

a wrapper for accumulate_distance and accumulate_distance_at_chain

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

void compute_qubit_weights(const embedding_t &emb)

compute the weight of each qubit, first selecting alpha

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

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

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>
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 find_embedding::pathfinder_serial< embedding_problem_t >

friend find_embedding::pathfinder_parallel< embedding_problem_t >

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

template<>
using super = pathfinder_base<embedding_problem_t>

template<>
using embedding_t = embedding<embedding_problem_t>

Public Functions

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)

virtual ~pathfinder_parallel()

virtual void prepare_root_distances(const embedding_t &emb, const int u)

compute the distances from all neighbors of u to all qubits

Private Functions

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

template<typename C>
void exec_chunked(C e_chunk)

template<typename C>
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

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

template<>
using super = pathfinder_base<embedding_problem_t>

template<>
using embedding_t = embedding<embedding_problem_t>

Public Functions

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)

virtual ~pathfinder_serial()

virtual void prepare_root_distances(const embedding_t &emb, const int u)

compute the distances from all neighbors of u to all qubits