Extending the capabilities of 2BGA codes via Oscar's Group Algebra

[Fe-r-oz]

Extending the capabilities of 2BGA codes via Oscar's Group Algebra

Introduction

With regards to 2BGA code, The PR #356 introduced a basic functionality for 2BGA codes where GroupAlgebra is only a single cyclic group of order l. So, we are only limited to this group algebra: GA = group_algebra(GF(2), abelian_group(l)). However, the 2BGA codes were discovered by Lin and Pryadko in their seminal paper Quantum two-block group algebra codes where they introduced these codes with rich a Group Algebra, incorporating both abelian and non-abelian groups and products (direct/semidirect) of groups.

For researchers deeply involved in researching 2BGA codes, functionalities such as designing very specific group presentations, non-abelian groups, direct products of groups are currently not supported. This is well highlighted in this aforementioned paper, where specific presentations are the key ingredient for construction of Group Algebra of 2BGA with abelian and non-abelian groups.

The goal is to extend the capabilities of 2BGA codes in three verticals:

graph TD
    A[Extend 2BGA Capabilities] --> B[Table 1: Specific Group Presentations ⟨S∣R⟩]
    A --> C[Table 2: Direct Product of Cyclic Groups Cₗ x Cₘ]
    A --> D[Table 3: Group Presentation for Dihedral Groups Dₘ]

Loading

The diagram below distinguishes between Hecke.small_group and finitely presented groups (Oscar.free_group) based on the presence of extra relations in group presentations. The aforementioned paper utilizes specific presentations that necessitate the use of Oscar.free_group.

graph TD
    A[Group Presentation  ⟨S∣R⟩] --> B{Specific Presentation?}
    
    B -- No --> C[Small Groups <br> Hecke.small_group]
    C --> D[Independent generators]
    C --> E[" Example <br> ⟨r, s∣ s^4, r^9⟩"]

    B -- Yes --> F[Finitely Presented Groups <br> Oscar.free_group]
    F --> G[Defined by interactions]
    F --> H["Example <br>⟨r, s∣s^4, r^9, s⁻¹rsr⟩"]

Loading

The diagram below distinguishes between Hecke.direct_product and Oscar.direct_product. The aforementioned paper utilizes direct product between two or more general groups that necessitate the use of Oscar.direct_product. The order of group supported by Oscar is substantially larger. With twobga_from_direct_product , we offer comprehensive documentation and implementation for accurately computing the direct product of two or more general groups, ensuring that the presentation $⟨X∣S⟩$ is satisfied and that the two subgroups indeed form a valid group.

graph TB
    root[Direct Product of Groups]
   
    root --> A[Hecke.direct_product]
    root --> B[Oscar.direct_product]
   
    %% Hecke Branch
    A --> A1[Supports mostly abelian groups and list of finite groups]
    A1--> A2[abelian_group symmetric_group small_group]
    A2 --> A3[C × C, C × S]

    %% Oscar Branch
    B --> B1[Supports finite general groups, including non-abelian groups]
    B1--> B2[alternating_group <br> dihedral_group <br> free_group <br> cyclic_group <br> permutation_group <br>  quaternion_group <br> symmetric_group <br> abelian_group<br> small_group]
    B2--> B3[A × C,  A × D <br> D × C, D × D <br> F × F, F × A, F × D <br> F × S, F × C <br> C × C, C × S]

Loading

Additionally, with regards to HeckeExt, Bivariate Bicycle (BB) codes using Hecke's Group Algebra are currently unsupported. Two group algebraic implementations are planned: one with 2BGA as the parent and the other with LPCode as the parent, both extending the capabilities of HeckeExt.

1. BB codes are Abelian LP codes over groups of the form ℤₗ × ℤₘ.
2. BB codes are also a class of Abelian 2BGA codes, formed by the direct product of two cyclic groups ℤₗ × ℤₘ.

Objectives

1. Direct Product of Groups $C_l \times C_m$
2. Specific Group Presentations $\langle S \mid R \rangle$
3. Non-abelian groups such as Dihedral Group,Symmetric Group, Alternating Groups
4. Group presentation of non-abelian Dihedral group, $D_m$
5. Small Groups with Multiplication Table via Free Groups
6. Semidirect Product of two Cyclic groups $C_l \ltimes C_m$
7. Additional: Implement Bivariate Bicycle codes using 2BGA as the parent and LPCode as the parent

For correctness, the goal is to reproduce the results (Table 1, Table 2 , Table 3) from the paper and provide researchers in QEC codes access to this crucial functionality. Some of the necessary functionalities are only available in Oscar such as Free Group that enables group presentations for constructing codes for Clifford simulation. These functionalities would facilitate further exploration of these codes by researchers, as the paper by Lin and Pryadko was the first to utilize small groups and group presentations for constructing a rich group algebra.

Additionally, with regards to HeckeExt, the equivalence between the two group algebraic implementations of BB codes will be tested: parity_checks(BB using 2BGA as the parent) == parity_checks(BB using LPCode as the parent). This equivalence relation can be seen from the following:

graph TD
    subgraph A[LP]
        B[2BGA]
        subgraph B[2BGA]
            C[BB]
        end
    end

Loading

Implementation

• 1) Direct Product of Groups Cₗ x Cₘ: add tests and examples of Cₘ × C₂ 2BGA codes #392
• 2), 3), 5) Non-abelian groups via Small Groups: tests: Specific Group Presentations Using Oscar's Free Group for Non-Abelian and Abelian Groups #390
• Discrepancy in 2BGA code_k values when reproducing some results from paper by Lin et al via Hecke/Oscar.small_group #391. Many Thanks to Tommy Hofmann for his wonderful insights in resolving this issue.
• Direct Product of non-abelian group with Cyclic group, Dₗ x Cₘ tests: Non-Abelian Dihedral Groups Dₘ via Group Presentation ⟨S|R⟩ #397
• Reproduce Table 3 using Dₗ x Cₘ tests: Non-Abelian Dihedral Groups Dₘ via Group Presentation ⟨S|R⟩ #397
• Group Presentation for Cyclic Group ⟨x,s|xᵐ=s²=xsx⁻¹s⁻¹=1⟩ tests: Group Presentation for Cyclic Group Cₘₕ = Cₘ × C₂ #398
• twobga_from_fp_group API, documentation, and testing via test_ecc_base.jl: add QuantumCliffordOscarExt to provide convenient API for finitely presented groups via specific group presentation #400
• Semidirect Product of two Cyclic groups tests: Semidirect Product Dₘ = Cₘ⋉C₂ of two Cyclic Groups to form Dihedral Group #402
• check_repr_commutation_relation to verify L(a) R(b) == R(b) L(a) for 2BGA code: add check_repr_commutation_relation to test the CSS orthogonality condition for 2BGA's Group Algebra with a General Group G #403
• check_repr_regular_linear add check_repr_regular_linear to verify F-linear regular representation for Group Algebra elements #407
• Hecke's Small Groups (small_group(l, Id)) without any extra relations for single cyclic groups  #406
• Implementing Bivariate Bicycle Codes using 2BGA as the parent via Hecke's Group Algebra #399
• tests: test consistency of Bivariate Bicycle code using LPCode constructor #372

I have mentioned each feature in more detail in respective PRs.

Outcome

• Reproduce results from Table 1 of Lin et al.
• """"""""""""""""""""""""""" Table 2 of Lin et al.
• """"""""""""""""""""""""""" Table 3 of Lin et al.
• API, docs, and tests via test_ecc_base.jl:QuantumCliffordOscarExt
• """"""""""""""""""""""""""" Table 3 of Bravyi et al.
• """"""""""""""""""""""""""" Table 1 of Berthusen et al.
• """"""""""""""""""""""""""" Table 1 of Wang et al.

Table 2 has been reproduced using two approaches: direct products of cyclic groups and group presentation, as a cross-check for consistency. Similarly, Table 3 has been cross-checked using semidirect products of cyclic groups and group presentation.

Reviewer: Stefan Krastanov

Additional Details

Note: Given the fact that there were quite a few PRs related to this new functionality, the overall goals and objectives may not be immediately clear. Therefore, I've outlined them concisely to ensure progress is tracked and to communicate the purpose of these PRs.

The paper by Lin and Pryadko is the base paper that discovered these codes.

Oscar v1.2.0 has not been released yet. It will fix the CI error that 'GAP.jl currently does not support multithreaded garbage collection' as it will update it to GAP.jl 0.11.2 from GAP v0.10.4

I think the functionalities here apply to many types of codes that use Group Algebra, not just 2BGA. This will have to be added in documentation, that these functionalities are not restricted to just this code.

[Fe-r-oz]

Hi, @Krastanov,

I wanted to check with you about a potential Bug Bounty for some recent work. I've been collaborating with @thofma to fully reproduce the results from the Lin and Pryadko paper, extending Group Algebra-based functionality, and building significant new features on top of #356. Tommy’s contributions were invaluable, particularly with the group presentation, and he helped resolve issue #391. Initially, I pursued this to explore the paper and add new functionality, without the intention of turning it into a Bug Bounty.

However, given the scope and impact of this work, I was wondering whether it might qualify for the Quantum Savory Bug Bounty program. It seems like the type of contribution that could be a good fit, though I understand that you're best placed to assess its relevance and whether it aligns with the program.

Additionally, I believe Tommy could quickly address the downgrade and the specific CI errors we've encountered with Oscar. I wanted to explore whether this could also be structured as a Bug Bounty, with shared credit, though I’ll leave the details to your judgment and am happy to accept whatever you decide.

Thank you for your time and guidance, and I look forward to hearing your thoughts.

Best Regards.

[Krastanov]

Indeed, this is a pretty significant contribution, and a very valuable set of tests verifying the consistency of @royess 's work, thank you for looking into it. It will be appropriate to provide a bounty for its completion. It will take me some time to go over the PRs and review them and to write down the exact parameters of the bounty (we will probably need a convenient API for accessing these codes, having some decoder benchmarks, etc, not just having them as examples in the test runner). I will try to write this up over the next week.

@thofma , thank you for the guidance you have provided to Feroz, it is much appreciated.

[Fe-r-oz]

Indeed. I think that implementing a convenient API, namely twobga_from_fp_group, similar to LPCode(A,B), within a new QuantumCliffordOscarExt would be helpful. The twobga_from_fp_group method would utilize the 2bga method from HeckeExt and further extend its functionalities through group presentations. For example, in the first doctest, the user defines the elements A and B using group_algebra, GA, which are then passed to LPCode(A,B). Similarly, users will be able to define GA based on group presentation for non-abelian/abelian groups, specify the elements a and b, and input them into twobga_from_fp_group.

In addition, QuantumCliffordOscarExt will be helpful in the future, particularly if we need specific methods from Oscar, as we can define those methods within this Ext. It will enable clear differentiation in the functionalities we require from Oscar that are not available in AA, Hecke, or Nemo and should be used exclusively for those purposes.

Please refine and enhance this along with the other requirements during the writing process. Thank you.