List-Decodable Folded Quantum Hermitian Codes

Technische Zusammenfassung: Listen-decodierbare gefaltete Quanten-Hermitische Codes

Problemstellung
Quantenfehlerkorrigierende Codes, die aus algebraisch-geometrischen (AG) Codes abgeleitet sind, sind seit langem Gegenstand von Untersuchungen, wobei Hermitische Kurven aufgrund ihrer reichhaltigen Automorphismengruppen und günstiger asymptotischer Parameter eine herausragende Rolle spielen. Während sich das klassische Listen-Decodieren erheblich weiterentwickelt hat – mit gefalteten Reed-Solomon-Codes als Höhepunkt, die die Singleton-Schranke annähern – stellt die Übertragung dieser Techniken auf das Quantensetting Herausforderungen dar. Insbesondere erreichen gefaltete Quanten-Reed-Solomon-Codes, die kürzlich von Bergamaschi, Golowich und Gunn konstruiert wurden, zwar die Quanten-Singleton-Schranke, leiden jedoch unter großen Alphabetgrößen. Um dies zu mildern, setzten diese Arbeiten „Quanten-Distanzverstärkung" ein, eine Technik, die die Komplexität erhöht. Das zentrale Problem, das in diesem Papier behandelt wird, besteht darin, ob gefaltete Quantencodes aus Kurven positiven Geschlechts (speziell Hermitischen Kurven) konstruiert werden können, um eine vergleichbare Listen-Decodierleistung zu erzielen und sich der Quanten-Singleton-Schranke anzunähern, während kleinere Alphabetgrößen genutzt werden, was die Distanzverstärkung möglicherweise überflüssig macht.

Methodik
Die Autoren verwenden das Calderbank-Shor-Steane (CSS)-Rahmenwerk, um Quantencodes aus klassischen gefalteten AG-Codes zu konstruieren. Die Methodik verläuft in folgenden Schritten:

1. Klassisches Falten: Die Autoren nutzen die Automorphismengruppe der Hermitischen Kurve $H$ über $\mathbb{F}_{q^2}$. Im Gegensatz zu Reed-Solomon-Codes, die sich auf eine einzige zyklische Orbitale stützen, nutzen Hermitische Codes Automorphismen $\sigma_{\delta, \mu}$, die die affinen rationalen Punkte in mehrere strukturierte Orbits partitionieren. Aufeinanderfolgende Auswertungen entlang dieser Orbits werden zu einzelnen Symbolen über einem Erweiterungskörper $\mathbb{F}_{q^m}$ gruppiert, wodurch gefaltete einpunktige Hermitische Codes $C^{(\sigma, m)}$ entstehen.
2. CSS-Konstruktion: Zwei gefaltete klassische Hermitische Codes, $C_1^{(\sigma, m)}$ und $C_2^{(\sigma, m)}$, werden so ausgewählt, dass das Dual des zweiten im ersten enthalten ist ($(C_2^{(\sigma, m)})^\perp \subseteq C_1^{(\sigma, m)}$). Die Autoren formalisieren die Bedingung, unter der das Falten mit der CSS-Konstruktion kommutiert, und stellen sicher, dass der resultierende Quantencode wohldefiniert ist.
3. Verschränkungsunterstützte Erweiterung: Das Papier präsentiert zudem eine Konstruktion für verschränkungsunterstützte gefaltete Quanten-AG-Codes. Dieser Ansatz lockert die strikte Inklusionsanforderung ($C_2^\perp \subseteq C_1$) durch die Nutzung vorab geteilter Verschränkung (Ebits), was es ermöglicht, dass beliebige zwei gefaltete Hermitische Codes einen Quantencode definieren.
4. Decodierungsanalyse: Die Listen-Decodierbarkeit der resultierenden Quantencodes wird analysiert, indem die Listen-Decodierbarkeit der zugrundeliegenden klassischen gefalteten Hermitischen Codes genutzt wird. Die Autoren wenden ein Lemma aus früheren Arbeiten (Bergamaschi et al.) an, wonach, wenn die konstituierenden klassischen Codes $(\tau, L)$-listen-decodierbar sind, der resultierende CSS-Code $(\tau, L^2)$-quanten-listen-decodierbar ist.

Hauptbeiträge und Ergebnisse

• Konstruktion gefalteter Quanten-Hermitischer Codes (FQHC): Das Papier liefert explizite Konstruktionen gefalteter Quanten-Hermitischer Codes unter Verwendung des CSS-Rahmenwerks. Diese Codes werden aus einpunktigen Hermitischen Codes abgeleitet, die durch spezifische Automorphismen der Hermitischen Kurve gefaltet werden.
• Listen-Decodierbarkeit bis zur Quanten-Singleton-Schranke: Die Autoren beweisen, dass FQHCs $(\tau, L)$-listen-decodierbar sind mit einem Decodieradius $\tau = \frac{1 - R_{FQHC}}{2} - \epsilon$, wobei $R_{FQHC}$ die Rate des Quantencodes ist. Dieser Radius nähert sich der Quanten-Singleton-Schranke ($1 - R$) an und entspricht der Leistung gefalteter Quanten-Reed-Solomon-Codes.
• Effizienz der Alphabetgröße: Ein Hauptergebnis ist der Nachweis, dass FQHCs diese Leistung mit einer Alphabetgröße von $(1/\epsilon)^{O(1/\epsilon^2)}$ erreichen. Im Gegensatz dazu erfordern gefaltete Quanten-Reed-Solomon-Codes, die ähnliche Schranken erreichen, eine Quanten-Distanzverstärkung, was zu einer Alphabetgröße von $2^{O(1/\epsilon^5)}$ führt. Die Autoren zeigen, dass für jedes $\epsilon$ die Alphabetgröße des FQHC strikt kleiner ist, wodurch die Notwendigkeit einer Distanzverstärkung entfällt.
• Deterministischer Decodieralgorithmus: Das Papier etabliert die Existenz eines deterministischen Quanten-Listen-Decodieralgorithmus. Das Verfahren umfasst das Messen von Stabilisatoren zur Gewinnung klassischer Syndrome, das Ausführen klassischer Listen-Decodierer auf den konstituierenden gefalteten Hermitischen Codes zur Generierung von Kandidatenfehlerlisten und das Pairing dieser Listen, um eine Liste von Kandidaten-Pauli-Fehlern polynomieller Größe zu bilden. Die Gesamtlaufzeit beträgt $N^{O(1/\epsilon^2)}$.
• Verschränkungsunterstützte Konstruktion: Das Papier erweitert das Rahmenwerk auf verschränkungsunterstützte Codes und ermöglicht die Konstruktion von Quantencodes aus beliebigen Paaren gefalteter Hermitischer Codes ohne die Anforderung der Dual-Inklusionsbedingung, jedoch unter dem Preis des Verbrauchs von Verschränkung.

Bedeutung
Das Papier behauptet, dass seine Konstruktion gefalteter Quanten-Hermitischer Codes eine effizientere Alternative zu gefalteten Quanten-Reed-Solomon-Codes darstellt. Durch die Nutzung der geometrischen Struktur von Kurven positiven Geschlechts erreichen die Autoren eine Listen-Decodierbarkeit bis zur Quanten-Singleton-Schranke bei gleichzeitiger Aufrechterhaltung einer deutlich kleineren Alphabetgröße. Entscheidend zeigt die Arbeit, dass die „kostspielige" Technik der Quanten-Distanzverstärkung nicht notwendig ist, um nahezu optimale Decodieradien zu erreichen, wenn Hermitische Kurven verwendet werden. Dies legt nahe, dass Kurven positiven Geschlechts einen überlegenen Kompromiss zwischen Rate, Fehlerkorrekturradius und Alphabetgröße für gefaltete Quantencodes bieten. Das Papier schließt mit der Feststellung, dass die Konstruktion expliziter gefalteter Quanten-AG-Codes aus anderen Kurven positiven Geschlechts und die Erforschung von Konstruktionen jenseits der CSS- und verschränkungsunterstützten Rahmenwerke offene Probleme bleiben.