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, re-establishing 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 parent-path 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)¶ non-const unsafe data accessor
-
-
struct
frozen_chain
¶ - #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. 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