Inconsistency in two_block_group_algebra_codes (2BGA) for non-abelian groups

[Fe-r-oz]

Describe the bug 🐞

There is an inconsistency in the two_block_group_algebra_codes (2BGA) implementation in #356. The current 2BGA code follows the standard definition as outlined in the literature. However, when non-abelian groups are used, the resulting stabilizer matrix becomes non-commutative, causing the check_allrowscommute test within stab_looks_good to fail.

The group algebra construction, group_algebra(GF(2), parent(group_elem_array[1,1])), permits the use of non-abelian groups as per the standard definition for 2BGA codes. To illustrate this, a dihedral group can be used as an example. We have found that, although the code parameters are correct, the stabilizer matrix fails to be commutative.

QuantumClifford.jl/ext/QuantumCliffordHeckeExt/lifted.jl

Line 67 in f3eb7cd

function LiftedCode(group_elem_array::Matrix{<: GroupOrAdditiveGroupElem}; GA::GroupAlgebra=group_algebra(GF(2), parent(group_elem_array[1,1])), repr::Union{Function, Nothing}=nothing)

Expected behavior

The expectation is that the stabilizer matrix should be commutative. After all, non-abelian groups satisfy the CSS orthogonality condition, which is verified by the commutativity of the left and right representation matrices in the group algebra of non-abelian groups.

This inconsistency was overlooked because non-abelian groups were not tested during the implementation of the 2BGA.

For more details, https://arxiv.org/pdf/1407.6228, Appendix B of https://arxiv.org/pdf/2111.03654

Minimal Reproducible Example 👇

[[24, 8, 3]] from Table 3, Example 1: of https://arxiv.org/pdf/2306.16400.

julia> using QuantumClifford: check_allrowscommute, stab_looks_good; using QuantumClifford.ECC: two_block_group_algebra_codes, code_n, code_k, parity_checks;

julia> import Hecke: gens, quo, group_algebra, GF, one;

julia> import Oscar: free_group, small_group_identification, describe, order, dihedral_group;

julia> m = 6;

julia> G = dihedral_group(2*m);

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

julia> s, r = gens(G); # first, we show that this set of generators indeed satisfy the standard group presentation: https://en.wikipedia.org/wiki/Dihedral_group#Other_definitions   

julia> r^m == s^2 == (r*s)^2 # presentation is satisfied
true

julia> s, r = gens(GA);

julia> a_elts = [one(G), r^4];

julia> b_elts = [one(G), s*r^4, r^3, r^4, s*r^2, r];

julia> a = sum(GA(z) for z in a_elts);

julia> b = sum(GA(z) for z in b_elts);

julia> c = two_block_group_algebra_codes(a,b);

julia> check_allrowscommute(parity_checks(c)) # inconsistency
false

julia> stab_looks_good(parity_checks(c), remove_redundant_rows = true)  # inconsistency
false

julia> order(G) # correct
12

julia> describe(G) # correct
"D12"

julia> code_n(c), code_k(c)
(24, 8) # matches with the paper

Now, let's do the above same example using Oscar.free_group, to reproduce the same error:

julia> using QuantumClifford: check_allrowscommute, stab_looks_good; using QuantumClifford.ECC: two_block_group_algebra_codes, code_n, code_k, parity_checks;

julia> import Hecke: gens, quo, group_algebra, GF, one;

julia> import Oscar: free_group, small_group_identification, describe, order, dihedral_group;

julia> m = 6;

julia> F = free_group(["s", "r"]);

julia> s, r = gens(F);

julia> G, = quo(F, [r^m, s^2, (r*s)^2]);

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

julia> s, r = gens(G);

julia> a_elts = [one(G), r^4];

julia> b_elts = [one(G), s*r^4, r^3, r^4, s*r^2, r];

julia> a = sum(GA(z) for z in a_elts);

julia> b = sum(GA(z) for z in b_elts);

julia> c = two_block_group_algebra_codes(a,b);

julia> check_allrowscommute(parity_checks(c)) # inconsistency
false

julia> stab_looks_good(parity_checks(c), remove_redundant_rows = true)  # inconsistency
false

julia> order(G) # correct
12

julia> describe(G) # correct
"D12"

julia> code_n(c), code_k(c) # matches with the paper
(24, 8)

Additional context

The Alternating group 2BGA given in ECC Zoo example fails the stab_looks_good and check_allrowscommute test as well: https://errorcorrectionzoo.org/c/2bga

When the group is abelian, no errors occur.

I would like to express my sincere gratitude to Tommy for his invaluable guidance.

[Fe-r-oz]

The third method using Oscar.semidirect_product to demonstrate the inconsistency in 2BGA code:

julia> using QuantumClifford: check_allrowscommute, stab_looks_good; using QuantumClifford.ECC: two_block_group_algebra_codes, code_n, code_k, parity_checks;

julia> import Hecke: gens, quo, group_algebra, GF, one;

julia> using Oscar: small_group_identification, describe, order, semidirect_product, automorphism_group, hom, gen, cyclic_group;

julia> m = 6;

julia> Cₘ = cyclic_group(m);

julia> C₂ = cyclic_group(2);

julia> A = automorphism_group(Cₘ); # Given dihedral group presentation, choose r -> r⁻¹

julia> au = A(hom(Cₘ,Cₘ,[Cₘ[1]],[Cₘ[1]^-1]));

julia> f = hom(C₂,A,[C₂[1]],[au]);

julia> G = semidirect_product(Cₘ,f,C₂);

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

julia> s, r = gens(GA); # first, we show that this set of generators indeed satisfy the standard group presentation: https://en.wikipedia.org/wiki/Dihedral_group#Other_definitions

julia> r^m == s^2 == (s*r)^2 # presentation is satisfied
true

julia> a_elts = [one(r), r^4];

julia> b_elts = [one(r), s*r^4, r^3, r^4, s*r^2, r];

julia> a = sum(GA(x) for x in a_elts);

julia> b = sum(GA(x) for x in b_elts);

julia> c = two_block_group_algebra_codes(a,b);

julia> check_allrowscommute(parity_checks(c)) # inconsistency
false

julia> stab_looks_good(parity_checks(c), remove_redundant_rows = true)  # inconsistency
false

julia> order(G) # correct
12

julia> describe(G) # correct
"D12"

julia> code_n(c), code_k(c) # matches with the paper
(24, 8)