[PRE REVIEW]: QDistRnd: A GAP package for computing the distance of quantum error-correcting codes

[whedon]

Submitting author: @LeonidPryadko (Leonid P. Pryadko) Repository: https://github.com/QEC-pages/QDistRnd/ Version: 0.7.0 Editor: @danielskatz Reviewers: @oscarhiggott, @pan-pavel Managing EiC: Kristen Thyng

:warning: JOSS reduced service mode :warning:

Due to the challenges of the COVID-19 pandemic, JOSS is currently operating in a "reduced service mode". You can read more about what that means in our blog post.

Status

Status badge code:

HTML: <a href="https://joss.theoj.org/papers/3f7bbe8765963b577608064456e69405"><img src="https://joss.theoj.org/papers/3f7bbe8765963b577608064456e69405/status.svg"></a>
Markdown: [![status](https://joss.theoj.org/papers/3f7bbe8765963b577608064456e69405/status.svg)](https://joss.theoj.org/papers/3f7bbe8765963b577608064456e69405)

Author instructions

Thanks for submitting your paper to JOSS @LeonidPryadko. Currently, there isn't an JOSS editor assigned to your paper.

@LeonidPryadko if you have any suggestions for potential reviewers then please mention them here in this thread (without tagging them with an @). In addition, this list of people have already agreed to review for JOSS and may be suitable for this submission (please start at the bottom of the list).

Editor instructions

The JOSS submission bot @whedon is here to help you find and assign reviewers and start the main review. To find out what @whedon can do for you type:

@whedon commands

[whedon]

Hello human, I'm @whedon, a robot that can help you with some common editorial tasks.

:warning: JOSS reduced service mode :warning:

Due to the challenges of the COVID-19 pandemic, JOSS is currently operating in a "reduced service mode". You can read more about what that means in our blog post.

For a list of things I can do to help you, just type:

@whedon commands

For example, to regenerate the paper pdf after making changes in the paper's md or bib files, type:

@whedon generate pdf

[whedon]

Wordcount for paper.md is 1143

[whedon]

Software report (experimental):

github.com/AlDanial/cloc v 1.88  T=0.04 s (292.4 files/s, 58743.1 lines/s)
-------------------------------------------------------------------------------
Language                     files          blank        comment           code
-------------------------------------------------------------------------------
ANTLR Grammar                    7            142              0           1209
TeX                              2             43              0            992
Markdown                         2             16              0            138
YAML                             2              6              9             57
-------------------------------------------------------------------------------
SUM:                            13            207              9           2396
-------------------------------------------------------------------------------

Statistical information for the repository 'aa02e5e1dd6017af96035fb3' was
gathered on 2021/12/01.
No commited files with the specified extensions were found.

[whedon]

Failed to discover a valid open source license.

[whedon]

Reference check summary (note 'MISSING' DOIs are suggestions that need verification):

OK DOIs

- 10.1109/ISIT.2009.5205648 is OK
- 10.1103/PhysRevLett.122.230501 is OK
- 10.1103/PhysRevA.102.062402 is OK
- 10.1103/PhysRevA.88.012311 is OK
- 10.22331/q-2021-11-22-585 is OK
- 10.1109/TIT.2015.2422294 is OK
- 10.1006/jsco.1996.0125 is OK
- 10.1103/PhysRevA.87.020304 is OK
- 10.18154/RWTH-2018-01100 is OK
- 10.1109/ICC.2004.1312605 is OK
- 10.1109/ISIT.2008.4595332 is OK
- 10.1109/TIT.2017.2690381 is OK
- 10.1109/18.21270 is OK
- 10.1109/18.57202 is OK

MISSING DOIs

- 10.1016/j.swevo.2020.100797 may be a valid DOI for title: Genetic algorithms with permutation-based representation for computing the distance of linear codes
- 10.1109/tit.2021.3119384 may be a valid DOI for title: Quantum LDPC Codes with Almost Linear Minimum Distance

INVALID DOIs

- http://dx.doi.org/10.1063/1.4891487 is INVALID because of 'https://doi.org/' prefix

[whedon]

:point_right::page_facing_up: Download article proof :page_facing_up: View article proof on GitHub :page_facing_up: :point_left:

[kthyng]

Hi @drvinceknight! I know I just asked you to edit another submission but perhaps you have bandwidth for two. Do you know about GAP?

[kthyng]

@whedon invite @drvinceknight as editor

[whedon]

@drvinceknight has been invited to edit this submission.

[kthyng]

@LeonidPryadko Can you add a license to your repo?

[LeonidPryadko]

How do I add a license? I already have a license listed in documentation (the manual), it says: Copyright

© 2021 by Leonid P. Pryadko and Vadim A. Shabashov

QDistRnd package is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License http://www.fsf.org/licenses/gpl.html as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

Thanks,

Leonid

On Wed, Dec 1, 2021 at 3:19 PM Kristen Thyng @.***> wrote:

@LeonidPryadko https://github.com/LeonidPryadko Can you add a license to your repo?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/openjournals/joss-reviews/issues/3970#issuecomment-984146908, or unsubscribe https://github.com/notifications/unsubscribe-auth/APF4LTWP7L7UBEDBWWHYCWLUO2UONANCNFSM5JFVKULQ . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.

[kthyng]

You can get more info here. In short you need to have a file called LICENSE that meets our guidelines.

[LeonidPryadko]

I just added GPL 2.0 (in the documentation, it says GPL 2.0 or any later version).

Will it do? Thanks,

Leonid

P.S. I also corrected a doi in one of the references.

On Wed, Dec 1, 2021 at 3:28 PM Kristen Thyng @.***> wrote:

You can get more info here https://joss.readthedocs.io/en/latest/submitting.html#typical-paper-submission-flow. In short you need to have a file called LICENSE that meets our guidelines.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/openjournals/joss-reviews/issues/3970#issuecomment-984151910, or unsubscribe https://github.com/notifications/unsubscribe-auth/APF4LTSVD6QJRRD3E4KJMVDUO2VSPANCNFSM5JFVKULQ . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.

[kthyng]

@whedon check repository

[whedon]

Wordcount for paper.md is 1143

[whedon]

Software report (experimental):

github.com/AlDanial/cloc v 1.88  T=0.03 s (441.6 files/s, 88737.4 lines/s)
-------------------------------------------------------------------------------
Language                     files          blank        comment           code
-------------------------------------------------------------------------------
ANTLR Grammar                    7            142              0           1209
TeX                              2             43              0            992
Markdown                         2             16              0            138
YAML                             2              6              9             57
-------------------------------------------------------------------------------
SUM:                            13            207              9           2396
-------------------------------------------------------------------------------

Statistical information for the repository '4ed730a6ad2b1eb141ed2d6c' was
gathered on 2021/12/01.
No commited files with the specified extensions were found.

[kthyng]

Hm I thought that command would re-check for the license. Anyway it looks ok.

[danielskatz]

I'll edit this one

[danielskatz]

@whedon assign me as editor

[whedon]

OK, the editor is @danielskatz

[danielskatz]

👋 @LeonidPryadko - Can you suggest any potential reviewers? If so, please mention them here in this thread (without tagging them with an @). This list of people have already agreed to review for JOSS and may be suitable for this submission (please start at the bottom of the list), but suggestions from elsewhere are also welcome.

[danielskatz]

@LeonidPryadko - You also need a create a README in your repo.

[LeonidPryadko]

Dear Daniel:

As for reviewers, I may suggest Cristophe Vuillot < @.> and Nikolas Breuckmann @.> ; these people have used GAP and also know about quantum error correcting codes.

Regarding the README, the distribution already has a short README.md file. Would you like me to rename it to just README, or add details?

Thanks,

Leonid

On Thu, Dec 9, 2021 at 9:33 AM Daniel S. Katz @.***> wrote:

@LeonidPryadko https://github.com/LeonidPryadko - You also need a create a README in your repo.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/openjournals/joss-reviews/issues/3970#issuecomment-990067566, or unsubscribe https://github.com/notifications/unsubscribe-auth/APF4LTWYSYFA3FVCDMSILHDUQDR7TANCNFSM5JFVKULQ . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.

[danielskatz]

@LeonidPryadko - as you can see in https://github.com/openjournals/joss-reviews/issues/3970#issuecomment-990104679, those emails didn't come across in a useful way. Can you type them into this thread, rather than replying by email?

And the README I see is https://github.com/QEC-pages/QDistRnd/blob/main/README.md - this doesn't meet what JOSS requires in https://joss.readthedocs.io/en/latest/review_criteria.html#documentation

[danielskatz]

@LeonidPryadko - I've been on vacation the last two weeks and will still be this week, but we do need to find reviewers, and for you to create a README that meets the JOSS requirements.

[LeonidPryadko]

Here are the email addresses of the suggested reviewers: Cristophe Vuillot < christophe.vuillot@inria.fr > and Nikolas Breuckmann < nikobreu@gmail.com >

I extended the README.md file for the package distribution at github; hope it contains enough information now. Please let me know if any additional information needed is still missing.

[danielskatz]

Thanks for the README changes - this looks good enough to start the review. I'll now get back to looking for reviewers

[danielskatz]

👋 @nikobreu - would you be willing to review this submission for JOSS? We carry out our checklist-driven reviews here in GitHub issues and follow these guidelines: https://joss.readthedocs.io/en/latest/review_criteria.html

[danielskatz]

@whedon assign @oscarhiggott as reviewer

thanks very much for agreeing to do this, @oscarhiggott - As you can see, I'm assigning you here, but we won't start the review until we get one more reviewer as well.

[whedon]

OK, @oscarhiggott is now a reviewer

[danielskatz]

👋 @dimpase, @fingolfin, @ChrisJefferson, @ruthhoffmann - You were suggested to me as potential reviewers of this JOSS submission by Alexander Konovalov...

Would one of you be willing to review it? We carry out our checklist-driven reviews here in GitHub issues and follow these guidelines: https://joss.readthedocs.io/en/latest/review_criteria.html

[dimpase]

I'd like to suggest to run this by a "real" quantum codes expert, e.g. @fredezerman (he might need a ping by email: https://personal.ntu.edu.sg/fredezerman/Fred_CV.pdf)

I find the package description lacking in the theoretical sense - it seems that the only detailed description of what's done there is in the code itself.

[danielskatz]

Thanks @dimpase - I'll check with @fredezerman.

Re your other comment, can you be more specific about what you mean by "the package description"? Note that JOSS papers are intended to be fairly short, though the repository (README, documentation, etc.) should be at an appropriate level of detail.

[danielskatz]

👋 @fredezerman - As you can see above, you were suggested to me as a potential reviewer of this JOSS submission by @dimpase

Would you be willing to review it? We carry out our checklist-driven reviews here in GitHub issues and follow these guidelines: https://joss.readthedocs.io/en/latest/review_criteria.html

I'll also be sending you an email about this shortly, in case that's a better way to get you

[dimpase]

what you mean by "the package description"

Basically, its manual says

The GAP package QDistRnd gives a reference implementation of a probabilistic algorithm for finding the distance of a q-ary quantum low-density parity-check code linear over a finite field F=GF(q).

It appears that the only description of the algorithm is in the manual/code itself. IMHO it's not what "reference implementation" is meant to be - there seems to be no other published material on it, or other implementations of it.

[danielskatz]

@dimpase - ok, thanks; that helps

[LeonidPryadko]

A few comments in relation to the comments of @dimpase.

1. I should remark that the manual indeed gives a detailed description of the algorithm; we thought it unnecessary to duplicate the information in the README file given that it is rather technical.

2. If deemed necessary, I will be happy to add the following two paragraphs describing the algorithm to the README file:

In the case of a CSS code with two stabilizer generator matrices, $H_x$ and $H_z$ with mutually orthogonal rows, the algorithm amounts to the following steps:

• Construct matrix $G_z$ dual to $H_x$ (mutually orthogonal rows and complementary ranks);
• Permute columns of $G_z$ randomly and perform row operations (Gauss elimination) to get a reduced row echelon form, followed by the inverse column permutation;
• Compare weights of the rows of thus obtained modified $G_z$ which are linearly independent from the rows of $H_z$; the minimum gives an upper bound for the distance $d_z$.
• A minimum weight code word can be found after repeating these steps for a sufficient number of times.

The algorithm works because it draws random code words from a distribution biased to lower weights. It is generic, meaning that it works with any code. It is also a generalization of a well established "information set" class of algorithms for classical linear codes (see references in the program manual), also used in cryptography. In all cases, the complexity is roughly exponential in the code distance. Unfortunately, there is no accurate estimate of the complexity exponent which could be used as a stopping criterion, definitely so in the case of quantum LDPC codes.

3. The algorithm in the package is a bit different but is related to that described in Dumer, Kovalev, and Pryadko "Distance verification for classical and quantum LDPC codes", IEEE Trans. Inf. Th. 63, 4675 (2017), where the exponent of question in the case of a family of random classical LDPC codes was related to the corresponding erasure threshold. Because of this similarity, the relation to the well-established information set algorithms, and also since there is no performance guarantee, we decided that it does not deserve a regular independent publication.

4. Yet, it turned very useful in my own research (both published papers and some work in progress). In addition, for a number of years I've been reviewing manuscripts (mostly submitted to Quantum Information & Computation) describing new constructions of q-ary quantum codes, often with lower distance bounds but no actual numerics to verify the distances. I kept writing in my reports that in this day and age, the distances should be actually computed, but could not suggest a package to do it. For these reasons, I decided to spend the time and get a student to help prepare the GAP package.

5. The GAP package QDistRnd, at least in the present version, is substantially slower than the C program which uses m4ri library for linear algebra. On the other hand, it works with q-ary codes. This is why we say in the manual that it gives a 'reference' implementation, i.e., not heavily optimized for performance.

6. Among coding theory specialists, both quantum and classical, who are familiar with the algorithm (but not the GAP package) are Pavel Panteleev panteleev@intsys.msu.ru and Gleb Kalachev kalachev.gleb@huawei.com. Some time ago I shared with them a C program for calculating the distance of binary CSS codes which uses a version of the same algorithm, and they have tried it. We even had a discussion about the performance of the algorithm and that it would be nice to get an accurate estimate of the exponent for specific classes of quantum codes.

I am not sure, though, whether either of these people have ever used GAP; this is why I did not mention the names previously.

Hope it helps,

Leonid

[danielskatz]

👋 @fingolfin, @ChrisJefferson, @ruthhoffmann - You were suggested to me as potential reviewers of this JOSS submission by Alexander Konovalov...

Would one of you be willing to review it? We carry out our checklist-driven reviews here in GitHub issues and follow these guidelines: https://joss.readthedocs.io/en/latest/review_criteria.html

[ruthhoffmann]

Sorry I will have to bow out of reviewing this. It is a little too far out of my field, and I do not have enough time to dedicate a good review to it. Thanks for considering me though!

[danielskatz]

👋 @fingolfin and @ChrisJefferson - You were suggested to me as potential reviewers of this JOSS submission by Alexander Konovalov...

Would one of you be willing to review it? We carry out our checklist-driven reviews here in GitHub issues and follow these guidelines: https://joss.readthedocs.io/en/latest/review_criteria.html

[danielskatz]

@LeonidPryadko - hi - I've been having great difficulty finding a second reviewer, after lots of emails and a tweet asked for help. Do you have have any more suggestions?

[danielskatz]

I'm happy to say that @pan-pavel has agreed to be our second reviewer, so I will be assigning him next and then starting the review

[danielskatz]

@whedon add @pan-pavel as reviewer

[whedon]

OK, @pan-pavel is now a reviewer

[danielskatz]

@whedon start review

[whedon]

OK, I've started the review over in https://github.com/openjournals/joss-reviews/issues/4120.