Information¶

The Union-Find Node-Suspension decoder [hu2020thesis] uses the potential matching weight as a heuristic to prioritize growth in specific partitions – the nodes – of the Union-Find cluster (see Information). The potential matching weight is approximated by levering a node-tree in the Node-Suspension Data-structure. The elements of the node-tree are descendent objects of Node.

The complexity of the algorithm is determined by the calculation of the node parity in ns_parity, the node delay in ns_delay, and the growth of the cluster, which is now applied as a recursive function that inspects all nodes in the node tree (ufns.sim.Toric.grow_node). During cluster mergers, additional to union, node-trees are joined by join_node_trees.

Todo

Proper calculation of delay for erasures/empty nodes in the graph

class qsurface.decoders.ufns.elements.Node(primer)¶

Element in the node-tree.

A subgraph \(\mathcal{V}\subseteq C\) is a spanning-tree of a cluster \(C\) if it is a connected acyclic subgraph that includes all vertices of \(C\) and a minimum number of edges. We call the spanning-tree of a cluster its ancilla-tree. An acyclic connected spanning-forest is required for the Union-Find Decoder.

A node-tree \(\mathcal{N}\) is a partition of a ancilla-tree \(\mathcal{V}\), such that each element of the partition – which we call a node \(n\) – represents a set of adjacent vertices that lie at the same distance – the node radius :math:`r` – from the *primer ancilla, which initializes the node and lies at its center. The node-tree is a directed acyclic graph, and its edges \(\mathcal{E}_i\) have lengths equal to the distance between the primer vertices of neighboring nodes.

Parameters: primer (AncillaQubit) – Primer ancilla-qubit.

short¶

Short name of the node.

Type: str

old_bound¶

Current boundary edges.

Type: list

new_bound¶

Next boundary edges.

Type: list

neighbors¶

Neighboring nodes in the node-tree.

Type: list

root_list¶

List of even subroots of merged node-trees.

Type: list

radius¶

Node radius size.

Type: int

parity¶

Node parity.

Type: {0,1}

delay¶

Number of iterations to wait.

Type: int

waited¶

Number of iterations waited.

Type: int

abstract ns_parity()¶: Calculates and returns the parity of the current node.

ns_delay(parent=None, min_delay=None)¶

Calculates the node delay.

Head recursive function that calculates the delays of the current node and all its descendent nodes.

\[n_d = m_d + \lfloor n_r-m_r \rfloor - (-1)^{n_p} |(n,m)|\]

The minimal delay min_delay in the tree is maintained as the actual delay is relative to the minimal delay value within the entire node-tree.

Parameters

parent (Optional[Tuple[Node, int]]) – The parent node and the distance to the parent node.
min_delay (Optional[int]) – Minimal delay value encountered during the current calculation.

Return type

int

class qsurface.decoders.ufns.elements.Syndrome(primer)¶

ns_parity(parent_node=None)¶

Calculates the node parity.

Tail recursive function that calculates the parities of the current node and all its descendent nodes.

\[s_p = \big( \sum_{n \in \text{ children of } s} (1+s_p) \big) \bmod 2\]

Parameters: parent_node (Optional[Node]) – Parent node in node-tree to indicate direction.
Return type: int

class qsurface.decoders.ufns.elements.Junction(primer)¶

ns_parity(parent_node=None)¶

Calculates the node parity.

Tail recursive function that calculates the parities of the current node and all its children.

\[j_p = 1 - \big(\sum_{n \in \text{ children of } j} (1+n_p) \big) \bmod 2.\]

Parameters: parent_node (Optional[Node]) – Parent node in node-tree to indicate direction.
Return type: int

class qsurface.decoders.ufns.elements.OddNode(*args, **kwargs)¶

ns_parity(*args, **kwargs)¶

Calculates and returns the parity of the current node.

Return type: int

qsurface.decoders.ufns.elements.print_tree(current_node, parent_node=None)¶

Prints the node-tree of current_node and its descendents.

Utilizes pptree to print a tree of nodes, which requires a list of children elements per node. Since the node-tree is semi-directional (the root can be any element in the tree), we need to traverse the node-tree from current_node in all directions except for the parent_node to find the children attributes for the current direction.

Parameters

current_node (Node) – Current root of the node-tree to print.
parent_node (Optional[Node]) – Parent node which will not be printed. s

Simulation¶

The following description also applies to ufns.sim.Planar.

class qsurface.decoders.ufns.sim.Toric(*args, **kwargs)¶

Union-Find Node-Suspension decoder for the toric lattice.

Within the combined Union-Find and Node-Suspension data structure, every Cluster is partitioned into one or more Node objectss. The node attribute is monkey-patched to the AncillaQubit object to assist the identification of its parent Node.

The boundary of every cluster is not stored at the cluster object, but divided under its partitioned nodes. Cluster growth is initiated from the root of the node-tree. The attributes root_node and min_delay are monkey-patched to the Cluster object to assist with cluster growth in the Node-Suspension data structure. See grow_node for more.

The current class inherits from unionfind.sim.Toric for its application the Union-Find data structure for cluster growth and mergers. To maintain low operating complexity in UFNS, the following parameters are set of the Union-Find parent class.

parameter	value
weighted_growth	True
weighted_union	True
dynamic_forest	True

new_boundary¶

List of newly found cluster boundary elements.

Type: list

cluster_add_ancilla(cluster, ancilla, parent=None, **kwargs)¶

Recursively adds erased edges to cluster and finds the new boundary.

For a given ancilla, this function finds the neighboring edges and ancillas that are in the the currunt cluster. If the newly found edge is erased, the edge and the corresponding ancilla will be added to the cluster, and the function applied recursively on the new ancilla. Otherwise, the neighbor is added to the new boundary self.new_boundary.

Parameters

cluster (Cluster) – Current active cluster
ancilla (AncillaQubit) – Ancilla from which the connected erased edges or boundary are searched.

bound_ancilla_to_node()¶

Saves the new boundary to their respective nodes.

Saves all the new boundaries found by cluster_add_ancilla, which are of the form [inner_ancilla, edge, outer_ancilla], to the node at inner_ancilla.node. This method is called after cluster union in union_bucket, which also joins the node-trees, such that the new boundary is saved to the updated nodes.

find_clusters(**kwargs)¶

Initializes the clusters on the lattice.

For every non-trivial ancilla on the lattice, a Cluster is initiated. If any set of ancillas are connected by some set of erased qubits, all connected ancillas are found by cluster_add_ancilla and a single cluster is initiated for the set.

Additionally, a syndrome-node is initiated on the non-trivial ancilla – a syndrome – with the ancilla as primer. New boundaries are saved to the nodes by bound_ancilla_to_node.

The cluster is then placed into a bucket based on its size and parity by place_bucket. See grow_clusters for more information on buckets.

grow_clusters(**kwargs)¶

Grows odd-parity clusters outward for union with others until all clusters are even.

Lists of odd-parity clusters are maintained at self.buckets. Starting from bucket 0, odd-parity clusters are popped from the bucket by ‘grow_bucket and grown at the boundary by grow_boundary by adding 1 for every boundary edge in cluster.bound in self.support. Grown clusters are then placed in a new bucket by place_bucket based on its size if it has odd parity.

Edges are fully added to the cluster per two growth iterations. Since a cluster with half-grown edges at the boundary has the same size (number of ancillas) as before growth, but is non-arguably bigger, the degeneracy in cluster size is differentiated by cluster.support. When an union occurs between two clusters during growth, if the merged cluster is odd, it is placed in a new bucket. Thus the real bucket number is saved at the cluster locally as cluster.bucket. These two checks are performed before a cluster is grown in grow_bucket.

The chronology of events per bucket must be the following:

Grow all clusters in the bucket if checks passed.
- Add all odd-parity clusters after growth to place_list.
- Add all merging clusters to union_list.
Merge all clusters in union_list
- Add odd-parity clusters after union to place_list.
Place all clusters in place_list in new bucket if parity is odd.

For clusters with cluster.support==1 or with half-grown edges at the boundary, the new boundary at clusters.new_bound consists of the same half-grown edges. For clusters with cluster.support==0, the new boundary is found by cluster_add_ancilla.

The current implementation of grow_clusters for the ufns decoder currently includes a work-around for a non-frequently occuring bug. Since the grown of a cluster is separated into nodes, and nodes may be buried by surrounding cluster trees such that it is an interior element and has no boundaries, it may be possible that when an odd cluster is grown no edges are actually added to the cluster. In this case, due to cluster parity duality the odd cluster will be placed in the same bucket after two rounds of growth. The work-around is to always check if the previous bucket is empty before moving on to the next one.

grow_boundary(cluster, union_list, **kwargs)¶

Grows the boundary of the cluster.

See grow_clusters for more information. Each element in the root_list of the root node of the cluster is a subroot of an even subtree in the node-tree. From each of these subroots, the node parity and delays are calculated by ns_parity and ns_delay. The node-tree is then recursively grown by grow_node.

Parameters

cluster (Cluster) – The cluster to be grown.
union_list (List[Tuple[AncillaQubit, Edge, AncillaQubit]]) – List of odd-parity clusters to be placed in new buckets.

grow_node(cluster, node, union_list, parent_node=None)¶

Recursive function that grows a node and its descendents.

Grows the boundary list that is stored at the current node if there the current node is not suspended. The condition required is the following:

where \(\mathcal{N}\) is the node-tree. The minimal delay value in the node-tree here stored as cluster.min_delay. Fully grown edges are added to union_list to be later considered by union_bucket.

Parameters

cluster (Cluster) – Parent cluster object of node.
node (Node) – Node to consider for growth.
union_list (List[Tuple[AncillaQubit, Edge, AncillaQubit]]) – List of potential mergers between two cluster-distinct ancillas.
parent_node (Optional[Node]) – Parent node in the node-tree to indicate recursive direction.

grow_node_boundary(node, union_list)¶: Grows the boundary of a node.

union_bucket(union_list, **kwargs)¶

Potentially merges two neighboring ancillas.

If the check by union_check is passed, the clusters of ancilla and new_ancilla are merged. additionally, the node-trees either directly joined, or by the creation of a new junction-node which as new_ancilla as its primer. Weighted union is applied to ensure low operating complexity.

check_compatibility()¶: Checks compatibility of the decoder with the code class and loaded errors.

correct_edge(ancilla_qubit, key, **kwargs)¶

Applies a correction.

The correction is applied to the data-qubit located at ancilla_qubit.parity_qubits[key]. More specifically, the correction is applied to the Edge object corresponding to the state_type of ancilla_qubit.

Return type: AncillaQubit

decode(**kwargs)¶

Decodes the code using the Union-Find algorithm.

Decoding process can be subdivided into 3 sections:

Finding the initial clusters.
Growing and merging these clusters.
Peeling the clusters using the Peeling algorithm.

Parameters: kwargs – Keyword arguments are passed on to find_clusters, grow_clusters and peel_clusters.

flip_edge(ancilla, edge, new_ancilla, **kwargs)¶: Flips the values of the ancillas connected to edge.

get_cluster(ancilla)¶

Returns the cluster to which ancilla belongs to.

If ancilla has no cluster or the cluster is not from the current simulation, none is returned. Otherwise, the root element of the cluster-tree is found, updated to ancilla.cluster and returned.

Parameters: ancilla (AncillaQubit) – The ancilla for which the cluster is to be found.
Return type: Optional[Cluster]

static get_neighbor(ancilla_qubit, key)¶

Returns the neighboring ancilla-qubit of ancilla_qubit in the direction of key.

Return type: Tuple[AncillaQubit, Edge]

get_neighbors(ancilla_qubit, loop=False, **kwargs)¶

Returns all neighboring ancillas, including other time instances.

Parameters: loop (bool) – Include neighbors in time that are not chronologically next to each other during decoding within the same instance.

get_syndrome(find_pseudo=False)¶

Finds the syndrome of the code.

Parameters

find_pseudo (bool, optional) – If enabled, the lists of syndromes returned are not only AncillaQubit objects, but tuples of (ancilla, pseudo), where pseudo is the closest PseudoQubit in the boundary of the code.

Return type

Union[Tuple[List[AncillaQubit], List[AncillaQubit]], Tuple[List[Tuple[AncillaQubit, PseudoQubit]], List[Tuple[AncillaQubit, PseudoQubit]]]]

Returns

list – Plaquette operator syndromes.
list – Star operator syndromes.

grow_bucket(bucket, bucket_i, **kwargs)¶

Grows the clusters which are contained in the current bucket.

See grow_clusters for more information.

Parameters

bucket (List[Cluster]) – List of clusters to be grown.
bucket_i (int) – Current bucket number.

Return type

Tuple[List, List]

Returns

list – List of potential mergers between two cluster-distinct ancillas.
list – List of odd-parity clusters to be placed in new buckets.

peel_clusters(**kwargs)¶

Loops over all clusters to find pendant ancillas to peel.

To make sure that all cluster-trees are fully peeled, all ancillas are considered in the loop. If the ancilla has not been peeled before and belongs to a cluster of the current simulation, the ancilla is considered for peeling by peel_leaf.

peel_leaf(cluster, ancilla)¶

Recursive function which peels a branch of the tree if the input ancilla is a pendant ancilla

If there is only one neighbor of the input ancilla that is in the same cluster, this ancilla is a pendant ancilla and can be peeled. The function calls itself on the other ancilla of the edge leaf.

If [“dynamic_forest”] is disabled, once a pendant leaf is found, the acyclic forest is constructed by static_forest.

Parameters

cluster – Current cluster being peeled.
ancilla – Pendant ancilla of the edge to be peeled.

place_bucket(clusters, bucket_i)¶

Places all clusters in clusters in a bucket if parity is odd.

If weighted_growth is enabled. the cluster is placed in a new bucket based on its size, otherwise it is placed in self.buckets[0]

Parameters

clusters (List[Cluster]) – Clusters to place in buckets.
bucket_i (int) – Current bucket number.

static_forest(ancilla)¶

Constructs an acyclic forest in the cluster of ancilla.

Applies recursively to all neighbors of ancilla. If a cycle is detected, edges are removed from the cluster.

Parameters: ancilla (AncillaQubit) –

union_check(edge, ancilla, new_ancilla, cluster, new_cluster)¶

Checks whether cluster and new_cluster can be joined on edge.

See union_bucket for more information.

Return type: bool

class qsurface.decoders.ufns.sim.Planar(*args, **kwargs)¶

Union-Find Node-Suspension decoder for the planar lattice.

See the description of ufns.sim.Toric.

Plotting¶

class qsurface.decoders.ufns.plot.Toric(*args, **kwargs)¶

Union-Find Node-Suspension decoder for the toric lattice with union-find plot.

Has all class attributes, methods, and nested figure classes from ufns.sim.Toric, with additional parameters below. Default values for these parameters can be supplied via a decoders.ini file under the section of [ufns] (see decoders._template.read_config).

The plotting class initiates a qsurface.plot object. For its usage, see Usage.

Parameters

step_bucket (bool, optional) – Waits for user after every occupied bucket. Default is false.
step_cluster (bool, optional) – Waits for user after growth of every cluster. Default is false.
step_node (bool, optional) – Waits for user after growth of every node. Default is false.
step_cycle (bool, optional) – Waits for user after every edge removed due to cycle detection. Default is false.
step_peel (bool, optional) – Waits for user after every edge removed during peeling. Default is false.

class qsurface.decoders.ufns.plot.Planar(*args, **kwargs)¶

Union-Find Node-Suspension decoder for the planar lattice with union-find plot.

Has all class attributes, methods, and nested figure classes from ufns.sim.Planar, with additional parameters below. Default values for these parameters can be supplied via a decoders.ini file under the section of [ufns] (see decoders._template.read_config).

The plotting class initiates a qsurface.plot object. For its usage, see Usage.

Parameters

step_bucket (bool, optional) – Waits for user after every occupied bucket. Default is false.
step_cluster (bool, optional) – Waits for user after growth of every cluster. Default is false.
step_node (bool, optional) – Waits for user after growth of every node. Default is false.
step_cycle (bool, optional) – Waits for user after every edge removed due to cycle detection. Default is false.
step_peel (bool, optional) – Waits for user after every edge removed during peeling. Default is false.

hu2020thesis: Hu, Mark Shui, Quasilinear Time Decoding Algorithm for Topological Codes with High Error Threshold, DOI: 10.13140/RG.2.2.13495.96162, 2020.