論文の概要: Proof of a finite threshold for the union-find decoder

• arxiv url: http://arxiv.org/abs/2602.20238v1
• Date: Mon, 23 Feb 2026 19:00:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-25 17:34:53.485081
• Title: Proof of a finite threshold for the union-find decoder
• Title（参考訳）: ユニオンフィンデコーダに対する有限しきい値の証明
• Authors: Satoshi Yoshida, Ethan Lake, Hayata Yamasaki,
• Abstract要約: 本稿では,回路レベルの局所誤差モデルに基づく表面符号上でのUnion-find(UF)デコーダに対する有限しきい値の証明を行う。 また,より単純なデコーダであるgreedyデコーダの有限しきい値が得られることを示す。 これらの結果は、フォールトトレラント量子コンピュータの開発において、UFベースのデコーダを実用化するための確かな理論基盤を提供する。
• 参考スコア（独自算出の注目度）: 0.9558392439655014
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Fast decoders that achieve strong error suppression are essential for fault-tolerant quantum computation (FTQC) from both practical and theoretical perspectives. The union-find (UF) decoder for the surface code is widely regarded as a promising candidate, offering almost-linear time complexity and favorable empirical error suppression supported by numerical evidence. However, the lack of a rigorous threshold theorem has left open whether the UF decoder can achieve fault tolerance beyond the error models and parameter regimes tested in numerical simulations. Here, we provide a rigorous proof of a finite threshold for the UF decoder on the surface code under the circuit-level local stochastic error model. To this end, we develop a refined error-clustering framework that extends techniques previously used to analyze cellular-automaton and renormalization-group decoders, by showing that error clusters can be separated by substantially larger buffers, thereby enabling analytical control over the behavior of the UF decoder. Using this guarantee, we further prove a quasi-polylogarithmic upper bound on the average runtime of a parallel UF decoder in terms of the code size. We also show that this framework yields a finite threshold for the greedy decoder, a simpler decoder with lower complexity but weaker empirical error suppression. These results provide a solid theoretical foundation for the practical use of UF-based decoders in the development of fault-tolerant quantum computers, while offering a unified framework for studying fault tolerance across these practical decoders.
• Abstract（参考訳）: フォールトトレラント量子計算(FTQC)において, 高い誤差抑制を実現する高速デコーダは, 実用的, 理論的両面から必須である。 表面符号に対するユニオンフィンド(UF)デコーダは、ほぼ直線的な時間複雑性と、数値的な証拠によって支持された好ましい経験的誤り抑制を提供する、有望な候補として広く見なされている。 しかし、厳密なしきい値定理の欠如は、UFデコーダがエラーモデルや数値シミュレーションで検証されたパラメータ規則を超えた耐故障性を達成できるかどうかを未然に残している。 ここでは、回路レベルの局所確率誤差モデルの下で、表面符号上のUFデコーダの有限しきい値の厳密な証明を行う。 そこで我々は,従来セルオートマトンと再正規化グループデコーダを解析するために用いられてきた手法を拡張した誤りクラスタリングフレームワークを開発し,エラークラスタをかなり大きなバッファで分離できることを示し,UFデコーダの動作を解析的に制御できるようにする。 この保証を用いて、符号サイズの観点から、並列UFデコーダの平均実行時における準多言語上界をさらに証明する。 また,より単純なデコーダであるgreedyデコーダの有限しきい値が得られることを示す。 これらの結果は、耐故障性量子コンピュータの開発においてUFベースのデコーダを実用的に使用するための確かな理論基盤を提供するとともに、これらの実用デコーダをまたいだ耐故障性を研究するための統一的なフレームワークを提供する。

関連論文リスト

• Approximate level-by-level maximum-likelihood decoding based on the Chase algorithm for high-rate concatenated stabilizer codes [0.0]
  量子誤り訂正符号を用いて論理量子ビットを符号化することが不可欠である。 フォールトトレラントプロトコルの理論的進歩により、高水準符号が注目されている。 本稿では,高階安定化器符号のための汎用高性能デコーダを提案する。
  論文  参考訳（メタデータ） (2026-01-26T18:04:29Z)
• Toward Uncertainty-Aware and Generalizable Neural Decoding for Quantum LDPC Codes [0.9453554184019106]
  量子誤り訂正(QEC)はスケーラブルな量子コンピューティングに不可欠である。 我々は,ドット生成物とマルチヘッドの両方に注意を集中させるベイズグラフニューラルデコーダである textbfQuBA を提案する。 textbfSAGU textbf(Sequential Aggregate Generalization under Uncertainty)は、ドメイン間の堅牢性を向上したマルチコードトレーニングフレームワークである。
  論文  参考訳（メタデータ） (2025-10-05T01:08:39Z)
• BF-Max: an Efficient Bit Flipping Decoder with Predictable Decoding Failure Rate [6.209770040937912]
  Bit-Flipping (BF) デコーダはポスト量子暗号方式で広く使われている。 セキュリティ上の問題に対して、デコード失敗率(DFR)が無視可能であることを保証しなければならない。 我々はBFデコーダの新バージョンを導入し、BF-Maxと呼ぶ。
  論文  参考訳（メタデータ） (2025-06-11T13:04:05Z)
• Linear Time Iterative Decoders for Hypergraph-Product and Lifted-Product Codes [3.8748565070264753]
  量子低密度パリティチェック(QLDPC)符号は、フォールトトレラントな量子計算を実現するための重要な候補である。 多くの研究が、QLDPC符号の能力をフル活用するために高速デコーダの必要性を主張している。 しかし、実証的な調査は、QLDPC符号を復号化しながら高いエラーフロアを持つような反復復号化が可能であることを示唆している。
  論文  参考訳（メタデータ） (2025-04-02T13:37:29Z)
• Testing the Accuracy of Surface Code Decoders [55.616364225463066]
  大規模でフォールトトレラントな量子計算は量子エラー訂正符号(QECC)によって実現される 本研究は,QECC復号方式の精度と有効性をテストするための最初の体系的手法である。
  論文  参考訳（メタデータ） (2023-11-21T10:22:08Z)
• Modular decoding: parallelizable real-time decoding for quantum computers [55.41644538483948]
  リアルタイム量子計算は、ノイズの多い量子ハードウェアによって生成されたデータのストリームから論理的な結果を取り出すことができる復号アルゴリズムを必要とする。 本稿では,デコーディングの精度を犠牲にすることなく,最小限の追加通信でこの問題に対処できるモジュールデコーディングを提案する。 本稿では,格子探索型耐故障ブロックのモジュールデコーディングの具体例であるエッジ頂点分解について紹介する。
  論文  参考訳（メタデータ） (2023-03-08T19:26:10Z)
• Deep Quantum Error Correction [73.54643419792453]
  量子誤り訂正符号(QECC)は、量子コンピューティングのポテンシャルを実現するための鍵となる要素である。 本研究では,新しいエンペンド・ツー・エンドの量子誤りデコーダを効率的に訓練する。 提案手法は,最先端の精度を実現することにより,QECCのニューラルデコーダのパワーを実証する。
  論文  参考訳（メタデータ） (2023-01-27T08:16:26Z)
• Neural Belief Propagation Decoding of Quantum LDPC Codes Using Overcomplete Check Matrices [60.02503434201552]
  元のチェック行列における行の線形結合から生成された冗長な行を持つチェック行列に基づいてQLDPC符号を復号する。 このアプローチは、非常に低い復号遅延の利点を付加して、復号性能を著しく向上させる。
  論文  参考訳（メタデータ） (2022-12-20T13:41:27Z)
• A Practical and Scalable Decoder for Topological Quantum Error Correction with Digital Annealer [0.5658123802733283]
  富士通デジタルアニール(DA)を用いた量子誤り訂正のための効率的でスケーラブルなデコーダを提案する。 特に,提案したDAデコーダを表面コードに実装し,様々なコードに対して詳細な数値実験を行い,その性能とスケーラビリティを検証した。 また、DAデコーダはハードウェア実装を含む様々な観点からUnion-Find(UF)デコーダよりも利点があることが示されている。
  論文  参考訳（メタデータ） (2022-03-29T07:48:51Z)
• Improved decoding of circuit noise and fragile boundaries of tailored surface codes [61.411482146110984]
  高速かつ高精度なデコーダを導入し、幅広い種類の量子誤り訂正符号で使用することができる。 我々のデコーダは、信仰マッチングと信念フィンドと呼ばれ、すべてのノイズ情報を活用し、QECの高精度なデモを解き放つ。 このデコーダは, 標準の正方形曲面符号に対して, 整形曲面符号において, より高いしきい値と低い量子ビットオーバーヘッドをもたらすことがわかった。
  論文  参考訳（メタデータ） (2022-03-09T18:48:54Z)

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

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