Generalizing LPCode to Non-Commutative and ℓ-Dimensional Associative Algebras

[Fe-r-oz]

Is your feature request related to a problem? Please describe.

The paper Asymptotically Good Quantum and Locally Testable Classical LDPC Codes developed the LPCode construction for non-abelian groups, where the $R$ is not necessarily commutative. The current limitation of #356 is that it works only with "commutative" group algebra R. When R is commutative, "we do not need to distinguish the left and the right representations". What that means that for A and B GroupAlgebraElemMatrix, we don't specify any particular group action as we see the default left representation is used for both A and B. In the following line, repr is Hecke.representation_matrix

QuantumClifford.jl/ext/QuantumCliffordHeckeExt/lifted.jl

Line 93 in 5fcf353

x = repr.(mat)

Hence, the LPCode currently works as Abelian LPCode. To generalize it, Panteleev and Kalachev remarked that for matrices $A$ and $B$, we use the right regular representation for $A$ and the left regular representation for $B$ to form the block matrices $\hat{A}$ and $\hat{B}$, defining the CSS code $LP(A, B)$. This approach also works well with any $\ell$-dimensional associative algebra $R$ over $\mathbb{F}_q$, not necessarily commutative, if we use the right (resp. left) regular matrix representation of its elements as the entries of $\hat{A}$ (resp. $\hat{B}$). When $R$ is not commutative, it becomes necessary to distinguish between the right and left regular representations to ensure the correct construction of the block matrices.

This construction method is presented in foot note 4, page 3 and detailed in appendix B (Page 48) of the aforementioned paper

Related Issue: #405

Note: Non-abelian groups satisfy the CSS orthogonality condition $L(a)R(b) = R(b)L(a)$

julia> using QuantumClifford

julia> using QuantumClifford.ECC: check_repr_commutation_relation

julia> using Oscar: dihedral_group, alternating_group

julia> G = dihedral_group(6);

julia> GA = group_algebra(GF(2), G);

julia> check_repr_commutation_relation(GA)
true

julia> G = alternating_group(4);

julia> GA = group_algebra(GF(2), G);

julia> check_repr_commutation_relation(GA)
true

When the algebra R is commutative, then ρ_r = λ_r for each r ∈ R, and we do not need to distinguish the left and the right representations of R.

julia> using Oscar

julia> G = cyclic_group(6);

julia> GA = group_algebra(GF(2), G);

julia> a = rand(GA);

julia> L_a = representation_matrix(a);

julia> R_a = representation_matrix(a, :right);

julia> L_a == R_a
true

For non-commutative Algebra (non-abelian groups):

julia> G = dihedral_group(6);

julia> GA = group_algebra(GF(2), G);

julia> a = rand(GA);

julia> L_a = representation_matrix(a);

julia> R_a = representation_matrix(a, :right);

julia> L_a == R_a
false

Therefore: For any two matrices $A \in \mathbb{R}^{m_a \times n_a}$ and $B \in \mathbb{R}^{m_b \times n_b}$, we can replace their elements by the corresponding right and left matrix representations to obtain the block matrices $\hat{A}$, $\hat{B}$ and get to $LP(A, B)$.

We can use Hecke.is_commutative instead of manually checking $L(a) = R(a)$ for each $a ∈ G$.

Abelian Groups

julia> using Hecke: is_commutative

julia> using Oscar: cyclic_group

julia> G = cyclic_group(6);

julia> GA = group_algebra(GF(2), G);

julia> is_commutative(GA)
true

Non-Abelian Groups

julia> using Hecke: is_commutative

julia> using Oscar: dihedral_group

julia> G = dihedral_group(6);

julia> GA = group_algebra(GF(2), G);

julia> is_commutative(GA)
false

Describe the solution you’d like

• For non commutative algebra (non-abelian groups), use the right (resp. left) regular matrix representation of its elements as the entries of $\hat{A}$ (resp. $\hat{B}$).
• Resolve Inconsistency in two_block_group_algebra_codes (2BGA) for non-abelian groups #405
• Using Hecke.jl, generalize the LPCode such that it works for associative_algebra. For more details on associative_algebra, see: https://github.com/thofma/Hecke.jl/blob/e76d83a97bf3e70437f37701d1e98703d0d68642/src/AlgAss/StructureConstantAlgebra.jl#L63.

Additional Context

Panteleev and Kalachev remarked in aforementioned paper that they used all abelian codes in their previous paper: Quantum LDPC Codes with Almost Linear Minimum Distance