論文の概要: Online Gaussian elimination for quantum LDPC decoding

• arxiv url: http://arxiv.org/abs/2504.05080v1
• Date: Mon, 07 Apr 2025 13:49:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-08 14:10:41.036748
• Title: Online Gaussian elimination for quantum LDPC decoding
• Title（参考訳）: 量子LDPC復号化のためのオンラインガウス除去
• Authors: Sam J. Griffiths, Asmae Benhemou, Dan E. Browne,
• Abstract要約: LUP分解を維持できるガウス除去アルゴリズムのオンライン版を提案する。 これは、方程式の最終系上でガウス的除去を実行することと等価である。 オンライン版では、従来のオフラインデコーダよりも平均ケースタイムの複雑さが優れていることを実証的に示しています。
• 参考スコア（独自算出の注目度）: 3.1952340441132474
• License:
• Abstract: Decoders for quantum LDPC codes generally rely on solving a parity-check equation with Gaussian elimination, with the generalised union-find decoder performing this repeatedly on growing clusters. We present an online variant of the Gaussian elimination algorithm which maintains an LUP decomposition in order to process only new rows and columns as they are added to a system of equations. This is equivalent to performing Gaussian elimination once on the final system of equations, in contrast to the multiple rounds of Gaussian elimination employed by the generalised union-find decoder. It thus significantly reduces the number of operations performed by the decoder. We consider the generalised union-find decoder as an example use case and present a complexity analysis demonstrating that both variants take time cubic in the number of qubits in the general case, but that the number of operations performed by the online variant is lower by an amount which itself scales cubically. This analysis is also extended to the regime of 'well-behaved' codes in which the number of growth iterations required is bounded logarithmically in error weight. Finally, we show empirically that our online variant outperforms the original offline decoder in average-case time complexity on codes with sparser parity-check matrices or greater covering radius.
• Abstract（参考訳）: 量子LDPC符号のデコーダは一般にガウス除去によるパリティチェック方程式の解法に依存し、一般化されたユニオンフィンデコーダは成長するクラスタで繰り返しこれを実行する。 方程式系に追加される新しい行や列のみを処理するために,LUP分解を保守するガウス除去アルゴリズムのオンライン版を提案する。 これは、一般のユニオンフィンデコーダによって使用されるガウスの除去の多重ラウンドとは対照的に、方程式の最終系上でガウスの除去を実行することと等価である。 これにより、デコーダによって実行される操作数を著しく削減する。 一般化されたUnion-findデコーダを実例として考察し、両変種が一般の場合のキュービット数で3乗時間を取ることを示す複雑性解析を行うが、オンライン変種によって実行される演算の数は、それ自体が3乗にスケールする量によって減少する。 この分析は、必要となる成長イテレーションの数が誤差重みで対数的に制限されるような ' well-behaved' 符号の体系にも拡張される。 最後に、我々のオンライン版は、スペーサーパリティチェック行列以上の被覆半径を持つコードに対して、平均ケースタイムの複雑さでオリジナルのオフラインデコーダよりも優れていることを実証的に示す。

関連論文リスト

• Cluster Decomposition for Improved Erasure Decoding of Quantum LDPC Codes [7.185960422285947]
  任意の量子LDPC符号に適用可能な新しい消去復号器を導入する。 制約のないサイズのクラスタを許可することにより、このデコーダは、最大限のML(maximum-likelihood)パフォーマンスを達成する。 私たちが研究した一般的な量子LDPC符号に対しては、クラスタデコーダを用いてML性能曲線を推定することができる。
  論文  参考訳（メタデータ） (2024-12-11T23:14:23Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• qecGPT: decoding Quantum Error-correcting Codes with Generative Pre-trained Transformers [5.392298820599664]
  生成モデルを用いて量子誤り訂正符号を復号するフレームワークを提案する。 自動回帰ニューラルネットワーク、特にトランスフォーマーを用いて、論理演算子とシンドロームの結合確率を学習する。 我々のフレームワークは汎用的であり、様々なトポロジを持つ任意のエラーモデルや量子コードに適用できる。
  論文  参考訳（メタデータ） (2023-07-18T07:34:02Z)
• Quick Adaptive Ternary Segmentation: An Efficient Decoding Procedure For Hidden Markov Models [70.26374282390401]
  ノイズの多い観測から元の信号(すなわち隠れ鎖)を復号することは、ほぼすべてのHMMに基づくデータ分析の主要な目標の1つである。 本稿では,多対数計算複雑性において隠れた列を復号化するための分法であるQuick Adaptive Ternary(QATS)を提案する。
  論文  参考訳（メタデータ） (2023-05-29T19:37:48Z)
• Neural Belief Propagation Decoding of Quantum LDPC Codes Using Overcomplete Check Matrices [60.02503434201552]
  元のチェック行列における行の線形結合から生成された冗長な行を持つチェック行列に基づいてQLDPC符号を復号する。 このアプローチは、非常に低い復号遅延の利点を付加して、復号性能を著しく向上させる。
  論文  参考訳（メタデータ） (2022-12-20T13:41:27Z)
• Efficient Nearest Neighbor Search for Cross-Encoder Models using Matrix Factorization [60.91600465922932]
  本稿では,クロスエンコーダのみに頼って,二重エンコーダによる検索を回避する手法を提案する。 我々のアプローチは、現在の広く使われている方法よりも優れたテスト時間リコール-vs計算コストトレードオフを提供する。
  論文  参考訳（メタデータ） (2022-10-23T00:32:04Z)
• An efficient decoder for a linear distance quantum LDPC code [0.1657441317977376]
  近年の量子的に優れたqLDPC符号に対する線形時間デコーダを提案する。 我々のデコーダは、一定サイズの領域内で補正を探索する反復アルゴリズムである。
  論文  参考訳（メタデータ） (2022-06-14T02:17:09Z)
• Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learning [58.91954425047425]
  本稿では,分散学習における部分トラグラーの緩和を目的とした,新たな勾配符号化方式を提案する。 L の符号パラメータを L に表わした勾配座標符号化方式を提案する。
  論文  参考訳（メタデータ） (2022-06-06T09:25:40Z)
• Sparse Coding with Multi-Layer Decoders using Variance Regularization [19.8572592390623]
  本稿では,デコーダの正規化を必要とせずに,符号の崩壊を防止する新しいスパース符号化プロトコルを提案する。 本手法は,各潜時符号成分が一定の閾値を超える分散を有するように,直接正規化する。 分散正規化法を用いて訓練した多層デコーダを用いたスパースオートエンコーダは、スペーサー表現を用いた高品質な再構成を実現する。
  論文  参考訳（メタデータ） (2021-12-16T21:46:23Z)
• Quantum Reduction of Finding Short Code Vectors to the Decoding Problem [0.9269394037577176]
  ランダムな線形コード中の短いコードワードの発見から、ハミング計量の復号化まで、量子的に低減する。 このような還元(古典的あるいは量子的)が得られたのはこれが初めてである。
  論文  参考訳（メタデータ） (2021-06-04T22:42:38Z)
• Pruning Neural Belief Propagation Decoders [77.237958592189]
  本稿では,機械学習を用いたBPデコードに対して,過剰完全パリティチェック行列を調整する手法を提案する。 我々は,デコーダの複雑さを低減しつつ,0.27dB,1.5dBのML性能を実現する。
  論文  参考訳（メタデータ） (2020-01-21T12:05:46Z)

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

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