論文の概要: Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time

• arxiv url: http://arxiv.org/abs/2609.40313v1
• Date: Wed, 30 Sep 2026 17:53:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:28.288232
• Title: Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time
• Title（参考訳）: ほぼ線形時間で復調可能な量子LDPC符号列の明示的容量化
• Abstract要約: 量子符号化理論では、コードファミリーがLDPCであることが非常に望ましい。 我々は、リスト復号化能力を達成する量子LDPC符号の最初の明示的な構成を提供する。 我々の明示的なコード構成は、アロン・エドモンド・ルービ(AEL)増幅の量子アナログによる拡張グラフに基づいている。
• 参考スコア（独自算出の注目度）: 42.71008503465268
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In classical coding theory, the quest for explicit codes achieving list decoding capacity has been an important driving force. While random codes are easily shown to achieve capacity, an explicit construction was only discovered decades later in the seminal work [Guruswami and Rudra, STOC 2006]. In quantum coding theory, it is highly desirable that a code family be LDPC. While good quantum codes were known for decades, obtaining the additional LDPC property was elusive. In fact, only very recently that good quantum LDPC codes were discovered in a breakthrough work [Panteleev and Kalachev, STOC 2022]. In this context, a natural question is to ask for an explicit family of quantum codes achieving list decoding capacity while also possessing the important LDPC property. In this work, we provide (to the best of our knowledge) the first explicit constructions of quantum LDPC codes achieving list decoding capacity, namely, with a list decoding radius approaching the quantum Singleton bound with constant list sizes. Furthermore, we provide near-linear time (in the block-length) list decoding algorithms approaching capacity. Our explicit code construction are based on expander graphs via the quantum analogue of Alon-Edmonds-Luby (AEL) amplification [Bergamaschi, Golowich and Gunn, STOC 2024], and this enables the important LDPC property. Our efficient list decoding algorithms are obtained by generalizing the classical expander-based weak-regularity list decoding algorithms [Srivastava and Tulsiani, FOCS 2025] [Jeronimo and Singh, 2025] to suitable instantiations of quantum AEL.
• Abstract（参考訳）: 古典的符号化理論では、リストの復号化能力を達成するための明示的な符号の探索が重要な推進力となっている。 ランダム符号は容易にキャパシティを達成できることが示されるが、明示的な構成は数十年後になって初めて精巧な研究(Guruswami and Rudra, STOC 2006)で発見された。 量子符号化理論では、コードファミリーがLDPCであることが非常に望ましい。 良い量子符号は数十年にわたって知られていたが、追加のLDPC特性を得ることができた。 実際、優れた量子LDPC符号がブレークスルーで発見されたのはごく最近のことです [Panteleev and Kalachev, STOC 2022]。 この文脈において、自然な疑問は、重要なLDPC特性をもちながら、リスト復号能力を達成するための量子コードの明示的なファミリーを求めることである。 本研究では、リスト復号能力を達成する量子LDPC符号の最初の明示的な構成、すなわち、定数リストサイズで有界な量子シングルトンに近づいたリスト復号半径を提供する。 さらに、ブロック長リストのデコードアルゴリズムがキャパシティに近づき、ほぼ線形時間(ブロック長)を提供する。 我々の明示的なコード構成は、アロン・エドモンド・ルービ(AEL)増幅(Bergamaschi, Golowich and Gunn, STOC 2024)の量子アナログによる拡張グラフに基づいており、これは重要なLDPC特性を可能にする。 我々の効率的なリスト復号アルゴリズムは、古典的拡張器に基づく弱正則リスト復号アルゴリズム (Srivastava and Tulsiani, FOCS 2025] [Jeronimo and Singh, 2025] を量子AELの適切なインスタンス化に応用することにより得られる。

関連論文リスト

• From Random Quantum Codes to Explicit qLDPC Codes via Local Properties [69.74086792721901]
  ネスト空間に対する局所座標ワイド線形(LCL)フレームワークの量子版である$S subseteq C$ を開発した。 我々は、最適なリストサイズを持つ量子リスト復号可能な符号とリスト復号可能な符号の最初の明示的な構成を得る。 明示的な構成はすべてqLDPC符号であり、量子エラー訂正符号の重要な性質である。
  論文  参考訳（メタデータ） (2026-09-30T17:39:08Z)
• Growing Sparse Quantum Codes from a Seed [0.0]
  量子反復符号のみを結合することにより、量子LDPC符号を構築することができることを示す。 また、2ビットの量子ビットフリップとフェーズフリップの繰り返しコードでさえ、CSSコードを作成することができるため、非常に強力であることも示しています。
  論文  参考訳（メタデータ） (2025-07-17T19:05:52Z)
• Quantum Hypothesis Testing Lemma for Deterministic Identification over Quantum Channels [49.126395046088014]
  この研究は、量子設定におけるDIコードの存在が、出力量子状態の修正された空間における適切なパッキングから従うことを示した。 これにより、同時復号化アプローチを超えて、量子チャネル上でのDIのキャパシティの低いバウンダリを厳格化することができる。
  論文  参考訳（メタデータ） (2025-04-29T17:57:36Z)
• List Decodable Quantum LDPC Codes [49.2205789216734]
  我々は、ほぼ最適レート距離のトレードオフを持つ量子低密度パリティチェック(QLDPC)符号の構成を行う。 復号化可能なQLDPCコードとユニークなデコーダを効率よくリストアップする。
  論文  参考訳（メタデータ） (2024-11-06T23:08:55Z)
• Neural Belief Propagation Decoding of Quantum LDPC Codes Using Overcomplete Check Matrices [60.02503434201552]
  元のチェック行列における行の線形結合から生成された冗長な行を持つチェック行列に基づいてQLDPC符号を復号する。 このアプローチは、非常に低い復号遅延の利点を付加して、復号性能を著しく向上させる。
  論文  参考訳（メタデータ） (2022-12-20T13:41:27Z)
• Quantum Error Correction via Noise Guessing Decoding [0.0]
  量子誤り訂正符号(QECC)は、量子通信と量子計算の両方において中心的な役割を果たす。 本稿では,有限ブロック長レジームの最大性能を達成できるQECCの構築と復号化が可能であることを示す。
  論文  参考訳（メタデータ） (2022-08-04T16:18:20Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。