論文の概要: A polynomial-time approximation scheme for minimum-weight decoding of topological codes
- arxiv url: http://arxiv.org/abs/2606.18145v1
- Date: Tue, 16 Jun 2026 16:44:08 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-17 17:15:32.55486
- Title: A polynomial-time approximation scheme for minimum-weight decoding of topological codes
- Title（参考訳）: 位相符号の最小重復号のための多項式時間近似法
- Abstract要約: 2D TTI)安定化符号の2次元トポロジカル変換は、フォールトトレラント量子計算の中心に位置する。
これらの符号の最小重復号化は、最近、基本的な設定でもNPハードであることが示されている。
- 参考スコア（独自算出の注目度）: 42.44256445495892
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Two-dimensional topological translationally invariant (2D TTI) stabilizer codes lie at the heart of fault-tolerant quantum computation, but using them requires solving the decoding problem. Minimum-weight decoding of these codes was recently shown to be NP-hard, even in basic settings, such as the color code with Pauli $Z$ errors and the toric code with Pauli $X$, $Y$ and $Z$ errors. Here, we prove that minimum-weight decoding of 2D TTI codes nonetheless admits a polynomial-time approximation scheme (PTAS), i.e., for any constant $\varepsilon>0$, a recovery operator of weight within a multiplicative factor of $1+\varepsilon$ of the minimum can be found in polynomial time. Our approach builds on Arora's PTAS for Euclidean problems, such as the traveling salesman problem, and applies when decoding can be cast in terms of point-like excitations connected by string-like errors. It therefore extends beyond two dimensions, covering certain higher-dimensional topological codes and quantum memories, including the toric code with phenomenological or circuit-level noise.
- Abstract（参考訳）: 2次元トポロジカル変換不変(2D TTI)安定化符号は、フォールトトレラント量子計算の中心にあるが、それを用いることで復号問題を解く必要がある。
例えば、Pauli $Z$エラーのカラーコードや、Pauli $X$、$Y$、$Z$エラーのトーリックコードなどである。
ここでは、多項式時間近似スキーム(PTAS)、すなわち任意の定数$\varepsilon>0$に対して、最小値の1+\varepsilon$の乗算係数内の重みの回復作用素が多項式時間で見つかるにもかかわらず、2D TTI符号の最小ウェイト復号が可能であることを証明する。
提案手法は, 旅行セールスマン問題などのユークリッド問題に対するAroraのPTASに基づいており, 文字列のようなエラーで接続された点状励起をデコードする場合に適用する。
したがって、2次元を超えて、特定の高次元トポロジー符号と量子記憶をカバーし、表現論的または回路レベルのノイズを持つトーリック符号を含む。
関連論文リスト
- Hardness of approximation for minimum-weight decoding of two-dimensional topological quantum codes [0.0]
位相量子符号の最小重復号法の計算複雑性について検討する。
独立な$X$-および$Z$-errorモデルの下でのカラーコードについては、分離最小ウェイトデコードを考える。
論文 参考訳（メタデータ） (2026-08-17T20:37:08Z) - High-threshold decoding of non-Pauli codes for 2D universality [0.15999407512883507]
トポロジカルコードには、比較的低いオーバーヘッドでフォールトトレラントな量子計算を可能にする多くの望ましい性質がある。
これらの符号のコアとなる課題は、接続性に制限のある低オーバヘッドのユニバーサルゲートセットを実現することである。
トポロジカルトーリックおよび曲面符号上の普遍ゲートセットを厳密に2次元で完備化するために使用できる非パウリ安定化符号を探索する。
論文 参考訳（メタデータ） (2026-04-02T13:39:46Z) - The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding [42.44256445495892]
最小ウェイトデコーディングは3つのクインテシデント設定においてNPハードであることを示す。
この結果から,最小重復号法とその近似実現法の間の計算複雑性の急激な分離が明らかとなった。
論文 参考訳（メタデータ） (2026-03-23T14:57:38Z) - Optimal Quantum $(r,δ)$-Locally Repairable Codes From Matrix-Product Codes [52.3857155901121]
最適量子$(r,delta)$-LRCを行列積(MP)符号から検討する。
フレキシブルパラメータを持つ最適量子$(r,delta)$-LRCの5つの無限族を提示する。
論文 参考訳（メタデータ） (2025-08-05T16:05:14Z) - Parallel Logical Measurements via Quantum Code Surgery [42.95092131256421]
量子符号手術(Quantum code surgery)は、量子誤り訂正符号の論理的測定を行うための、柔軟で低オーバーヘッドな技術である。
本稿では,量子ビット安定化器の低密度パリティチェック(LDPC)コードに適用可能なコード手術方式を提案する。
論文 参考訳（メタデータ） (2025-03-06T22:05:52Z) - Decoding Quasi-Cyclic Quantum LDPC Codes [23.22566380210149]
量子低密度パリティチェック(qLDPC)符号は耐故障性を求める上で重要な要素である。
近年のqLDPC符号の進歩は、量子的に良好であり、線形時間デコーダが符号ワード量子ビットの一定数に影響を与える誤りを正すという構成に繋がった。
実際には、2つの繰り返し符号の産物である表面/履歴符号は依然としてqLDPC符号として選択されることが多い。
論文 参考訳（メタデータ） (2024-11-07T06:25:27Z) - SSIP: automated surgery with quantum LDPC codes [55.2480439325792]
クビットCSSコード間の手術を自動化するための,オープンソースの軽量PythonパッケージであるSSIP(Identifying Pushouts)による安全手術について述べる。
ボンネットの下では、鎖複体の圏における普遍構成によって支配される$mathbbF$上の線型代数を実行する。
高い符号距離を犠牲にすることなく,手術によって様々な論理的測定を安価に行うことができることを示す。
論文 参考訳（メタデータ） (2024-07-12T16:50:01Z) - Estimating the Decoding Failure Rate of Binary Regular Codes Using Iterative Decoding [84.0257274213152]
並列ビットフリップデコーダのDFRを高精度に推定する手法を提案する。
本研究は,本症候群のモデル化およびシミュレーションによる重み比較,第1イテレーション終了時の誤りビット分布の誤検出,復号化復号化率(DFR)について検証した。
論文 参考訳（メタデータ） (2024-01-30T11:40:24Z) - Extracting topological orders of generalized Pauli stabilizer codes in two dimensions [5.593891873998947]
本稿では,2次元システムにおける変換不変な一般化されたパウリ安定化符号から位相データを抽出するアルゴリズムを提案する。
このアルゴリズムは$mathbbZ_d$ quditsに適用される。
論文 参考訳（メタデータ） (2023-12-18T13:18:19Z) - Error-correcting codes for fermionic quantum simulation [4.199246521960609]
二次元格子アルゴリズムを用いた量子ビットシステムによるフェルミオンの手法を提案する。
フェミオンシミュレーションに適した安定化符号群を同定する。
我々の手法は、(フェルミオン)符号率を低下させることなく、符号距離を増大させることができる。
論文 参考訳（メタデータ） (2022-10-16T01:43:07Z) - Efficient color code decoders in $d\geq 2$ dimensions from toric code
decoders [77.34726150561087]
Restriction Decoderは、対応するトーリックコード復号が成功した場合に限り、カラーコードのエラーを修正する。
ビットフリップと位相フリップの雑音に対して、2次元、3次元のカラーコードに対する制限デコーダ閾値を数値的に推定する。
論文 参考訳（メタデータ） (2019-05-17T17:41:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。