Construction of a Family of Quantum Codes Using Sub-exceding Functions via the Hypergraph Product and the Generalized Shor Construction

This paper introduces a scalable family of quantum LDPC codes with parameters $[[6k^2, k^2, d]]$ by combining the hypergraph product and generalized Shor construction on classical codes derived from sub-exceding functions, achieving a minimum distance of $d=3$ for $k=3$ and $d=4$ for $k \ge 4$.

The Gist

Imagine you are trying to send a very fragile message across a stormy ocean. In the world of computers, this "message" is a qubit (a quantum bit), and the "storm" is noise that can easily flip the message from a 0 to a 1, or vice versa, destroying the information.

To protect this message, we need a Quantum Code. Think of a quantum code as a special, super-strong shipping crate. You don't just put your fragile message in one box; you spread it out across many boxes (qubits) in a specific pattern. If one box gets smashed by a wave (an error), the pattern allows you to figure out exactly which box broke and fix it without ever opening the crate to look inside (which would destroy the quantum state).

This paper introduces a new, highly efficient type of shipping crate designed by the authors. Here is how they built it, explained simply:

1. The Building Blocks: "Sub-exceeding Functions"

Before building the quantum crate, the authors started with two types of classical (regular) codes, which they call $L_k$ and $L^+_k$.

• The Analogy: Imagine you are organizing a library. You have a list of books (data). To make sure no book goes missing, you write a "checksum" (a summary note) next to them.
• The Twist: The authors used a specific mathematical rule called a "sub-exceeding function" to write these checksums.
  • What is it? Imagine you have a list of numbers from 1 to $k$. A sub-exceeding function says: "For the number in position 5, your summary note can only be a number between 0 and 4." It's a rule that keeps the summary notes smaller than the position they describe.
• Why it matters: This rule creates a very neat, predictable pattern. In the world of coding, predictability is gold because it makes it easier to spot errors later.

2. The Construction: Mixing Two Recipes

The authors didn't just use one of these classical codes; they combined them using two famous "construction recipes" to make a quantum code.

Recipe A: The Hypergraph Product (The "Grid" Method)

• The Analogy: Imagine you have a sheet of graph paper. You take your first code and lay it out horizontally, and your second code vertically. Where they cross, you create a new, massive grid of connections.
• The Result: This creates a huge, interconnected web where every piece of data is checked by multiple neighbors. If one piece is wrong, its neighbors will scream, "Hey, something is wrong here!"

Recipe B: The Generalized Shor Construction (The "Nested Box" Method)

• The Analogy: This is like putting a smaller, simpler box inside a larger, more complex box. The inner box protects the data, and the outer box protects the inner box.
• The Result: This adds an extra layer of security, ensuring that even if the outer layer is breached, the inner logic still holds.

By mixing these two recipes using their special "sub-exceeding" codes, the authors created a new family of quantum codes called $Q_{L_k}$.

3. The Magic Numbers: What Did They Achieve?

The paper claims their new crate has some very impressive stats:

• The Size: If you want to store $k^2$ pieces of information (logical qubits), you need $6k^2$ physical boxes (physical qubits).
  • Simple Math: For every 1 piece of data, you use 6 boxes. This is a 1/6 efficiency rate. While not perfect, it's a very stable and reliable rate for this type of complex code.
• The Strength (Distance): The "distance" of a code is how many errors it can survive before the message is lost.
  • For small sizes ($k=3$), it can handle 3 errors.
  • For larger sizes ($k \ge 4$), it can handle 4 errors.
  • Why this is cool: Being able to correct 4 errors means the code is very robust against the "stormy ocean" of quantum noise.
• The Structure (LDPC): This is the most important part for the future. The code is LDPC (Low-Density Parity-Check).
  • The Analogy: In a normal, messy code, every box might be connected to 100 other boxes. Checking them all is a nightmare. In this new code, every box is only connected to a few neighbors (specifically, a small, fixed number).
  • The Benefit: This makes the code easy to decode. A computer doesn't have to do a million calculations to find an error; it just looks at its few neighbors. This is crucial for building real quantum computers that need to fix errors fast.

4. How It Works in Practice

The paper also explains how to actually encode (pack) and decode (unpack/check) the data.

• Encoding: You take your data and use a specific set of "CNOT gates" (quantum logic switches) to spread the information out according to the pattern. Because the pattern is so regular (thanks to the sub-exceeding functions), the instructions for the computer are very repetitive and easy to follow.
• Decoding: When an error happens, the system checks the "neighbors." Because of the special structure, the system can spot the error in two simple steps:
  1. Check for "Phase Flips" (errors that change the wave nature of the qubit).
  2. Check for "Bit Flips" (errors that change 0 to 1).
     The regularity of the code means these checks can happen in parallel, like a team of inspectors checking different sections of a building at the same time.

The Big Picture: Why Should We Care?

Quantum computers are incredibly powerful but also incredibly fragile. They are currently stuck in a "noisy" phase where errors happen too fast to be useful.

This paper offers a blueprint for a better shield.

• It uses a clever mathematical trick (sub-exceeding functions) to create a pattern that is both strong (high error correction) and simple (easy to check).
• It proves that you can build these codes with a constant efficiency (you always use 6 boxes for 1 piece of data), regardless of how big the computer gets.
• It opens the door for scalable quantum computers. If we can build these "crates," we can build quantum computers that are big enough to solve real-world problems (like designing new medicines or breaking complex encryption) without falling apart from errors.

In summary: The authors took a neat mathematical puzzle, used it to build two types of safety nets, and then wove them together into a super-strong, easy-to-use shield for the future of quantum computing.

Technical Summary

Here is a detailed technical summary of the paper "Construction of a Family of Quantum Codes Using Sub-exceding Functions via the Hypergraph Product and the Generalized Shor Construction."

1. Problem Statement

Quantum error correction is critical for the reliability of quantum computing systems. While classical binary coding has limitations, the transition to quantum computing requires robust error-correcting codes. Specifically, there is a need for Quantum Low-Density Parity-Check (QLDPC) codes that offer:

• Scalability: The ability to construct codes for large numbers of qubits.
• Constant Rate: A non-vanishing ratio of logical qubits to physical qubits as the code size increases.
• Locality: Sparse stabilizer matrices (LDPC structure) to facilitate efficient decoding and implementation on realistic hardware.
• Robustness: Sufficient minimum distance to detect and correct errors.

Existing constructions often struggle to balance these competing requirements. This paper addresses the challenge of constructing a scalable family of QLDPC codes with a constant rate and strong structural properties by leveraging combinatorial objects known as sub-exceeding functions.

2. Methodology

The authors propose a novel construction method that combines classical linear codes derived from sub-exceeding functions with two specific quantum code construction frameworks: the Hypergraph Product and the Generalized Shor Construction.

A. Classical Foundation: Sub-exceeding Functions

The foundation of the work relies on two families of classical binary linear codes, $L_k$ and $L^+_k$, constructed from sub-exceeding functions.

• Definition: A sub-exceeding function is a mapping $f: \{1, \dots, k\} \to \{0, \dots, k-1\}$ such that $f(i) \leq i-1$. These functions are in bijection with permutations and labeled trees.
• Code $L_k$:
  • Parameters: $[2k, k, d]$.
  • Minimum Distance ($d$): $3$for$k=3$;$4$for$k \geq 4$.
  • Structure: Systematic form $(c | f(c))$. The generator matrix is $G_{L_k} = [I_k | G_k]$, where $G_k$ is a binary matrix with zeros on the diagonal and ones elsewhere.
• Code $L^+_k$:
  • Parameters: $[3k, k, d]$.
  • Minimum Distance ($d$): $5$for$k=4$;$6$for$k \geq 5$.
  • Structure: Generator matrix $G_{L^+_k} = [I_k | G_k | I_k]$.

B. Quantum Construction Framework

The authors construct a CSS (Calderbank-Shor-Steane) quantum code $Q_{L_k}$ by combining $L_k$ and $L^+_k$ using the following steps:

1. Parity-Check and Generator Matrices:

   • The parity-check matrix for $L_k$ is $H_{L_k} = [G_k | I_k]$.
   • The parity-check matrix for $L^+_k$ is derived as $H_{L^+_k} = [A_{L^+_k} | I_{2k}]$.

2. Hybrid Construction:
   The paper utilizes a hybrid approach combining the Hypergraph Product and Generalized Shor methods to define the stabilizer matrices $H_X$ and $H_Z$:

   • $H_X$ (X-type checks): Constructed via the tensor product of the parity-check matrix of $L_k$ and the identity matrix of the length of $L^+_k$:
     $$H_X = H_{L_k} \otimes I_{3k}$$
   • $H_Z$ (Z-type checks): Constructed via the tensor product of the generator matrix of $L_k$ and the parity-check matrix of $L^+_k$:
     $$H_Z = G_{L_k} \otimes H_{L^+_k}$$

3. Commutation Verification:
   The construction satisfies the CSS condition $H_X H_Z^T = 0$, ensuring the stabilizer group is abelian. This is verified through the orthogonality of the underlying classical codes ($H_{L_k} G_{L_k}^T = 0$).

3. Key Contributions

• New Code Family: Introduction of a scalable family of quantum codes denoted as $Q_{L_k}$ with parameters $[[6k^2, k^2, d]]$.
• Combinatorial Integration: Successful adaptation of sub-exceeding functions (typically used in permutation theory) to the design of high-performance error-correcting codes.
• Hybrid Construction Technique: A specific application of the Hypergraph Product and Generalized Shor construction that yields a code with a constant rate and LDPC properties.
• Explicit Encoding/Decoding: The paper provides a detailed operational framework, including:
  • An explicit initialization procedure for the $6k^2$ qubit register.
  • A structured quantum encoding circuit utilizing Hadamard and CNOT gates based on the regularity of $H_X$.
  • A simplified decoding procedure leveraging the block-wise structure of the stabilizers.

4. Results

The constructed quantum codes exhibit the following parameters and properties:

• Parameters: $[[n, k_{log}, d]] = [[6k^2, k^2, d]]$.
  • Length ($n$): $6k^2$ physical qubits.
  • Dimension ($k_{log}$): $k^2$ logical qubits.
  • Rate ($R$): $k^2 / 6k^2 = 1/6$. This is a constant rate regardless of $k$.
• Minimum Distance ($d$):
  • For $k = 3$: $d = 3$.
  • For $k \geq 4$: $d = 4$.
  • Note: The distance is determined by $\min(d(L_k), d(L^+_k))$. Since $d(L_k) = 4$ for $k \geq 4$, the quantum code achieves $d=4$.
• Locality and Sparsity:
  • The codes are LDPC (Low-Density Parity-Check).
  • Each X-type stabilizer generator acts on exactly $k$ qubits.
  • The stabilizer matrices are sparse, ensuring that each qubit participates in a bounded number of checks.
• Examples:
  • $k=4$: Produces a $[[96, 16, 4]]$ code.
  • $k=5$: Produces a $[[120, 25, 4]]$ code.

5. Significance

• Scalability with Constant Rate: Unlike many quantum codes where the rate drops to zero as the code size increases, this family maintains a constant rate of $1/6$. This makes it highly suitable for large-scale quantum error correction where resource efficiency is paramount.
• Structural Regularity: The codes possess a rich combinatorial structure inherited from sub-exceeding functions. This regularity simplifies the analysis of code parameters and facilitates the design of efficient, local decoding algorithms.
• Error Correction Capability: With a minimum distance of $d=4$ for $k \geq 4$, the code can detect any 3-qubit error and correct any single-qubit error (and potentially some multi-qubit errors depending on the specific error model), providing robust protection for logical qubits.
• Implementation Feasibility: The explicit encoding circuit and the block-wise structure of the stabilizers suggest that these codes are well-suited for implementation on near-term and future quantum hardware, as they allow for parallel syndrome measurement and local correction.

In conclusion, this paper presents a mathematically rigorous and practically promising approach to constructing quantum LDPC codes, bridging the gap between combinatorial theory and quantum error correction requirements.