Enhancements to GF(2) Linear Algebra: in-place row echelon with pivots, nullspace, and basis for row space

[Fe-r-oz]

This PR implements enhancements to the GF(2) Linear Algebra functionality. Inspired by python comprehensive ldpc.mod2 functionality. The following functionality are implemented in simple Julia:

1. gf2_row_echelon_with_pivots!: return row echelon form, transformation matrix, rank and pivots
2. gf2_nullspace: null space
3. gf2_rowspace_basis: basis of the row space

Motivation: Currently, we don't have pure linear algebra implementation of the logical X and logical Z operators for stabilizer CSS code without using MixedDestabilizer. Meaning, we can determine the logicals that satisfy the following conditions:

1. $L_z \in \ker(H_x)$
2. $L_z \notin \text{Im}(H_z^T)$

And

1. $L_x \in \ker(H_z)$
2. $L_x \notin \text{Im}(H_x^T)$

These tools are going to be useful for pure linear algebra implementation of logical operators for CSS stabilizer codes. In general, I think it would nice to have complete set of GF(2) functionality. I have tested for correctness and also add consistency check with ldpc

Edit:

When the nullity is 0, a vector is zeros is convention. In this case, the ldpc.mod2.nullspace returns []. I have followed the convention.

• The code is properly formatted and commented.
• Substantial new functionality is documented within the docs.
• All new functionality is tested.
• All of the automated tests on github pass.
• We recently started enforcing formatting checks. If formatting issues are reported in the new code you have written, please correct them.

[Fe-r-oz]

Please help review this PR, Thank you!

[Krastanov]

These are neat! My main question would be whether these are available already in Nemo and company and if they are faster there. Any insight on that?

[Fe-r-oz]

My main question would be whether these are available already in Nemo and company and if they are faster there.

The row echelon form with pivots is likely not available. They have echelon_form for full gaussian elimination. Nemo methods deal has with ZZ, QQ, GF fields, while we only requireGF(2)mostly as end product.

I think we can add another consistency check: echelon_form(mat) == matrix(GF(2), gf2_row_echelon_with_pivots!(mat_int, full=true)[1]) The echelon form has mat that is GF(2)/FqFieldElemMatrix.

julia> using QuantumClifford

julia> using Nemo: echelon_form, matrix, GF

julia> mat = rand(Bool, 100, 100);

julia> mat_int = Matrix{Int}(mat);

julia> nemo_mat = matrix(GF(2), mat);

julia> using BenchmarkTools

julia> @btime echelon_form($nemo_mat)
  249.621 μs (25 allocations: 169.45 KiB)

julia> @btime gf2_row_echelon_with_pivots!($mat_int, full=true)
  22.280 μs (7 allocations: 80.14 KiB)

julia> echelon_form(nemo_mat) == matrix(GF(2), gf2_row_echelon_with_pivots!(mat_int, full=true)[1]) # consistency check, maybe we can add this to the test suite
true 

[Krastanov]

Yup, this looks great, especially being faster than Nemo (that is surprising). Could you make the following changes:

• do not export these -- generally I avoid exporting new functionality that is not used anywhere else yet, as it might require changes when we start using it
• add it to the changelog, but mention it is unexported and experimental
• put the new tests in a separate file -- I try to have the test files become smaller, so it is easier to interactive work with each one of them

This should be straightforward to merge afterwards. Thanks for the contribution!

[Krastanov]

The JET failure is unrelated and fixed on master

[codecov]

Codecov Report

Attention: Patch coverage is 97.36842% with 1 line in your changes missing coverage. Please review.

Project coverage is 82.77%. Comparing base (c6bc6ee) to head (3be3b4e).

Files with missing lines	Patch %	Lines
src/QuantumClifford.jl	97.36%	1 Missing ⚠️

Additional details and impacted files

@@            Coverage Diff             @@
##           master     #445      +/-   ##
==========================================
+ Coverage   82.63%   82.77%   +0.14%     
==========================================
  Files          70       70              
  Lines        4613     4651      +38     
==========================================
+ Hits         3812     3850      +38     
  Misses        801      801              

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

[Fe-r-oz]

Thank you for you suggestions! I have incorporated all of your suggestions.

Edit:

I had added the changelog to 0.9.15, corrected it to0.9.16 - dev

[Krastanov]

thank you!