File pathfinder.hpp

namespace find_embedding

template <typename embedding_problem_t>
class find_embeddingpathfinder_base

#include <pathfinder.hpp>

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

Public Types

template<>
using find_embedding::pathfinder_base<embedding_problem_t>embedding_t = embedding<embedding_problem_t>

Public Functions

find_embedding::pathfinder_basepathfinder_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)

virtual find_embedding::pathfinder_base~pathfinder_base()

int find_embedding::pathfinder_basecheck_improvement(const embedding_t &emb)

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

const chain &find_embedding::pathfinder_baseget_chain(int u) const

chain accessor

int find_embedding::pathfinder_baseheuristicEmbedding()

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

Protected Functions

int find_embedding::pathfinder_basefind_chain(embedding_t &emb, const int u)

tear out and replace the chain in emb for variable u

int find_embedding::pathfinder_baseinitialization_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 find_embedding::pathfinder_baseimprove_overfill_pass(embedding_t &emb)

tear up and replace each variable

int find_embedding::pathfinder_basepushdown_overfill_pass(embedding_t &emb)

tear up and replace each chain, strictly improving or maintaining the maximum qubit fill seen by each chain

int find_embedding::pathfinder_baseimprove_chainlength_pass(embedding_t &emb)

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

void find_embedding::pathfinder_baseaccumulate_distance_at_chain(const embedding_t &emb, const int v)

incorporate the qubit weights associated with the chain for v into total_distance

void find_embedding::pathfinder_baseaccumulate_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 find_embedding::pathfinder_baseaccumulate_distance(const embedding_t &emb, const int v, vector<int> &visited)

a wrapper for accumulate_distance and accumulate_distance_at_chain

void find_embedding::pathfinder_basecompute_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 find_embedding::pathfinder_basecompute_qubit_weights(const embedding_t &emb)

compute the weight of each qubit, first selecting alpha

void find_embedding::pathfinder_basecompute_qubit_weights(const embedding_t &emb, const int alpha, const int maxwid, 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 find_embedding::pathfinder_baseep

optional_parameters &find_embedding::pathfinder_baseparams

embedding_t find_embedding::pathfinder_basebestEmbedding

embedding_t find_embedding::pathfinder_baselastEmbedding

embedding_t find_embedding::pathfinder_basecurrEmbedding

embedding_t find_embedding::pathfinder_baseinitEmbedding

int find_embedding::pathfinder_basenum_qubits

int find_embedding::pathfinder_basenum_reserved

int find_embedding::pathfinder_basenum_vars

int find_embedding::pathfinder_basenum_fixed

vector<vector<int>> find_embedding::pathfinder_baseparents

vector<distance_t> find_embedding::pathfinder_basetotal_distance

vector<int> find_embedding::pathfinder_basetmp_space

vector<int> find_embedding::pathfinder_basemin_list

int_queue find_embedding::pathfinder_baseintqueue

vector<distance_t> find_embedding::pathfinder_basequbit_weight

vector<int> find_embedding::pathfinder_basetmp_stats

vector<int> find_embedding::pathfinder_basebest_stats

int find_embedding::pathfinder_basepushback

clock::time_point find_embedding::pathfinder_basestoptime

vector<distance_queue> find_embedding::pathfinder_basedijkstras

Private Functions

virtual void find_embedding::pathfinder_baseprepare_root_distances(const embedding_t &emb, const int u) = 0

compute the distances from all neighbors of u to all qubits

int find_embedding::pathfinder_basefind_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

Friends

friend find_embedding::pathfinder_serial< embedding_problem_t >

friend find_embedding::pathfinder_parallel< embedding_problem_t >

template <typename embedding_problem_t>
class find_embeddingpathfinder_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 find_embedding::pathfinder_parallel<embedding_problem_t>super = pathfinder_base<embedding_problem_t>

template<>
using find_embedding::pathfinder_parallel<embedding_problem_t>embedding_t = embedding<embedding_problem_t>

Public Functions

find_embedding::pathfinder_parallelpathfinder_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 find_embedding::pathfinder_parallel~pathfinder_parallel()

virtual void find_embedding::pathfinder_parallelprepare_root_distances(const embedding_t &emb, const int u)

compute the distances from all neighbors of u to all qubits

Private Functions

void find_embedding::pathfinder_parallelrun_in_thread(const embedding_t &emb, const int u)

template <typename C>
void find_embedding::pathfinder_parallelexec_chunked(C e_chunk)

template <typename C>
void find_embedding::pathfinder_parallelexec_indexed(C e_chunk)

Private Members

int find_embedding::pathfinder_parallelnum_threads

vector<vector<int>> find_embedding::pathfinder_parallelvisited_list

vector<std::future<void>> find_embedding::pathfinder_parallelfutures

vector<int> find_embedding::pathfinder_parallelthread_weight

mutex find_embedding::pathfinder_parallelget_job

unsigned int find_embedding::pathfinder_parallelnbr_i

int find_embedding::pathfinder_parallelneighbors_embedded

template <typename embedding_problem_t>
class find_embeddingpathfinder_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 find_embedding::pathfinder_serial<embedding_problem_t>super = pathfinder_base<embedding_problem_t>

template<>
using find_embedding::pathfinder_serial<embedding_problem_t>embedding_t = embedding<embedding_problem_t>

Public Functions

find_embedding::pathfinder_serialpathfinder_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 find_embedding::pathfinder_serial~pathfinder_serial()

virtual void find_embedding::pathfinder_serialprepare_root_distances(const embedding_t &emb, const int u)

compute the distances from all neighbors of u to all qubits

Private Members

vector<int> find_embedding::pathfinder_serialvisited