loom.eka.utilities.graph_matrix_utils

Copyright (c) Entropica Labs Pte Ltd 2025.

Use, distribution and reproduction of this program in its source or compiled form is prohibited without the express written consent of Entropica Labs Pte Ltd.

loom.eka.utilities.graph_matrix_utils.binary_gaussian_elimination(matrix)

Performs binary gaussian elimination on an input matrix.

Algorithm reference: https://www.cs.umd.edu/~gasarch/TOPICS/factoring/fastgauss.pdf

Implementation: https://gist.github.com/popcornell/bc29d1b7ba37d824335ab7b6280f7fec

Return type:

ndarray

loom.eka.utilities.graph_matrix_utils.cardinality_distribution(t_graph)

Extracts the edges in a HGP Tanner Graph associated with each cardinality {N,E,S,W}.

Parameters:

t_graph (nx.Graph) – Tanner graph associated with HGP code.

Returns:

edge_dict – A dictionary whose keys are the different cardinalities and the values all the edges associated with it.

Return type:

dict[str,list]

loom.eka.utilities.graph_matrix_utils.extract_subgraphs_from_edge_labels(graph, label_attribute='cardinality')

Extract subgraphs of the Tanner Graphs induced by the edges associated with a particular attribute. This function is mainly used for obtaining the ones associated with the cardinality decorators in the cardinal circuit constructor function.

Parameters:

• graph (nx.Graph) – Tanner Graph from HGP code whose edges are decorated according to the different attributes.

• label_attribute (str) – Edge attribute name. Defaults to cardinality.

Returns:

subgraphs_dict – Dictionary containing the value of each attribute as a key and the associated induced subgraph as a value.

Return type:

dict[str,nx.Graph]

loom.eka.utilities.graph_matrix_utils.find_maximum_matching(graph)

Obtains maximum matching of a bipartite graph.

Parameters:

graph (nx.Graph) – Networkx Graph from which to extract the maximum matching. The graph needs to be bipartite.

Returns:

matching – Matching as dictionary whose values and keys contain the matching connections between nodes.

Return type:

dict[int,int]

loom.eka.utilities.graph_matrix_utils.minimum_edge_coloring(graph)

Computes the minimum edge coloring of a bipartite graph graph. The chromatic index for all bipartite graphs is equal to the maximum degree of the graph. In the context of leveraging this algorithm for circuit construction, this is equivalent to distributing more gates into a single layer.

Parameters:

graph (nx.Graph) – A bipartite graph.

Returns:

coloring – Minimum edge coloring as a dictionary where keys are color indices and values the list of edges.

Return type:

dict[int,list]

loom.eka.utilities.graph_matrix_utils.verify_css_code_condition(hx, hz)

Verifies that the parity-check matrices define a valid CSS code, by checking that the X and Z check matrices are orthogonal, i.e. that the stabilizers commute.

Parameters:

• hx (np.ndarray) – X parity-check matrix.

• hz (np.ndarray) – Z parity-check matrix.

Returns:

valid – If True, the parity-check matrices define a valid CSS code.

Return type:

bool