論文の概要: Exact Maximum Likelihood Decoding beyond Treewidth via Rank-Decomposition Dynamic Programming

• arxiv url: http://arxiv.org/abs/2609.39556v1
• Date: Wed, 30 Sep 2026 11:54:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:27.633347
• Title: Exact Maximum Likelihood Decoding beyond Treewidth via Rank-Decomposition Dynamic Programming
• Title（参考訳）: ランク分解動的プログラミングによる木幅を超える最大値デコーディング
• Abstract要約: ランク分解動的プログラミングに基づく新しい復号アルゴリズム(Rank DP)を提案する。 パンクされた量子リード・ミュラー符号のデコーダ時間デコードと、独立した単一量子ビットパウリ雑音の下で距離が増大するステイン結合族を与える。
• 参考スコア（独自算出の注目度）: 4.207274960389197
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Maximum-likelihood decoding provides an optimal decoding strategy for quantum error correction under stochastic Pauli noise. However, computing logical-class probabilities is challenging, and the leading exact tensor-network contraction requires time exponential in treewidth. In this work, we introduce a new decoding algorithm based on rank-decomposition dynamic programming (Rank DP). We express decoding partition functions with independent local fault factors as quadratic sums of powers and apply Rank DP. The resulting exact evaluator has arithmetic complexity polynomial in the input size and exponential in the Tanner graph's rank-width with respect to the fault partition, including decomposition construction. After Gaussian elimination, it gives polynomial-time decoding for punctured quantum Reed-Muller codes and a Steane-concatenated family with growing distance under independent single-qubit Pauli noise. Standard contraction of the corresponding tensor networks requires superpolynomial time. A nonnegative realization gives relative floating-point error bounds under explicit arithmetic assumptions. Numerical experiments demonstrate runtime advantages over the tested tensor-network implementations on selected code-capacity and circuit-level instances, with full likelihood evaluation for Reed-Muller codes up to $1{,}023$ qubits. We further use these likelihoods to learn circuit noise parameters from syndromes, evaluate rare postselection probabilities, and quantify decoder optimality gaps. Our work opens new avenues for exploiting algebraic structure in quantum decoding and noise characterization.
• Abstract（参考訳）: 最大様相復号法は、確率的パウリ雑音下での量子誤り訂正のための最適復号法を提供する。 しかし、論理クラス確率の計算は困難であり、正確なテンソル・ネットワークの収縮はツリー幅で指数関数的な時間を必要とする。 本研究では,ランク分解動的プログラミング(Rank DP)に基づく新しい復号アルゴリズムを提案する。 我々は、独立な局所的故障要因を持つ復号化分割関数をパワーの2次和として表現し、ランクDPを適用した。 得られた正確な評価器は、入力サイズにおける算術複雑性多項式を持ち、分解構成を含む断層分割に関して、タナーグラフのランク幅の指数関数である。 ガウスの除去後、これは独立した単一量子ビットのパウリ雑音の下で距離が増大するパンクテッド量子リード・ミュラー符号とステアン結合族に対して多項式時間復号を与える。 対応するテンソルネットワークの標準収縮にはスーパーポリノミアル時間が必要である。 非負の実現は、明示的な算術的仮定の下で相対的な浮動小数点誤差境界を与える。 数値実験により、選択されたコード容量と回路レベルのインスタンス上でのテンソルネットワークの実装に対する実行時の利点を実証し、リード・ミュラー符号の最大1{,}023$ qubitsに対する完全な可能性評価を行った。 さらに、これらの可能性を利用して、症候群から回路ノイズパラメータを学習し、稀な選択確率を評価し、デコーダの最適性ギャップを定量化する。 我々の研究は、量子デコーディングとノイズ特性の代数的構造を利用するための新しい道を開く。

関連論文リスト

• Cycle Codes and Decoded Quantum Interferometry [1.2336438977950792]
  固定されたインスタンスに対して不完全復号化が存在する場合の満足度保証を導出し、ランダムなインスタンスに対する事前結果を一般化する。 最小重復号法は、二進サイクル符号の既知の結果とは対照的に、$q>2$のすべてのフィールドに対してNPハードであることが示される。
  論文  参考訳（メタデータ） (2026-09-30T16:07:40Z)
• Quantum Message Passing Convergence and Vanishing Block-Error Probability for Random LDPC Codes [9.855041870231533]
  BPQM (Breief propagation with quantum message) は、古典的量子チャネル上で伝送される古典的符号を復号する量子アルゴリズムである。 ランダム$q$-ary LDPC符号に対する2段階BPQMデコーダを対称$q$-ary純状態チャネル上に構築する。 アンサンブル平均ブロックエラー確率はブロック長$N$が無限大になる傾向にあるため消滅することを示す。
  論文  参考訳（メタデータ） (2026-09-05T03:36:03Z)
• Certified decoding of quantum LDPC codes [31.93810256110857]
  量子低密度パリティチェック(qLDPC)符号は、フォールトトレラント量子計算の量子ビットオーバーヘッドを桁違いに減少させる。 多くの物理誤差は安定化器と同値であるため、縮退した最大形(ML)デコーダは、単一エラーではなく分割関数であるエラーの同値クラス全体の確率を比較する必要がある。 非方向性のグラフィカルモデルにおいて、退化復号化を確率的推論として扱う。
  論文  参考訳（メタデータ） (2026-08-26T08:57:01Z)
• Coset Ensemble Decoder for Quantum Error Correction with Algorithm-Hardware Co-Design [16.143601808851162]
  量子エラー補正(QEC)は、エラー症候群をリアルタイムで抽出し、復号する。 QECの重要なコンポーネントはデコーダであり、これは古典的なサブシステムであり、高い論理精度と超低レイテンシを同時に提供する必要がある。 本稿では,既存のアプローチに対する精度-遅延トレードオフを改善するアルゴリズム-ハードウェア共同設計を提案する。
  論文  参考訳（メタデータ） (2026-06-09T16:37:13Z)
• Fault-Tolerant Quantum Memory using Low-Depth Random Circuit Codes [0.24578723416255752]
  低深さランダム回路符号は、量子誤り訂正に望ましい多くの特性を有する。 1次元ランダム回路符号の符号化状態を作成するための耐故障性蒸留プロトコルを設計する。 数値シミュレーションにより,提案プロトコルはエラー率を最大2%の誤差率で補正できることを示す。
  論文  参考訳（メタデータ） (2023-11-29T19:00:00Z)
• Scalable noisy quantum circuits for biased-noise qubits [37.69303106863453]
  安定猫量子ビットの既存システムに動機づけられたビットフリップ誤差のみに影響されるバイアスノイズ量子ビットを考察する。 現実的なノイズモデルでは、位相フリップは無視できないが、Pauli-Twirling近似では、ベンチマークが最大106ドルのゲートを含む回路の正しさを確認できる。
  論文  参考訳（メタデータ） (2023-05-03T11:27:50Z)
• Machine Learning-Aided Efficient Decoding of Reed-Muller Subcodes [59.55193427277134]
  Reed-Muller (RM) 符号は、一般的なバイナリインプットメモリレス対称チャネルの容量を達成する。 RM符号は制限されたレートのみを許容する。 効率的なデコーダは、RM符号に対して有限長で利用可能である。
  論文  参考訳（メタデータ） (2023-01-16T04:11:14Z)
• Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
  我々は、$c-不連続性を計算すること、あるいはそれを定数乗算係数の範囲内で近似することの問題はNP完全であることを示す。 CSSコード、$dコード、ハイパーグラフコードなど、さまざまなコードファミリの相違点に関するバウンダリを提供します。 以上の結果から,一般的な量子誤り訂正符号に対するフォールトトレラント論理ゲートの発見は,計算に難題であることが示唆された。
  論文  参考訳（メタデータ） (2021-08-10T15:00:20Z)

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

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