論文の概要: Improved decoding algorithms for surface codes under independent bit-flip and phase-flip errors

• arxiv url: http://arxiv.org/abs/2601.00972v1
• Date: Fri, 02 Jan 2026 19:43:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-06 16:25:21.919048
• Title: Improved decoding algorithms for surface codes under independent bit-flip and phase-flip errors
• Title（参考訳）: 独立ビットフリップおよび位相フリップ誤差下における曲面符号の復号化アルゴリズムの改良
• Authors: Louay Bazzi,
• Abstract要約: 標準独立雑音モデル(X/Z)の下で,トーリック符号と平面および回転曲面符号の正確な復号化について検討した。 我々は, (O(n3/2log n)) 時間デコーダが表面およびトーリック符号に対して実現可能であることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study exact decoding for the toric code and for planar and rotated surface codes under the standard independent \(X/Z\) noise model, focusing on Separate Minimum Weight (SMW) decoding and Separate Most Likely Coset (SMLC) decoding. For the SMW decoding problem, we show that an \(O(n^{3/2}\log n)\)-time decoder is achievable for surface and toric codes, improving over the \(O(n^{3}\log n)\) worst-case time of the standard approach based on complete decoding graphs. Our approach is based on a local reduction of SMW decoding to the minimum weight perfect matching problem using Fisher gadgets, which preserves planarity for planar and rotated surface codes and genus~\(1\) for the toric code. This reduction enables the use of Lipton--Tarjan planar separator methods and implies that SMW decoding lies in \(\mathrm{NC}\). For SMLC decoding, we show that the planar surface code admits an exact decoder with \(O(n^{3/2})\) algebraic complexity and that the problem lies in \(\mathrm{NC}\), improving over the \(O(n^{2})\) algebraic complexity of Bravyi \emph{et al.} Our approach proceeds via a dual-cycle formulation of coset probabilities and an explicit reduction to planar Pfaffian evaluation using Fisher--Kasteleyn--Temperley constructions. The same complexity measures apply to SMLC decoding of the rotated surface code. For the toric code, we obtain an exact polynomial-time SMLC decoder with \(O(n^{3})\) algebraic complexity. In addition, while the SMLC formulation is motivated by connections to statistical mechanics, we provide a purely algebraic derivation of the underlying duality based on MacWilliams duality and Fourier analysis. Finally, we discuss extensions of the framework to the depolarizing noise model and identify resulting open problems.
• Abstract（参考訳）: 本稿では,SMWデコードとSMLCデコードに着目し,標準独立型 \(X/Z\) ノイズモデルに基づくトーリック符号と平面および回転曲面符号の正確な復号について検討する。 SMW復号問題では, 曲面およびトーリック符号に対して, \(O(n^{3/2}\log n)\)-時間デコーダが実現可能であることを示す。 提案手法は, 平面および回転曲面符号の平面性を保ち, トーリック符号の種数 −\(1\) を保存したFisherガジェットを用いて, SMWデコーディングを最小ウェイト完全マッチング問題に局所的に還元することに基づく。 この還元により、リプトン-タージャン平面分離器法が利用可能となり、SMW復号法が \(\mathrm{NC}\) に含まれることが示唆される。 SMLC復号法では、平面曲面符号が \(O(n^{3/2})\) 代数的複雑性を持つ正確な復号器を許容し、問題は \(O(n^{2})\) 代数的複雑性の改善である。 回転した曲面符号のSMLC復号にも同様の複雑さが適用される。 トーリック符号に対しては、(O(n^{3})\)代数的複雑性を持つ多項式時間SMLCデコーダを得る。 さらに、SMLCの定式化は統計力学との接続によって動機付けられるが、MacWilliams双対性とフーリエ解析に基づく基礎的双対性の純粋代数的導出を提供する。 最後に, 脱分極雑音モデルへのフレームワークの拡張について検討し, 結果として生じる開放的問題を同定する。

関連論文リスト

• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Progressive-Proximity Bit-Flipping for Decoding Surface Codes [8.971989179518214]
  トリックやサーフェスコードのようなトポロジカル量子コードは、ハードウェア実装の優れた候補である。 既存のデコーダは、計算複雑性の低いような要求を満たすのに不足することが多い。 トリックおよび表面符号に適した新しいビットフリップ(BF)デコーダを提案する。
  論文  参考訳（メタデータ） (2024-02-24T22:38:05Z)
• CORE: Common Random Reconstruction for Distributed Optimization with Provable Low Communication Complexity [110.50364486645852]
  コミュニケーションの複雑さは、トレーニングをスピードアップし、マシン番号をスケールアップする上で、大きなボトルネックになっています。 本稿では,機械間で送信される情報を圧縮するための共通Om REOmを提案する。
  論文  参考訳（メタデータ） (2023-09-23T08:45:27Z)
• Machine Learning-Aided Efficient Decoding of Reed-Muller Subcodes [59.55193427277134]
  Reed-Muller (RM) 符号は、一般的なバイナリインプットメモリレス対称チャネルの容量を達成する。 RM符号は制限されたレートのみを許容する。 効率的なデコーダは、RM符号に対して有限長で利用可能である。
  論文  参考訳（メタデータ） (2023-01-16T04:11:14Z)
• FeDXL: Provable Federated Learning for Deep X-Risk Optimization [105.17383135458897]
  我々は、既存のアルゴリズムが適用できないXリスクのファミリーを最適化するために、新しい連邦学習(FL)問題に取り組む。 Xリスクに対するFLアルゴリズムを設計する際の課題は、複数のマシンに対する目的の非可逆性と、異なるマシン間の相互依存にある。
  論文  参考訳（メタデータ） (2022-10-26T00:23:36Z)
• Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learning [58.91954425047425]
  本稿では,分散学習における部分トラグラーの緩和を目的とした,新たな勾配符号化方式を提案する。 L の符号パラメータを L に表わした勾配座標符号化方式を提案する。
  論文  参考訳（メタデータ） (2022-06-06T09:25:40Z)
• A Learning-Based Approach to Address Complexity-Reliability Tradeoff in OS Decoders [32.35297363281744]
  本稿では,人工ニューラルネットワークを用いて順序統計に基づくデコーダの必要な順序を予測することで,平均的複雑性やデコーダの遅延を低減できることを示した。
  論文  参考訳（メタデータ） (2021-03-05T18:22:20Z)

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

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