compute upper bounds of quantum code distance

[Fe-r-oz]

Problem Description

The library supports computing exact minimum distance of CSS quantum codes via linear programming method. Algorithms such as random information set can be used to compute the upper bound of quantum code distance.

Motivation

The motivation for the upper bound algorithms is inspired from Distance bounds for generalized bicycle codes. Exact minimum distance algorithms (e.g., GAP's QDistRnd or ILP methods) compute the actual distance/lower bound for specific codes. Upper bounds, however, expose limitations (universal constraints) that apply to all codes within a class, helping us understand what is theoretically achievable. For example, in the case of GB codes, we are given a constraint:

An incommensurate GB code with row weight $w$ and parameters $[[n = 2ℓ, k, d]]_{q}$ is equivalent to a CSS code local in $D≤w−1$ dimensions ($D≤w−2$ if $ℓ$ is prime). Its parameters satisfy the inequalities $d≤O(n^{1−1/D})$ and $kd^{2/(D−1)}≤O(n)$. (Statement 13)

This locality imposes an unavoidable scaling law: the distance $d$ satisfies $d ≤ O(n^{1-1/D}$). No clever design can bypass this, as even with optimal polynomial choices $(a(x),b(x))$, the dimensional constraint $D$ sets a ceiling.

In addition, upper bounds are essential for assessing whether known code constructions are optimal. For example, in the case of GB codes, it follows:

For such GB codes., we constructed upper distance bounds and lower existence bounds which give $d ≥ O(n^{(1/2}))$. For weight-4 codes ($w=4, D=2$), these upper and lower bounds coincide to prove the optimality of $√n$ scaling. (Statement 14)

For weight $4$ codes ($w=4$, implying $D=2$), upper bound is $d ≤ O(√n)$. Without the upper bound, one might futilely search for weight-4 GB codes with better than √n scaling. In this case, the exact algorithm confirms distances for specific codes, but the upper bound proves $√n$ is the best possible for the entire subclass.

The numerical results also show that upper bounds inform the trade-offs involved in code design.

upper bound for GB codes suggests a power-law distance scaling with the exponent that may change with $w$, $d < O(n^γ)$, where $γ = 1−1/D$ with the effective dimension $D(w) ≤ w − 2$ for a prime $ℓ$.

The figure 4 on page 8 show that increasing $w$ (e.g., from $4$ to $6$ to $8$) yields codes with larger distances for the same $n$. However, the upper bound $d ≤ O(n^{1-1/D}$) with $D ≤ w-1$ quantifies the potential advantage: higher $w$ allows higher $D$, leading to a slower decay of the exponent ($1-1/D$). Thus, the upper bound reveals how much code distance improvement can be theoretically expected by increasing stabilizer row weight $w$.

Solution Description

Investigate wrapping Leonid P. Pryadko's C library dist-m4ri for supporting dedicated algorithms for computing upper/lower distance bounds. Native Julia implementation can also be considered.

Implementation Notes from Stefan Krastanov

Usually for C code in Julia one would use BinaryBuilder to build a "shared library" or "executable". The preferred option is usually "shared library", but it seems like this particular codebase is not really designed to be used as a library. I guess then the build target would be an executable and one would need to prepare temporary files and give them to the executable as input.

Check BinaryBuilder, Base.run, and whatever tools julia provides for creating temporary files.

Additional Context

The upper bounds of various GB codes are presented here.

[Krastanov]

It would also help explaining why would anyone want to bother with an upper bound algorithm if there is already an exact one implemented.

[Fe-r-oz]

That’s a fair point -- I’ve now added a motivation section to clarify why the upper bound algorithm is useful alongside the exact one. Happy to revise if you think it needs more detail.

[Fe-r-oz]

The dist-m4ri also contains a lower bound/exact minimum distance algorithm which I hope would work for $200$ to $500$ physical qubits faster than the ILP method (although the benchmarks will be the final proof of that). E.g. dist-m4ri has been used to calculate a distance of code with $486$ physical qubits! Currently, the ILP method we support works for small instances sizes as the paper remarks

we can solve the associated IP for reasonably small instance sizes (page 9)

With these motivations, I submitted the PR for dist_mri yesterday to Yggdrasil but looking at the make file, it made me realize that m4ri is needed as dependency. The make file is in the src folder in dist-m4ri. This is the latest progress update; I will work on the m4ri_jll recipe by looking at the recent merged jll recipes and documentation and post it here for feedback, Thank you!

Draft Recipe (Thank you to Mose for refining it):

using BinaryBuilder, Pkg

name = "dist_m4ri"
version = v"0.0.1"

sources = [
    GitSource("https://github.com/QEC-pages/dist-m4ri.git",
              "0c540cb766f5538d9a89152dc875ae5a357ee6c6")
]

dependencies = [
    Dependency("M4RI_jll"), # After a PR about [M4RI_JLL is merged]
]

script = raw"""
cd $WORKSPACE/srcdir/dist-m4ri/src/ # the make file is in the src folder so added /src/ here
make -j${nproc} CC=$CC CXX=$CXX
install -Dvm 755 "dist-m4ri${exeext}"  -t "${bindir}"
"""

platforms = filter(p -> Sys.islinux(p) || Sys.isapple(p) || Sys.isfreebsd(p) || Sys.iswindows(p), supported_platforms())

products = [
    ExecutableProduct("dist_m4ri", :dist_m4ri)
]

build_tarballs(ARGS, name, version, sources, script, platforms, products, dependencies; julia_compat="1.6")

Edit: removed this extra dependencies = Dependency[] from recipe

[Fe-r-oz]

More use cases of upper-bound algorithms:

Reference

For d > 20, the integer-programming method fails to terminate in a reasonable time. Accordingly, we use the probabilistic algorithm of Ref. [93], using between 5,000 and 10,000 information sets to estimate an upper bound on d. Each computation is repeated several hundred times to ensure consistency, yielding a bound that we consider tight ~ From Table II of reference