File chain.hpp

Defines

DIAGNOSE2(other, X)

DIAGNOSE(X)

namespace find_embedding

class find_embeddingchain

#include <chain.hpp>

This class stores chains for embeddings, and performs qubit-use accounting.

The label is the index number for the variable represented by this chain. The links member of a chain is an unordered map storing the linking information for this chain. The data member of a chain stores the connectivity information for the chain.

Links: If u and v are variables which are connected by an edge, the following must be true: either chain_u or chain_v is empty,

or

chain_u.links[v] is a key in chain_u.data, chain_v.links[u] is a key in chain_v.data, and (chain_u.links[v], chain_v.links[u]) are adjacent in the qubit graph

Moreover, (chain_u.links[u]) must exist if chain_u is not empty, and this is considered the root of the chain.

Data: The data member stores the connectivity information. More precisely, data is a mapping qubit->(parent, refs) where: parent is also contained in the chain refs is the total number of references to qubit, counting both parents and links the chain root is its own parent.

Public Functions

find_embedding::chainchain(vector<int> &w, int l)

construct this chain, linking it to the qubit_weight vector w (common to all chains in an embedding, typically) and setting its variable label l

chain &find_embedding::chainoperator=(const vector<int> &c)

assign this to a vector of ints.

each incoming qubit will have itself as a parent.

chain &find_embedding::chainoperator=(const chain &c)

assign this to another chain

int find_embedding::chainsize() const

number of qubits in chain

int find_embedding::chaincount(const int q) const

returns 0 if q is not contained in this, 1 otherwise

int find_embedding::chainget_link(const int x) const

get the qubit, in this, which links this to the chain of x (if x==label, interpret the linking qubit as the chain’s root)

void find_embedding::chainset_link(const int x, const int q)

set the qubit, in this, which links this to the chain of x (if x==label, interpret the linking qubit as the chain’s root)

int find_embedding::chaindrop_link(const int x)

discard and return the linking qubit for x, or -1 if that link is not set

void find_embedding::chainset_root(const int q)

insert the qubit q into this, and set q to be the root (represented as the linking qubit for label)

void find_embedding::chainclear()

empty this data structure

void find_embedding::chainadd_leaf(const int q, const int parent)

add the qubit q as a leaf, with parent as its parent

int find_embedding::chaintrim_branch(int q)

try to delete the qubit q from this chain, and keep deleting until no more qubits are free to be deleted.

return the first ancestor which cannot be deleted

int find_embedding::chaintrim_leaf(int q)

try to delete the qubit q from this chain.

if q cannot be deleted, return it; otherwise return its parent

int find_embedding::chainparent(const int q) const

the parent of q in this chain which might be q but otherwise cycles should be impossible

void find_embedding::chainadopt(const int p, const int q)

assign p to be the parent of q, on condition that both p and q are contained in this, q is its own parent, and q is not the root

int find_embedding::chainrefcount(const int q) const

return the number of references that this makes to the qubit q where a “reference” is an occurrence of q as a parent or an occurrence of q as a linking qubit / root

template <typename embedding_problem_t>
void find_embedding::chainsteal(chain &other, embedding_problem_t &ep, int chainsize = 0)

assumes this and other have links for eachother’s labels steals all qubits from other which are available to be taken by this; starting with the qubit links and updating qubit links after all

void find_embedding::chainlink_path(chain &other, int q, const vector<int> &parents)

link this chain to another, following the path q, parent[q], parent[parent[q]], …

from this to other and intermediate nodes (all but the last) into this (preconditions: this and other are not linked, q is contained in this, and the parent-path is eventually contained in other)

iterator find_embedding::chainbegin() const

iterator pointing to the first qubit in this chain

iterator find_embedding::chainend() const

iterator pointing to the end of this chain

void find_embedding::chaindiagnostic(char *last_op)

run the diagnostic, and if it fails, report the failure to the user and throw -1.

the last_op argument is used in the error message

int find_embedding::chainrun_diagnostic() const

run the diagnostic and return a nonzero status r in case of failure if(r&1), then the parent of a qubit is not contained in this chain if(r&2), then there is a refcounting error in this chain

Public Members

const int find_embedding::chainlabel

Private Functions

const pair<int, int> &find_embedding::chainfetch(int q) const

const unsafe data accessor

pair<int, int> &find_embedding::chainretrieve(int q)

non-const unsafe data accessor

Private Members

vector<int> &find_embedding::chainqubit_weight

unordered_map<int, pair<int, int>> find_embedding::chaindata

unordered_map<int, int> find_embedding::chainlinks

class find_embedding::chainiterator

#include <chain.hpp>

Public Functions

find_embedding::chain::iterator::iterator(typename decltype(data)::const_iterator it)

iterator find_embedding::chain::iteratoroperator++()

bool find_embedding::chain::iteratoroperator!=(const iterator &other)

decltype(data) const ::key_type& find_embedding::chain::iterator::operator*() const

Private Members

decltype(data) ::const_iterator find_embedding::chain::iterator::it