loom.eka.utilities.graph_matrix_utils

Licensed under the Apache License, Version 2.0 (the “License”); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an “AS IS” BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

loom.eka.utilities.graph_matrix_utils.binary_gaussian_elimination(matrix)[source]

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)[source]

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')[source]

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)[source]

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)[source]

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)[source]

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