qldpc package

Subpackages

Submodules

qldpc module

qldpc.abstract module

Module for abstract algebra: groups, algebras, and representations thereof

Copyright 2023 The qLDPC Authors and Infleqtion Inc.

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.

All groups in this module are finite, and represented under the hood as a SymPy PermutationGroup, or a subgroup of the symmetric group. Group members subclass the SymPy Permutation class.

Groups additionally come equipped with a representation, or “lift”, that maps group elements to square matrices, such that the group action gets lifted to matrix multiplication.

!!! WARNINGS !!!

Whereas matrices are “left-acting” (that is, act on objects from the left) by standard convention, SymPy permutations are “right-acting”, which is to say that the action of two permutations p and q on an integer i compose as (p*q)(i) = q(p(i)) = i^p^q. To preserve the order of products before and after lifting permutations to matrices, which ensures that the lift L(p*q) = L(p) @ L(q), we therefore make representations likewise right-acting, which is to say that a permutation matrix M transposes a vector v as v –> v @ M. In practice, this simply means that matrices are the transpose of what one might expect.

This module only supports representations of group members by orthogonal matrices over finite fields. The restriction to orthogonal representations allows identifying the “transpose” of a group member p with respect to a representation (lift) L, which is defined by enforcing L(p.T) = L(p).T. If the representation is orthogonal, then p.T is equal to the inverse ~p = p**-1.

class qldpc.abstract.AbelianGroup(*orders: int, product_lift: bool = False)[source]

Bases: Group

Direct product of cyclic groups of the specified orders.

By default, an AbelianGroup member of the form ∏_i g_i^{a_i}, where {g_i} are the generators of the group, gets lifted to a direct sum ⨁_i L(g_i)^{a_i}. If an AbelianGroup is initalized with product_lift=True, the group members get lifted to a Kronecker product ⨂_i L(g_i)^{a_i}.

class qldpc.abstract.AlternatingGroup(degree: int)[source]

Bases: Group

Alternating group: even permutations of a set with a given number of elements.

class qldpc.abstract.CyclicGroup(order: int)[source]

Bases: Group

Cyclic group of a specified order.

The cyclic group has one generator, g. All members of the cyclic group of order R can be written as g^p for an integer power p in {0, 1, …, R-1}. The member g^p can be represented by (that is, lifted to) an R×R “shift matrix”, or the identity matrix with all rows shifted down (equivalently, all columns shifted right) by p. That is, the lift L(g^p) acts on a standard basis vector <i| as <i| L(g^p) = < i + p mod R |.

class qldpc.abstract.DihedralGroup(sides: int)[source]

Bases: Group

Dihedral group: symmetries of a regular polygon with a given number of sides.

class qldpc.abstract.Element(group: Group, *members: GroupMember)[source]

Bases: object

An element of a group algebra over a finite field F_q.

Each Element x is a sum of group members with coefficients in F_q: x = sum_{g in G} x_g g, with each x_g in F_q.

The field F_q is taken to be the same as that of the representation of the group.

property T: Element

Transpose of this element.

If this element is x = sum_{g in G) x_g g, return x.T = sum_{g in G} x_g g.T, where g.T is the group member for which the lift L(g.T) = L(g).T. The fact that group members get lifted to orthogonal matrices implies that g.T = ~g = g**-1.

copy() → Element[source]: Copy of self.

property field: type[FieldArray]: Base field of this algebra.

property group: Group: Base group of this algebra.

lift() → FieldArray[source]: Lift this element using the underlying group representation.

one() → Element[source]: One (multiplicative identity) element.

zero() → Element[source]: Zero (additive identity) element.

class qldpc.abstract.Group(*generators: Permutation, field: int | None = None, lift: Callable[[GroupMember], ndarray[Any, dtype[int64]]] | None = None, name: str | None = None)[source]

Bases: object

Base class for a finite group.

Under the hood, a Group is represented by a SymPy PermutationGroup. Group elements are represented by SymPy permutations.

A group additionally comes equipped with a “lift”, or a representation that maps group elements to orthogonal matrices over a finite field. The group action gets lifted to matrix multiplication. If no lift is provided, the group will default to the representation of group members by explicit permutation matrices.

property field: type[FieldArray]: Base field of this group.

classmethod from_generating_mats(*matrices: ndarray[Any, dtype[int64]] | Sequence[Sequence[int]], field: int | None = None) → Group[source]

Constructs a Group from a given set of generating matrices.

Group members are represented by how they permute elements of the group itself.

classmethod from_name(name: str) → Group[source]: Named group in the GAP computer algebra system.

classmethod from_sympy(group: PermutationGroup, field: int | None = None, lift: Callable[[GroupMember], ndarray[Any, dtype[int64]]] | None = None) → Group[source]: Instantiate a Group from a SymPy permutation group.

classmethod from_table(table: ndarray[Any, dtype[int64]] | Sequence[Sequence[int]], field: int | None = None, integer_lift: Callable[[int], ndarray[Any, dtype[int64]]] | None = None) → Group[source]: Construct a group from a multiplication (Cayley) table.

generate() → Iterator[GroupMember][source]: Iterate over all group members.

property generators: Sequence[GroupMember]: Generators of this group.

property identity: GroupMember: The identity element of this group.

lift(member: GroupMember) → FieldArray[source]: Lift a group member to its representation by an orthogonal matrix.

property lift_dim: int: Dimension of the repesentation for this group.

property name: str: A name for this group, which is not required to uniquely identify the group.

property order: int: Number of members in this group.

classmethod product(*groups: Group, repeat: int = 1) → Group[source]: Direct product of Groups.

random(*, seed: int | None = None) → GroupMember[source]: A random element this group.

random_symmetric_subset(size: int, *, exclude_identity: bool = False, seed: int | None = None) → set[GroupMember][source]

Construct a random symmetric subset of a given size.

Note: this is not a uniformaly random subset, only a “sufficiently random” one.

WARNING: if excluding the identity element, not all groups have symmetric subsets of arbitrary size. If called with a poor choice of group and subset size, this method may never terminate.

property table: ndarray[Any, dtype[int64]]: Multiplication (Cayley) table for this group.

to_sympy() → PermutationGroup[source]: The underlying SymPy permutation group of this Group.

class qldpc.abstract.GroupMember(*args, size=None, **kwargs)[source]

Bases: Permutation

Wrapper for SymPy Permutation class.

Supports sorting permutations (by their rank), and taking their tensor product.

default_assumptions = {}

classmethod from_sympy(other: Permutation) → GroupMember[source]: Convert a SymPy Permutation into a GroupMember.

qldpc.abstract.PSL: alias of ProjectiveSpecialLinearGroup

class qldpc.abstract.ProjectiveSpecialLinearGroup(dimension: int, field: int | None = None, linear_rep: bool = True)[source]

Bases: Group

Projective special linear group (PSL = SL/center).

Here “center” is the subgroup of SL that commutes with all elements of SL. Specifically, every element in the center of SL is a scalar multiple of the identity matrix I. In the case of SL(d,q) (d×d matrices over F_q with determinant 1), the determinant of scalar*I is scalar**d, which is only contained in SL(d,q) if scalar**d == 1.

Altogether, we construct PSL(d,q) by SL(d,q) mod [d-th roots of unity over F_q].

property dimension: int: Dimension of the elements of this group.

classmethod get_generating_mats(dimension: int, field: int | None = None) → tuple[FieldArray, FieldArray][source]: Generating matrices of PSL, constructed out of the generating matrices of SL.

classmethod iter_mats(dimension: int, field: int | None = None) → Iterator[FieldArray][source]: Iterate over all elements of PSL(dimension, field).

class qldpc.abstract.Protograph(data: ndarray[Any, dtype[object_]] | Sequence[Sequence[object]], group: Group | None = None)[source]

Bases: ndarray[Any, dtype[object_]]

Array whose entries are members of a group algebra over a finite field.

property T: Protograph: Transpose of this protograph, which also transposes every array entry.

classmethod build(group: Group, data: ndarray[Any, dtype[object_ | int64]] | Sequence[Sequence[object | int]]) → Protograph[source]

Construct a protograph.

The constructed protograph is built from: - a group, and - an array populated by

elements of the group algebra,

group members, or

integers.

Integers and group members are “elevated” to elements of the group algebra.

property field: type[FieldArray]: Base field of this protograph.

property group: Group: Base group of this protograph.

lift() → FieldArray[source]: Block matrix obtained by lifting each entry of the protograph.

class qldpc.abstract.QuaternionGroup[source]

Bases: Group

Quaternion group: 1, i, j, k, -1, -i, -j, -k.

qldpc.abstract.SL: alias of SpecialLinearGroup

class qldpc.abstract.SmallGroup(order: int, index: int)[source]

Bases: Group

Group indexed by the GAP computer algebra system.

classmethod generator(order: int) → Iterator[SmallGroup][source]: Iterator over all groups of a given order.

classmethod get_structure(order: int, index: int) → str[source]: Retrieve a description of the structure of a group.

index: int

classmethod number(order: int) → int[source]: The number of groups of a given order.

property structure: str: A description of the structure of this group.

class qldpc.abstract.SpecialLinearGroup(dimension: int, field: int | None = None, linear_rep: bool = True)[source]

Bases: Group

Special linear group (SL): square matrices with determinant 1.

property dimension: int: Dimension of the elements of this group.

classmethod get_generating_mats(dimension: int, field: int | None = None) → tuple[FieldArray, FieldArray][source]: Generating matrices for the Special Linear group, based on arXiv:2201.09155.

classmethod iter_mats(dimension: int, field: int | None = None) → Iterator[FieldArray][source]: Iterate over all elements of SL(dimension, field).

class qldpc.abstract.SymmetricGroup(symbols: int)[source]

Bases: Group

Symmetric group: all permutations of a given number of symbols.

class qldpc.abstract.TrivialGroup(field: int | None = None)[source]

Bases: Group

The trivial group with one member: the identity.

random(*, seed: int | None = None) → GroupMember[source]

A random (albeit unique) element this group.

Necessary to circumvent an error thrown by sympy when “unranking” an empty Permutation.

classmethod to_protograph(data: ndarray[Any, dtype[int64]] | Sequence[Sequence[int]], field: int | None = None) → Protograph[source]: Convert a matrix of 0s and 1s into a protograph of the trivial group.

qldpc.abstract.default_lift(member: GroupMember) → ndarray[Any, dtype[int64]][source]

Default lift: represent a permutation object by a permutation matrix.

For consistency with how SymPy composes permutations, this matrix is right-acting, meaning that it acts on a vector p from the right: p –> p @ M.

qldpc.cache module

Helper function(s) for caching results

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.

qldpc.cache.get_disk_cache(cache_name: str, *, cache_dir: str | None = None) → Cache[source]: Retrieve a dictionary-like cache object.

qldpc.cache.use_disk_cache(cache_name: str, *, cache_dir: str | None = None) → Callable[[Callable[[...], Any]], Callable[[...], Any]][source]: Decorator to cache results to disk.

qldpc.decoder module

Decoding a syndrome with a parity check matrix

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.

qldpc.decoder.decode(matrix: ndarray[Any, dtype[int64]], syndrome: ndarray[Any, dtype[int64]], **decoder_args: object) → ndarray[Any, dtype[int64]][source]

Find a vector that solves matrix @ vector == syndrome mod 2.

If passed an explicit decoder, use it.
If passed with_ILP=True, solve exactly with an integer linear program.
Otherwise, use a BP-OSD decoder.

In all cases, pass the decoder_args to the decoder that is used.

qldpc.decoder.decode_with_BP_OSD(matrix: ndarray[Any, dtype[int64]], syndrome: ndarray[Any, dtype[int64]], **decoder_args: object) → ndarray[Any, dtype[int64]][source]

Decode with belief propagation with ordered statistics (BP+OSD).

For details about the BD-OSD decoder and its arguments, see: - Documentation: https://roffe.eu/software/ldpc/ldpc/osd_decoder.html - Reference: https://arxiv.org/abs/2005.07016

qldpc.decoder.decode_with_ILP(matrix: ndarray[Any, dtype[int64]], syndrome: ndarray[Any, dtype[int64]], **decoder_args: object) → ndarray[Any, dtype[int64]][source]

Decode with an integer linear program (ILP).

Supports integers modulo q for q > 2 with a “modulus” argument.

If a “lower_bound_row” argument is provided, treat this linear constraint (by index) as a lower bound (>=), rather than an equality (==) constraint.

All remaining keyword arguments are passed to cvxpy.Problem.solve.

qldpc.decoder.decode_with_MWPM(matrix: ndarray[Any, dtype[int64]], syndrome: ndarray[Any, dtype[int64]], **decoder_args: object) → ndarray[Any, dtype[int64]][source]: Decode with minimum weight perfect matching (MWPM).

qldpc.objects module

Instrumental objects used to construct error-correcting codes

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.

class qldpc.objects.CayleyComplex(subset_a: Collection[GroupMember], subset_b: Collection[GroupMember] | None = None, *, bipartite: bool = False)[source]

Bases: object

Left-right Cayley complex, used for constructing quantum Tanner codes.

A Cayley complex is a geometric structure that is built out of two subsets A and B of a group G. The subsets respectively act on elements of G from the left and right, and must be symmetric, which is to say (for example) that if a ∈ A, then a^-1 ∈ A.

The generating data (A,B) is used to build vertices V, edges E, and faces F as follows: - vertices are members of G, - edges have the form (g, ag) and (g, gb), and - faces f(g,a,b) have the form {g, ab, gb, agb}:

g → gb ↓ ↓

ag → agb

If the complex is disconnected, we keep only the component connected to the identity element.

After constructing the complex (V,E,F), we can define two bipartite directed graphs: - subgraph_x with edges ( g, f(g,a,b)), and - subgraph_z with edges (ag, f(g,a,b)). These graphs are used to construct classical Tanner codes that serve as the X and Z sectors of a quantum CSS code known as a quatnum Tanner code.

There are, however, two complications to keep in mind. First, in order for the faces to be nondegenerate (that is, for each face to contain four vertices), the generating data (A,B) must satisfy the Total No Conjugacy condition:

[1] ag != gb for all g,a,b in (G,A,B).

Second, in order to construct a valid quantum Tanner code out of subgraph_x and subgraph_z, the graph (V,E) must be bipartite, V = V_0 ∪ V_1, such that (for example) nodes {g, agb} are in one partition, while nodes {ag, gb} are in the other partition. The nodes V_0 and V_1 are then used as the source nodes of subgraph_x and subgraph_z. The graph (V,E) is bipartite if:

[2] The Cayley graphs (G;A) and (G;B) both are bipartite.

The Cayley graphs (G;A) and (G;B) are graphs whose - vertices are members of G, and - edges are pairs of vertices connected by A or B, as in (g, ag) or (g, gb).

In fact, condition [2] can be enforced at no added cost by taking the double cover of G and modifying members of A and B as: - G –> G ⨂ Z_2, - a –> (a,1), and - b –> (b,1), where Z_2 ~ {0,1} is the 2-element group (under addition), such that (a,1) * (g,i) = (ag,i+1) and (g,i) * (b,1) = (gb,i+1). The complex generated by A and B after this modification is the “bipartite” Cayley complex constructed in https://arxiv.org/abs/2202.13641.

If requirement [1] is not satisfied, then we can construct a “quadripartite” complex that enforces [1] and [2] by taking the quadruple cover of G and modifying members of A and B as: - G –> G ⨂ Z_2 ⨂ Z_2, - a –> (a,1,0), and - b –> (b,0,1), where similarly to before (a,1,0) * (g,i,j) = (ag,i+1,j) and (g,i,j) * (b,0,1) = (gb,i,j+1). This modification of A and B corresponds to the “quadripartite” Cayley complex constructed in https://arxiv.org/abs/2206.07571.

References: - https://arxiv.org/abs/2202.13641 - https://arxiv.org/abs/2206.07571 - https://www.youtube.com/watch?v=orWcstqWGGo

bipartite: bool

classmethod build_cayley_graph(subset_a: set[GroupMember], subset_b: set[GroupMember]) → None[source]: Build a left-right Cayley graph generated from the identity element of a group.

property cover_subset_a: set[GroupMember]: Subset induced by taking the double cover(s) of the group for this complex.

property cover_subset_b: set[GroupMember]: Subset induced by taking the double cover(s) of the group for this complex.

property graph: Graph: Graph consisting of the nodes and edges of the complex.

classmethod satisfies_total_no_conjugacy(subset_a: Collection[GroupMember], subset_b: Collection[GroupMember]) → bool[source]: Check the Total No-Conjugacy condition: aa gg != gg bb for all gg, aa, bb.

subset_a: set[GroupMember]

subset_b: set[GroupMember]

class qldpc.objects.ChainComplex(*ops: ndarray[Any, dtype[int64]] | Protograph, field: int | None = None, skip_validation: bool = False)[source]

Bases: object

Chain complex: a sequence modules with “boundary operators” that map between them.

An n-chain complex with modules (A_0, A_1, …, A_n) can be written as

{} <–[d_0] A_0 <–[d_1] A_1 <– … <–[d_n] A_n <–[d_{n+1}] {}

Here j is called the “degree” of A_j, and d_j : A_j –> A_{j-1} is a “boundary operator” or “differential”. Neighboring boundary operators annihilate, in the sense that d_j d_{j-1} = 0.

In practice, we represent a chain complex by the boundary operators (d_1, d_2, …, d_n), which are in turn represented by matrices over (i) a finite field, or (ii) a group algebra. The boundary operators d_0 and d_{n+1} are formally treated as 0 × dim(A_0) and dim(A_n) × 0 matrices.

References: - https://en.wikipedia.org/wiki/Chain_complex - https://arxiv.org/abs/1810.01519 - https://arxiv.org/abs/2103.06309

property T: ChainComplex: Transpose and reverse the order of the boundary operators in this chain complex.

dim(degree: int) → int[source]: The dimension of the module of the given degree.

property field: type[FieldArray]: The base field of this chain complex.

property group: Group | None: The base group of this chain complex.

property num_links: int: The number of “internal” links in this chain complex.

op(degree: int) → ndarray[Any, dtype[int64]] | Protograph[source]: The boundary operator of this chain complex that acts on the module of a given degree.

property ops: tuple[ndarray[Any, dtype[int64]] | Protograph, ...]: The boundary operators of this chain complex.

Tensor product of two chain complexes.

The tensor product of chain complexes C_A and C_B, respectively with modules (A_0, A_1, …) and (B_0, B_1, …), is a new chain complex C_P with modules (P_0, P_1, …). The module P_k of degree k can be written as a direct sum of tensor products A_i ⨂ B_j for which i+j=k, that is:

[1] P_k = ⨁_{i+j=k} A_i ⨂ B_j.

Elements of P_2, for example, can be written as vectors [a_2 ⨂ b_0, a_1 ⨂ b_1, a_0 ⨂ b_2], that concatenate different a_i ⨂ b_j ∈ A_i ⨂ B_j.

The boundary operator d_k in C_P is defined by its action on each “sector” (i, j), namely

[2] d_{i+j}(a_i ⨂ b_j) = d_i^A(a_i) ⨂ b_j + (-1)^i a_i ⨂ d_j^B(b_j),

where d_i^A and d_j^B are boundary operators of C_A and C_B.

In practice, to construct a boundary operator d_k we build a block matrix whose rows and columns correspond, respectively, to sectors of P_{k-1} and P_k. We then populate this block matrix by the maps between sectors of P_k and P_{k-1} that are induced by the definition of d_{i+j}.

class qldpc.objects.Node(index: int, is_data: bool = True)[source]

Bases: object

Node in a Tanner graph.

A node essentially an integer index, together with a boolean flag to distinguish “data” node from a “check” node in an error-correcting code.

index: int

is_data: bool = True

class qldpc.objects.Pauli(value)[source]

Bases: Enum

Pauli operators.

I = (0, 0)

X = (1, 0)

Y = (1, 1)

Z = (0, 1)

classmethod from_string(string: str) → Pauli[source]: Build a Pauli operator from a string.

property index: int: Numerical index for Pauli operators.

class qldpc.objects.QuditOperator(value: tuple[int, int] = (0, 0))[source]

Bases: object

A qudit operator of the form X(val_x)*Z(val_z).

classmethod from_string(string: str) → QuditOperator[source]: Build a qudit operator from its string representation.

qldpc package

Subpackages

Submodules

qldpc module

qldpc.abstract module

qldpc.cache module

qldpc.decoder module

qldpc.objects module

Module contents