🔢 mathematics

List-Decodable Folded Quantum Hermitian Codes

This paper constructs folded quantum Hermitian codes using the CSS framework and proves they are list-decodable up to the quantum Singleton bound, offering comparable performance to folded quantum Reed-Solomon codes but with more efficient implementations due to their ability to achieve similar lengths over smaller alphabets.

Original authors: Gretchen L. Matthews, Julia Shapiro

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Gretchen L. Matthews, Julia Shapiro

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Fixing Broken Quantum Messages

Imagine you are trying to send a secret message across a very noisy room. In the quantum world, this message is made of "qubits" (quantum bits). Unfortunately, the room is so noisy that the message gets scrambled.

For a long time, scientists have used Quantum Error-Correcting Codes to fix these mistakes. Think of these codes like a safety net. If a few letters in your message get changed, the net catches the error and lets you reconstruct the original message.

However, there is a limit to how much noise this net can handle. If the noise is too high, the net breaks, and you can't tell what the message was. This paper introduces a new, stronger type of safety net that can handle much more noise than before, while using less "space" to do it.

The Ingredients: Folding and Hermitian Curves

To understand the new invention, we need to look at two main ideas the authors combined: Folding and Hermitian Codes.

1. The "Folding" Trick (The Origami Analogy)

Imagine you have a long scroll of paper with a message written on it. If the paper gets wet and smudges, it's hard to read.

Old Way: You try to read the whole long scroll at once. If too many spots are smudged, you give up.
The "Folding" Way: Instead of reading the whole scroll, you fold the paper into a thick stack. You group several letters together into one big "block."
- If one letter in a block is smudged, the whole block is still mostly intact.
- By treating a group of letters as a single, larger unit, you can ignore small errors and focus on the big picture.
- In the paper, this is called Folding. It allows the code to tolerate a higher percentage of errors (up to the theoretical limit known as the "Singleton bound").

2. The "Hermitian" Shape (The Garden Analogy)

To make these folded codes work, you need a specific mathematical structure to organize the letters.

Reed-Solomon Codes (The Old Standard): These are like a simple, straight garden path. They work well, but to get a long path, you need a huge field (a very large "alphabet" or vocabulary).
Hermitian Codes (The New Standard): These are like a complex, beautiful garden with many winding paths and rich structures (mathematically, they are based on "positive-genus curves").
- The Advantage: You can fit a much longer garden (a longer code) into a smaller field (a smaller alphabet) using Hermitian codes than you can with the simple straight path.
- Why it matters: In computing, a smaller "alphabet" means the system is more efficient and easier to build.

The Innovation: Folding the Quantum Hermitian Garden

Before this paper, scientists had successfully "folded" the simple Reed-Solomon codes for quantum computers. However, those folded codes still required a massive vocabulary (large alphabet size) to work well. To fix this, previous researchers had to use a complicated, expensive technique called "distance amplification" (which is like adding extra heavy machinery just to make the code fit).

What this paper does:
The authors, Matthews and Shapiro, took the Hermitian garden (which is naturally efficient) and applied the folding trick to it.

They built a new code: They created "Folded Quantum Hermitian Codes."
They proved it works: They showed that these codes can correct errors up to the absolute maximum limit allowed by physics (the quantum Singleton bound).
The "List-Decoding" Superpower:
- Usually, a code tries to find the one correct answer. If the noise is too high, it fails.
- List-Decoding is like a detective who, when the evidence is messy, doesn't guess one suspect. Instead, they produce a short list of the top 5 most likely suspects.
- The paper proves that their new code can produce this short list of possibilities even when the noise is extremely high.
The Efficiency Win:
- Unlike the previous folded codes, these new codes do not need the expensive "distance amplification" machinery.
- They achieve the same high performance with a much smaller alphabet.
- Analogy: It's like building a skyscraper that reaches the same height as a previous one, but using fewer bricks and without needing a giant crane.

The Result

The paper concludes that by using these specific mathematical shapes (Hermitian curves) and the folding technique, we can create quantum codes that:

Handle more errors than ever before.
Are more efficient (smaller alphabet size).
Can be decoded quickly by a computer to find the correct message from a short list of candidates.

In short, they found a smarter, more compact way to protect quantum information from noise, making future quantum computers potentially more reliable and easier to build.

Technical Summary: List-Decodable Folded Quantum Hermitian Codes

Problem Statement
Quantum error-correcting codes derived from algebraic-geometric (AG) codes have long been a subject of study, with Hermitian curves playing a prominent role due to their rich automorphism groups and favorable asymptotic parameters. While classical list decoding has advanced significantly—culminating in folded Reed-Solomon codes that approach the Singleton bound—translating these techniques to the quantum setting presents challenges. Specifically, folded quantum Reed-Solomon codes, recently constructed by Bergamaschi, Golowich, and Gunn, achieve the quantum Singleton bound but suffer from large alphabet sizes. To mitigate this, those works employed "quantum distance amplification," a technique that increases complexity. The central problem addressed in this paper is whether folded quantum codes can be constructed from positive-genus curves (specifically Hermitian curves) to achieve comparable list-decoding performance and approach the quantum Singleton bound while utilizing smaller alphabet sizes, potentially rendering distance amplification unnecessary.

Methodology
The authors employ the Calderbank-Shor-Steane (CSS) framework to construct quantum codes from classical folded AG codes. The methodology proceeds through the following steps:

Classical Folding: The authors utilize the automorphism group of the Hermitian curve $H$ over $\mathbb{F}_{q^2}$ . Unlike Reed-Solomon codes which rely on a single cyclic orbit, Hermitian codes utilize automorphisms $\sigma_{\delta, \mu}$ that partition the affine rational points into multiple structured orbits. Consecutive evaluations along these orbits are grouped into single symbols over an extension field $\mathbb{F}_{q^m}$ , creating folded one-point Hermitian codes $C^{(\sigma, m)}$ .
CSS Construction: Two folded classical Hermitian codes, $C_1^{(\sigma, m)}$ and $C_2^{(\sigma, m)}$ , are selected such that the dual of the second is contained in the first ( $(C_2^{(\sigma, m)})^\perp \subseteq C_1^{(\sigma, m)}$ ). The authors formalize the condition under which folding commutes with the CSS construction, ensuring the resulting quantum code is well-defined.
Entanglement-Assisted Extension: The paper also presents a construction for entanglement-assisted folded quantum AG codes. This approach relaxes the strict inclusion requirement ( $C_2^\perp \subseteq C_1$ ) by utilizing pre-shared entanglement (ebits), allowing any two folded Hermitian codes to define a quantum code.
Decoding Analysis: The list-decodability of the resulting quantum codes is analyzed by leveraging the list-decodability of the underlying classical folded Hermitian codes. The authors apply a lemma from prior work (Bergamaschi et al.) stating that if the constituent classical codes are $(\tau, L)$ -list-decodable, the resulting CSS code is $(\tau, L^2)$ -quantum list-decodable.

Key Contributions and Results

Construction of Folded Quantum Hermitian Codes (FQHC): The paper provides explicit constructions of folded quantum Hermitian codes using the CSS framework. These codes are derived from one-point Hermitian codes folded via specific automorphisms of the Hermitian curve.
List-Decodability up to the Quantum Singleton Bound: The authors prove that FQHCs are $(\tau, L)$ -list-decodable with a decoding radius $\tau = \frac{1 - R_{FQHC}}{2} - \epsilon$ , where $R_{FQHC}$ is the rate of the quantum code. This radius approaches the quantum Singleton bound ( $1 - R$ ), matching the performance of folded quantum Reed-Solomon codes.
Alphabet Size Efficiency: A primary result is the demonstration that FQHCs achieve this performance with an alphabet size of $(1/\epsilon)^{O(1/\epsilon^2)}$ . In contrast, folded quantum Reed-Solomon codes achieving similar bounds require quantum distance amplification, resulting in an alphabet size of $2^{O(1/\epsilon^5)}$ . The authors show that for any $\epsilon$ , the alphabet size of the FQHC is strictly smaller, eliminating the need for distance amplification.
Deterministic Decoding Algorithm: The paper establishes the existence of a deterministic quantum list-decoding algorithm. The procedure involves measuring stabilizers to obtain classical syndromes, running classical list decoders on the constituent folded Hermitian codes to generate candidate error lists, and pairing these lists to form a polynomial-size list of candidate Pauli errors. The total runtime is $N^{O(1/\epsilon^2)}$ .
Entanglement-Assisted Construction: The paper extends the framework to entanglement-assisted codes, allowing for the construction of quantum codes from any pair of folded Hermitian codes without requiring the dual containment condition, at the cost of consuming entanglement.

Significance
The paper claims that its construction of folded quantum Hermitian codes offers a more efficient alternative to folded quantum Reed-Solomon codes. By leveraging the geometric structure of positive-genus curves, the authors achieve list-decodability up to the quantum Singleton bound while maintaining a significantly smaller alphabet size. Crucially, the work demonstrates that the "costly" technique of quantum distance amplification is not necessary to achieve near-optimal decoding radii when using Hermitian curves. This suggests that positive-genus curves provide a superior trade-off between rate, error-correction radius, and alphabet size for folded quantum codes. The paper concludes by noting that constructing explicit folded quantum AG codes from other positive-genus curves and exploring constructions beyond the CSS and entanglement-assisted frameworks remain open problems.