Existence and Characterisation of Bivariate Bicycle Codes

This paper characterizes the existence and dimension of bivariate bicycle quantum error correction codes by leveraging their ring structure, ultimately proving that while they are asymptotically bad and thus unsuitable for achieving optimal low-density parity check parameters, they remain valuable for experimental demonstrations of quantum error correction that surpass surface codes.

The Gist

Imagine you are trying to send a delicate message across a stormy ocean. In the world of quantum computing, that message is "quantum information," and the storm is "noise" that can easily scramble or destroy the data. To survive the storm, we wrap our message in a special shield called a Quantum Error Correction (QEC) code.

Think of these codes like a safety net. If a few threads break (errors), the net holds the message together. The better the net, the more broken threads it can handle before the message is lost.

This paper by Postema and Kokkelmans is about a specific, new type of safety net called Bivariate Bicycle (BB) codes. Here is the story of what they found, explained simply:

1. The Goal: A Better, Smaller Net

For a long time, the best safety nets we had were like giant, flat blankets (called surface codes). They work well, but they are huge and heavy. They require a massive amount of "fabric" (physical qubits) to protect just a little bit of information.

Scientists wanted a net that was compact—one that could protect the same amount of information using far fewer physical parts. They found a promising new design called BB codes. These codes are like a cleverly woven bicycle wheel: they are sturdy, have a specific repeating pattern, and are much lighter than the old blankets.

2. The Big Question: How Good Are They?

The authors asked: Exactly how good are these bicycle nets?

• Can they protect a lot of information?
• How many broken threads can they fix?
• Do they get better as we make them bigger?

To answer this, they didn't just guess; they used a mathematical "map" (algebra and rings) to predict the size and strength of these nets before building them.

3. The Discovery: The "Magic Numbers" Rule

The researchers discovered a strict rule for when these bicycle nets actually work. You can't just pick any size for the wheel.

They found that for a BB code to exist and actually protect data, the size of the wheel must be divisible by very specific "magic numbers" (mathematically known as Mersenne primes or specific "outlier" primes like 73 or 121,369).

• Analogy: Imagine trying to build a bicycle wheel. If you pick a random number of spokes, the wheel might wobble and fall apart (a "trivial" code that does nothing). But if you pick a number of spokes that is a multiple of a specific "magic number," the wheel locks into place and becomes a functional shield.

They also proved that these codes can never have a "dimension" (amount of protected data) of just 2; they must be at least 4 to work.

4. The Catch: The "Asymptotic Badness" Limit

Here is the most important finding of the paper. The authors asked: If we keep making these bicycle nets bigger and bigger, will they eventually become perfect?

The answer is no.

They proved that as you make these codes infinitely large, their efficiency drops. They call this "asymptotic badness."

• Analogy: Imagine a bicycle that works great for a short ride. But as you try to make it a trans-continental vehicle, it starts to wobble, and the wheels get so heavy that it's no longer efficient.
• What this means: While these codes are amazing for small-to-medium sizes, they will never be the "perfect, infinite" solution that some other theoretical codes promise. Their structure (being "abelian," or having a simple, repeating symmetry) is the very thing that limits their ultimate potential.

5. The Trade-off: Size vs. Connectivity

Even though they aren't perfect for infinite sizes, the paper shows that for the computers we can build today (which are relatively small), these codes are fantastic.

• The Surface Code (Old Way): Like a flat grid. It's easy to build because every part only needs to talk to its immediate neighbors. But it requires a huge number of parts.
• The BB Code (New Way): Like a bicycle wheel with spokes. It requires fewer parts to do the same job, BUT the parts have to talk to each other across longer distances (non-local connectivity).

The Verdict:
If you have a small quantum computer (under 1,000 qubits), BB codes are a winner. They can protect your data using 2 to 3 times fewer physical qubits than the old surface codes. The only catch is that your hardware needs to be able to connect parts that aren't right next to each other.

Summary

This paper is a "blueprint" for a new type of quantum safety net.

1. It works: They figured out exactly which sizes work and which don't.
2. It's efficient: For current technology, these nets are much smaller and lighter than the old ones.
3. It has a limit: They proved mathematically that these nets will never be perfect for infinite sizes, but that doesn't matter for the machines we are building right now.

The authors conclude that while these codes aren't the "holy grail" for the distant future, they are the perfect tool for the near future, allowing us to build better, more compact quantum memories today.

Technical Summary

1. Problem Statement

Quantum Error Correction (QEC) is essential for fault-tolerant quantum computing. While topological codes (like surface codes) are experimentally mature, they suffer from high overhead (low rate $k/n$) and limited distance scaling ($d \sim \sqrt{n}$). Low-Density Parity Check (LDPC) codes offer a promising alternative with better asymptotic parameters, but finding codes that are both asymptotically good and practically implementable on near-term hardware remains a challenge.

Bivariate Bicycle (BB) codes have emerged as a candidate for compact quantum memory. They are a subclass of two-block group algebra (2BGA) codes defined over a commutative group algebra. However, prior to this work:

• The exact trade-off between code parameters $[[n, k, d]]$ was unknown.
• There was no efficient method to determine the existence of non-trivial codes without computationally expensive brute-force searches.
• It was unclear whether BB codes could achieve asymptotic goodness (non-vanishing rate and relative distance).

2. Methodology

The authors leverage the algebraic structure of BB codes, treating them as ideals within a polynomial quotient ring $S = \mathbb{F}_2[x, y] / \langle x^\ell - 1, y^m - 1 \rangle$.

• Algebraic Characterization:
  • Coprime Case ($\gcd(\ell, m)=1$): The authors prove that when $\ell$ and $m$ are coprime and odd, the bivariate ring is isomorphic to a univariate polynomial ring $\mathbb{F}_2[z] / \langle z^{\ell m} - 1 \rangle$. This allows the code dimension $k$ to be calculated via the greatest common divisor (GCD) of the generator polynomials.
  • Quasi-Cyclic Case ($\gcd(\ell, m) \neq 1$): For general integers, the authors utilize the Chinese Remainder Theorem (CRT) to decompose the ring and employ Gröbner bases to calculate the code dimension. This provides an explicit algorithm to determine $k$ without brute force.
• Existence Conditions: The paper investigates the factorization of cyclotomic polynomials over $\mathbb{F}_2$. It establishes that non-trivial BB codes (where $k \geq 2$) can only exist if the code length $2\ell m$ is divisible by specific types of primes: Mersenne primes ($2^s - 1$) or specific outlier primes (e.g., 73, 121369).
• Connectivity Analysis: The authors derive conditions for the Tanner graph to be fully connected (irreducible), ensuring the code does not decompose into smaller, weaker sub-codes. This is linked to the incommensurability of the generator polynomials.
• Asymptotic Analysis: The authors apply generalized Bravyi-Terhal bounds for abelian 2BGA codes to determine the asymptotic behavior of the code distance.

3. Key Contributions

A. Theoretical Characterization

• Dimension Formulas: Derived exact formulas for the code dimension $k$ for both coprime and quasi-cyclic BB codes using ring theory and Gröbner bases (Theorems 2.3, 2.6, 2.12).
• Existence Theorem (Theorem 3.5): Proved that non-trivial BB codes under the trinomial ansatz exist if and only if the code length is divisible by a Mersenne prime or an outlier prime. This eliminates the need for blind brute-force searches.
• Connectivity Criteria: Established necessary and sufficient conditions for the Tanner graph to be fully connected (Corollaries 3.9 and 3.10), linking graph connectivity to the GCD of polynomial exponents.

B. Asymptotic Badness

• Theorem 2.19: The authors prove that any sequence of constant-weight BB codes is asymptotically bad. As the number of physical qubits $n \to \infty$, the relative minimum distance $d/n$ vanishes.
• Reasoning: This limitation arises from the abelian nature of the underlying group algebra. The authors show that BB codes are equivalent to local CSS codes in $D=4$ dimensions, leading to a distance bound $d \leq O(n^{1-1/D}) = O(n^{3/4})$, which implies $d/n \to 0$.

C. New Code Constructions

• Using the derived existence conditions, the authors constructed a series of new BB codes, including those with previously unexplored divisors (e.g., 31, 73).
• They identified the smallest error-detecting and error-correcting BB codes (e.g., a $[[18, 4, 2]]$ code and a $[[18, 8, 2]]$ code).
• Table 1 & 2: Provided lists of new coprime and quasi-cyclic codes with improved parameters compared to previous brute-force findings.

4. Results

• Performance vs. Surface Codes:
  • When benchmarked against rotated surface codes of comparable logical qubit count ($k$) and distance ($d$), BB codes require significantly fewer physical qubits ($n$).
  • Trade-off: The reduction in qubit overhead comes at the cost of non-local connectivity. While surface codes are planar (degree 4), BB codes require degree 6 connectivity (or can be decomposed into two planar layers with non-local links).
  • Example: A $[[270, 4, 16]]$ BB code requires ~3.3x fewer qubits than 4 patches of a $[[225, 1, 15]]$ surface code to achieve similar error correction capabilities.
• Asymptotic Limits: The paper confirms that while BB codes are not asymptotically good, they are highly effective for moderate-length codes (up to $\sim 1000$ qubits), which are within reach of current and near-future quantum processors.
• Self-Reciprocal Generators: The authors found that for coprime codes with self-reciprocal generators, the only connected solution is $g(z) = 1+z+z^2$, explaining the scarcity of symmetric generators in previous literature.

5. Significance

• Practical Utility: Despite being asymptotically bad, BB codes are highly significant for near-term quantum hardware. They offer a path to demonstrating error correction superior to surface codes on devices with $\sim 1000$ qubits, provided the hardware can support the required non-local connectivity (e.g., via trapped ions, neutral atoms, or fusion-based architectures).
• Efficient Search: The paper replaces inefficient brute-force searches with a rigorous algebraic framework. Researchers can now predict the existence and dimension of BB codes based solely on the prime factorization of the code length.
• Future Directions: The work highlights that the limitation of BB codes is their abelian structure. It suggests that non-abelian 2BGA codes might be the key to achieving asymptotically good parameters while maintaining low-weight parity checks, opening a new avenue for research in quantum LDPC codes.

In summary, this paper provides a complete algebraic characterization of Bivariate Bicycle codes, proving their asymptotic limitations while simultaneously providing the tools to construct optimal, compact codes for near-term quantum error correction experiments.