Information¶

The Union-Find decoder [delfosse2017almost] maps each element of the syndrome \(\sigma\) to an ancilla \(v\) in a non-connected graph defined on the code lattice. From this starting point, it grows clusters around these ancillas by repeatedly adding a layer of edges and ancillas to existing clusters, until all clusters have an even number of non-trivial syndrome ancillas. Then, it selects a spanning tree \(F\) for each cluster.

The leaves of each spanning tree are conditionally peeled in a tail-recursive breadth-first search until all non-trivial syndrome ancillas are paired and linked by a path within \(F\), which is the correcting operator \(\mathcal{C}\) [delfosse2017linear]. The strategy for constructing the clusters turns out to have a strong effect on performance. For instance, the threshold for bitflip noise of a decoder that grows the clusters following a random order is 9.2% [delfosse2017almost], while if the clusters are grown in order of cluster size, which we call Weighted Growth, the threshold increases to 9.9% [delfosse2017almost].

The complexity of the Union-Find decoder is driven by the merging of the clusters. For this, the algorithm uses the Union-Find or disjoint-set data structure [tarjan1975efficiency]. This data structure contains a set of elements, in this case ancillas on the lattice. The set of elements is represented by a two-level tree. At the root of the tree sits one element chosen arbitrarily; the rest of the elements are linked to the root element. The structure admits two functions: \(Find\) and \(Union\). Given \(v\) an element from the structure, the function \(Find(v)\) returns the root element of the tree. This is is used to identify the cluster to which \(v\) belongs. The second function is \(Union(u, v)\), this function merges the sets associated with elements \(u\) and \(v\). This requires pointing all the elements of one of the sets to the root of the other. In order to minimize the number of operations the root of the set with the larger number of elements is chosen as root for the merged set, this is called Weighted Union. In this context, \(Union\) is used when the growth of a cluster requires adding a vertex that belongs to another.

class qsurface.decoders.unionfind.elements.Cluster(index, instance, **kwargs)¶

CLuster of AncillaQubit objects.

A disjoint set, or cluster, of ancilla-qubits. The size of the cluster is equal to the number of qubits in the cluster. The parity of the cluster is equal to the number of non-trivial ancilla-qubits in the cluster.

A cluster can be joined with another by union. Joined clusters are stored in the union-find data structure [tarjan1975efficiency]. The representative element or root cluster is returned by find.

Parameters

index (int) – Indicator index number.
instance (float) – The epoch timestamp of the simulation.

size¶

Size of this cluster based on the number contained ancillas.

Type: int

support¶

Growth state of the cluster.

Type: int

parity¶

Parity of this cluster based on the number non-trivial ancilla-qubits.

Type: int

parent¶

The parent cluster of the current cluster.

Type: Cluster

bound, new_bound

The current and next boundary of the current cluster.

Type: list, [[inner_ancilla, edge, outer_ancilla],...]

bucket¶

The bucket number the current ancilla belongs to.

Type: int

on_bound¶

Whether this cluster is connected to the boundary.

Type: bool

add_ancilla(ancilla)¶: Adds an ancilla to a cluster.

find(**kwargs)¶

Finds the representative root cluster.

The function is applied recursively until the root element of the union-find tree is encountered. The representative root element is returned. Path compression is applied to reduce the depth of the tree.

Examples

For joined clusters in the union-find data structure:

    cl0
    / \
  cl1 cl2
  /
cl2

the representative element can be found by

>>> cl2.find()
cl0

Return type: Cluster

union(cluster, **kwargs)¶

Merges two clusters.

The cluster is made a child of the current cluster. The joined size and parity attributes are updated.

Parameters: cluster (Cluster) – The cluster to merge with self.

Examples

For two clusters cl0 and cl1, cl0.union(cl1) results in the following tree:

  cl0
  /
cl1

Simulation¶

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

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

Union-Find decoder for the toric lattice.

In this implementation, cluster properties are not stored at the root of the tree. Instead, ancillas are collected within Cluster objects, which contain the union and find methods.

Default values for the following parameters can be supplied via a decoders.ini file under the section of [unionfind].

The cluster and peeled attributes are monkey patched to the AncillaQubit object to assist the identification of its parent cluster and to assist peeling. The forest attribute is monkey-patched to AncillaQubit and Edge if a dynamic forest is not maintained to assist with the construction of the acyclic forest after cluster growth.

Parameters

weighted_growth (bool, optional) – Enables weighted growth via bucket growth. Default is true. See grow_clusters.
weighted_union (bool, optional) – Enables weighted union, Default is true. See union_bucket.
dynamic_forest (bool, optional) – Enables dynamically mainted forests. Default is true.
print_steps (bool, optional) – Prints additional decoding information. Default is false.
kwargs – Keyword arguments are forwarded to Sim.

support¶

Dictionary of growth states of all edges in the code.

value	state
2	fully grown
1	half grown
0	none
-1	removed by cycle or peel
-2	added to matching

Type: dict

buckets¶

Ordered dictionary (by index) for bucket growth (implementation of weighted growth). See grow_clusters.

Type: defaultdict

bucket_max_filled¶

The hightest occupied bucket. Allows for break from bucket loop.

Type: int

clusters¶

List of all clusters at initialization.

Type: list

cluster_index¶

Index value for cluster differentiation.

Type: int

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.

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]

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_bound.

Parameters

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

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.

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.

If weighted_growth is disabled, odd-parity clusters are always placed in self.buckets[0]. The same checks for cluster.bucket and cluster.support are applied to ensure clusters growth is valid.

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.

grow_boundary(cluster, union_list, **kwargs)¶

Grows the boundary of the cluster.

See grow_clusters for more information.

Parameters

cluster (Cluster) – The cluster to be grown.
union_list (List[Tuple[AncillaQubit, Edge, AncillaQubit]]) – List of potential mergers between two cluster-distinct ancillas.

union_bucket(union_list, **kwargs)¶

Merges clusters in union_list if checks are passed.

Items in union_list consists of [ancillaA, edge, ancillaB] of two ancillas that, at the time added to the list, were not part of the same cluster. The cluster of an ancilla is stored at ancilla.cluster, but due to cluster mergers the cluster at ancilla_cluster may not be the root element in the cluster-tree, and thus the cluster must be requested by ancilla.cluster. find. Since the clusters of ancillaA and ancillaB may have already merged, checks are performed in union_check after which the clusters are conditionally merged on edge by union_edge.

If weighted_union is enabled, the smaller cluster is always made a child of the bigger cluster in the cluster-tree. This ensures the that the depth of the tree is minimized and the future calls to find is reduced.

If dynamic_forest is disabled, cycles within clusters are not immediately removed. The acyclic forest is then later constructed before peeling in peel_leaf.

Parameters: union_list (List[Tuple[AncillaQubit, Edge, AncillaQubit]]) – List of potential mergers between two cluster-distinct ancillas.

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

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.

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.

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

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) –

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

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.

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

Union-Find decoder for the planar lattice.

See the description of unionfind.sim.Toric.

Plotting¶

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

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

Has all class attributes and methods from unionfind.sim.Toric, with additional parameters below. Default values for these parameters can be supplied via a decoders.ini file under the section of [unionfind] (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_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 Figure2D(decoder, name, *args, **kwargs)¶

Visualizer for the Union-Find decoder and Union-Find based decoders with perfect measurements.

Parameters

args – Positional and keyword arguments are forwarded to plot.Template2D.
kwargs – Positional and keyword arguments are forwarded to plot.Template2D.

class Figure3D(*args, **kwargs)¶

Visualizer for the Union-Find decoder and Union-Find based decoders with faulty measurements.

Parameters

args – Positional and keyword arguments are forwarded to Figure2D and plot.Template3D.
kwargs – Positional and keyword arguments are forwarded to Figure2D and plot.Template3D.

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

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

Has all class attributes and methods from unionfind.sim.Planar, with additional parameters below. Default values for these parameters can be supplied via a decoders.ini file under the section of [unionfind] (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_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.
kwargs – Keyword arguments are passed on to unionfind.sim.Planar.

class Figure2D(decoder, name, *args, **kwargs)¶

Visualizer for the Union-Find decoder and Union-Find based decoders with perfect measurements.

Parameters

args – Positional and keyword arguments are forwarded to unionfind.plot.Toric.Figure2D.
kwargs – Positional and keyword arguments are forwarded to unionfind.plot.Toric.Figure2D.

class Figure3D(*args, **kwargs)¶

Visualizer for the Union-Find decoder and Union-Find based decoders with faulty measurements.

Parameters

args – Positional and keyword arguments are forwarded to Figure2D and plot.Template3D.
kwargs – Positional and keyword arguments are forwarded to Figure2D and plot.Template3D.

delfosse2017almost(1,2,3): Delfosse, Nicolas and Nickerson, Naomi H., Almost-linear time decoding algorithm for topological codes, arXiv preprint arXiv:1709.06218, 2017.
delfosse2017linear: Delfosse, Nicolas and Zemor, Gilles, Linear-time maximum likelihood decoding of surface codes over the quantum erasure channel, arXiv preprint arXiv:1703.01517, 2017.
tarjan1975efficiency(1,2): Tarjan, Robert, Efficiency of a good but not linear set union algorithm, Journal of the ACM, 22(2)215-225, 1975.