Fugu-MT 論文翻訳(概要): Sparse-Blossom Decoding in $o(1)$ Time

論文の概要: Sparse-Blossom Decoding in $o(1)$ Time

arxiv url: http://arxiv.org/abs/2609.12262v1
Date: Thu, 10 Sep 2026 22:38:01 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-15 07:38:31.560743
Title: Sparse-Blossom Decoding in $o(1)$ Time
Title（参考訳）: o(1)$時間におけるスパースブロッサムデコーディング
Abstract要約: 並列スパース・ブロッソムアルゴリズムは,本来の非並列スパース・フラワーと同じ補正を行うことを示す。これらの結果は、スケーラブルな並列マッチングベースのデコーディングの基礎を提供する。
参考スコア（独自算出の注目度）: 1.0742675209112622
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Matching-based decoding is widely used in quantum error correction, and accelerating it is key to enabling fast and scalable fault-tolerant quantum computation. Minimum-weight perfect matching (MWPM) decoding provides rigorous guarantees for error suppression, while sparse blossom enables its practical implementation at modest problem sizes. However, the runtime of existing sparse-blossom implementations unavoidably increases with problem size, motivating a rigorous parallelization framework that guarantees correctness and a runtime shorter than the syndrome-extraction timescale. Here, we present such a framework and prove that the resulting parallel sparse-blossom algorithm produces the same correction as the original, non-parallel sparse blossom. For the rotated surface code with code distance $d$ and physical error rates below a finite threshold, we prove that the average parallel runtime of decoding for $O(d)$ rounds of syndrome extraction is upper bounded by a quasi-polylogarithmic function of $d$. For a $d$-round decoding window, this implies that the average parallel runtime per round is $o(1)$. We also perform numerical simulation to identify conditions under which the parallel runtime per round decreases with increasing code distance. These results suggest that increasing code distance need not lead to longer parallel decoding times, providing a foundation for scalable parallel matching-based decoding.
Abstract（参考訳）: マッチングベースの復号化は量子誤り訂正において広く使われており、高速でスケーラブルなフォールトトレラント量子計算を実現するための鍵となっている。最小ウェイト完全マッチング(MWPM)復号法は誤りの抑制を厳格に保証する一方、スパース花は最小の問題サイズで実用的な実装を可能にする。しかし、既存のスパース・ブロッサム実装のランタイムは、問題のサイズによって必然的に増加し、厳格な並列化フレームワークをモチベーションとして、正確性と、シンドローム抽出タイムスケールよりも短いランタイムを保証している。そこで本研究では, 並列スパース・ブロッソムアルゴリズムが, 本来の非並列スパース・フラワーと同じ補正を導出することを示す。符号距離$d$と有限しきい値以下での物理誤差率を持つ回転曲面符号に対して、$O(d)$の症候群抽出におけるデコードの平均並列実行時間は、$d$の準多元関数で上限づけられていることを証明する。 $d$ラウンドのデコードウィンドウの場合、ラウンド当たりの平均並列ランタイムは$o(1)$である。また,コード距離の増大に伴い,ラウンド当たりの並列実行時間が減少する条件を特定するための数値シミュレーションも行う。これらの結果は、コード距離の増大は、より長い並列デコーディング時間をもたらす必要がなく、スケーラブルな並列マッチングベースのデコーディングの基礎となることを示唆している。

関連論文リスト

dParallel: Learnable Parallel Decoding for dLLMs [77.24184219948337]
拡散大言語モデル(dLLM)は並列トークン予測と低推論遅延を提供する。既存のオープンソースモデルは、パフォーマンスを確保するためにトークン長のデコードステップをほとんど必要としています。高速サンプリングのためにdLLMs固有の並列性を解き放つシンプルで効果的な方法であるdParallelを導入する。
論文参考訳（メタデータ） (2025-09-30T16:32:52Z)
Learning to Parallel: Accelerating Diffusion Large Language Models via Learnable Parallel Decoding [21.609237262034636]
大規模言語モデル(LLM)における自己回帰復号には、$n$トークンに対して$mathcalO(n)$シーケンシャルステップが必要である。本稿では,並列デコード学習(Learn2PD)を提案する。これは軽量かつ適応的なフィルタモデルをトレーニングし,各トークン位置に対して,現在の予測が最終出力と一致するかどうかを予測するフレームワークである。この学習されたフィルタは、正しく予測された場合にのみトークンをアンマスクするオラクル並列復号法を近似する。
論文参考訳（メタデータ） (2025-09-29T17:59:54Z)
Fast correlated decoding of transversal logical algorithms [67.01652927671279]
大規模計算には量子エラー補正(QEC)が必要であるが、かなりのリソースオーバーヘッドが発生する。近年の進歩により、論理ゲートからなるアルゴリズムにおいて論理キュービットを共同で復号化することにより、症候群抽出ラウンドの数を削減できることが示されている。ここでは、回路を介して伝播する関連する論理演算子製品を直接復号することで、回路の復号化の問題を修正する。
論文参考訳（メタデータ） (2025-05-19T18:00:00Z)
Hardware-Aware Parallel Prompt Decoding for Memory-Efficient Acceleration of LLM Inference [23.633481089469836]
LLM(Large Language Models)の自動回帰デコーディングは、ハードウェアの性能に大きなオーバーヘッドをもたらす。トレーニング可能なパラメータを0.0002$%しか必要とせず,A100-40GBのGPUをたった16時間で効率的にトレーニングできる並列プロンプトデコーディングを提案する。我々のアプローチでは、最大2.49$times$ スピードアップを示し、最小のメモリオーバーヘッドは0.0004$%である。
論文参考訳（メタデータ） (2024-05-28T22:19:30Z)
FPGA-based Distributed Union-Find Decoder for Surface Codes [3.780617572622938]
フォールトトレラントな量子コンピュータは、エラー訂正による指数的な減速を防ぐために、エラーの復号と修正を高速に行う必要がある。並列計算資源を利用したUnion-Findデコーダの分散バージョンを報告する。
論文参考訳（メタデータ） (2024-03-20T13:36:59Z)
Fast Chain-of-Thought: A Glance of Future from Parallel Decoding Leads to Answers Faster [61.83949316226113]
FastCoTは並列デコーディングに基づくモデルに依存しないフレームワークである。我々は、FastCoTが通常のアプローチと比較して、無視できる性能低下だけで、推論時間を20%近く削減できることを示します。
論文参考訳（メタデータ） (2023-11-14T15:56:18Z)
Scalable Quantum Error Correction for Surface Codes using FPGA [67.74017895815125]
フォールトトレラントな量子コンピュータは、出現するよりも早くデコードし、エラーを修正する必要がある。並列計算資源を利用したUnion-Findデコーダの分散バージョンを報告する。この実装では、並列コンピューティングリソースをハイブリッドツリーグリッド構造に整理する、Heliosと呼ばれるスケーラブルなアーキテクチャを採用している。
論文参考訳（メタデータ） (2023-01-20T04:23:00Z)
Scalable surface code decoders with parallelization in time [8.28402656078529]
並列処理による曲面符号の高速な古典的処理を実現するスライディングウィンドウ復号方式を提案する。提案手法では, 時空のシンドロームを時間方向に沿って重なり合うウィンドウに分割し, 内部デコーダと並列に復号化することができる。
論文参考訳（メタデータ） (2022-09-19T17:42:53Z)
Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
Person Re-Identification (ReID) は、歩行者を分離したカメラで識別する。実値特徴記述子を用いた既存のReID法は精度が高いが、ユークリッド距離計算が遅いため効率が低い。本稿では,ReID 処理を 0.25 倍高速化するサブスペース一貫性規則化 (SCR) アルゴリズムを提案する。
論文参考訳（メタデータ） (2022-07-13T02:44:05Z)
A Push-Relabel Based Additive Approximation for Optimal Transport [5.111364864495785]
最適な輸送を計算するための厳密なアルゴリズムは遅くなる。我々は、OT距離の$varepsilon$approximationを求めるための、新しい非常に単純なアプローチを導入する。我々のアルゴリズムは、OT距離を計算するために、O(n2/varepsilon2)$のほぼ最適実行時間を達成する。
論文参考訳（メタデータ） (2022-03-07T21:40:14Z)
Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving [106.63673243937492]
ニューラルネットワークの評価や自己回帰モデルからのサンプリングなどのフィードフォワード計算は、機械学習においてユビキタスである。本稿では,非線形方程式の解法としてフィードフォワード計算の課題を定式化し,ジャコビ・ガウス・シーデル固定点法とハイブリッド法を用いて解を求める。提案手法は, 並列化可能な繰り返し回数の削減(あるいは等値化)により, 元のフィードフォワード計算と全く同じ値が与えられることを保証し, 十分な並列化計算能力を付与する。
論文参考訳（メタデータ） (2020-02-10T10:11:31Z)

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

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