File chain.hpp¶

namespace
find_embedding
¶ 
class
chain
 #include <chain.hpp>
Public Functions

chain
(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 labell

chain &
operator=
(const vector<int> &c) assign this to a vector of ints.
each incoming qubit will have itself as a parent.

size_t
size
() const number of qubits in chain

size_t
count
(const int q) const returns 0 if
q
is not contained inthis
, 1 otherwise

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

void
set_link
(const int x, const int q) set the qubit, in
this
, which linksthis
to the chain of x (if x==label, interpret the linking qubit as the chain’s root)

int
drop_link
(const int x) discard and return the linking qubit for
x
, or 1 if that link is not set

void
set_root
(const int q) insert the qubit
q
intothis
, and setq
to be the root (represented as the linking qubit forlabel
)

void
clear
() empty this data structure

void
add_leaf
(const int q, const int parent) add the qubit
q
as a leaf, withparent
as its parent

int
trim_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
trim_leaf
(int q) try to delete the qubit
q
from this chain.if
q
cannot be deleted, return it; otherwise return its parent

int
parent
(const int q) const the parent of
q
in this chain which might beq
but otherwise cycles should be impossible

void
adopt
(const int p, const int q) assign
p
to be the parent ofq
, on condition that bothp
andq
are contained inthis
,q
is its own parent, andq
is not the root

int
refcount
(const int q) const return the number of references that
this
makes to the qubitq
where a “reference” is an occurrence ofq
as a parent or an occurrence ofq
as a linking qubit / root

size_t
freeze
(vector<chain> &others, frozen_chain &keep) store this chain into a
frozen_chain
, unlink all chains from this, and clear()

void
thaw
(vector<chain> &others, frozen_chain &keep) restore a
frozen_chain
into this, reestablishing links from other chains.precondition: this is empty.

template<typename
embedding_problem_t
>
voidsteal
(chain &other, embedding_problem_t &ep, int chainsize = 0) assumes
this
andother
have links for eachother’s labels steals all qubits fromother
which are available to be taken bythis
; starting with the qubit links and updating qubit links after all

void
link_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
toother
and intermediate nodes (all but the last) intothis
(preconditions:this
andother
are not linked,q
is contained inthis
, and the parentpath is eventually contained inother
)

iterator
begin
() const iterator pointing to the first qubit in this chain

iterator
end
() const iterator pointing to the end of this chain

void
diagnostic
() run the diagnostic, and if it fails, report the failure to the user and throw a CorruptEmbeddingException.
the
last_op
argument is used in the error message

int
run_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
label
¶
Private Functions

const pair<int, int> &
fetch
(int q) const¶ const unsafe data accessor

pair<int, int> &
retrieve
(int q)¶ nonconst unsafe data accessor


struct
frozen_chain
¶  #include <chain.hpp>
This class stores chains for embeddings, and performs qubituse accounting.
The
label
is the index number for the variable represented by this chain. Thelinks
member of a chain is an unordered map storing the linking information for this chain. Thedata
member of a chain stores the connectivity information for the chain.Links: If
u
andv
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 mappingqubit>(parent, refs)
where:parent
is also contained in the chainrefs
is the total number of references toqubit
, counting both parents and links the chain root is its own parent.Public Functions

void
clear
()¶

void

class